Graph isomorphism 설명 (그래프 동형이란? Graph isomorphism 활용 및 검증)

Isomorphic graph는 노드의 ordering의 차이로 인해 다르게 표현되지만 완전히 같은 구조를 가지고 있는 그래프들을 말한다. 이번 글에서는 graph isomorphism이 무엇인지에 대해 알아보고, 이것이 graph representation을 표현할 때 어떻게 활용될 수 있는지에 대해 알아보겠다. 정의 Isomorphic graph는 위에서 언급했듯이, 노드의 ordering의 차이로 인해 다르게 표현되지만 완전히 같은 구조를 가지고 있는 그래프들을 말한다. 예를 들어, 다음과 같은 두 그래프가 있다고 하자. 두 그래프를 비교해 보면 다르게 생긴 것처럼 보인다. 하지만, 각 노드가 연결된 구조를 살펴보면 두 그래프가 정확히 같은 구조를 가지고 있는 것을 알 수 있다. 각 노드가 가지고 ..