그래프의 아이소멀피즘

그래프의 아이소멀피즘

Isomorphism of graphs

정의 1

그래프 $G_{1}$ 와 $G_{2}$ 가 주어져 있다고 하자. $V(G_{1})$ 과 $V(G_{2})$ 사이에 전단사가 존재하고 $G_{1}$ 의 버텍스끼리의 에지의 수와 그에 대응하는 $G_{2}$ 의 버텍스끼리의 에지의 수가 같으면 그 전단사를 아이소멀피즘이라 하고 두 그래프가 아이소멀픽Isomorphic하다고 한다. 다시 말해, 다음을 만족하는 전단사 $\phi : G_{1} \to G_{2}$ 를 아이소멀피즘이라 부른다. $$ u \sim_{1} v \iff \phi (u) \sim_{2} \phi (v) $$

예시

예로써 다음 두 그래프를 살펴보자: 20200128\_142425.png 20200128\_142548.png

위의 두 그래프는 물론 엄밀히 말해서 같은 것은 아니다. 물론 그래프를 구별할 때 겉으로 보이는 모습은 중요하지 않다. 그러나 그것을 차치하고서라도 버텍스의 집합과 에지의 집합이 엄연히 다르기 때문에 다르다. 하지만 다음과 같은 일대일 대응관계를 주면 두 그래프는 사실상 같은 것으로 볼 수 있다. $$ A \leftrightarrow x \\ B \leftrightarrow y \\ C \leftrightarrow z \\ D \leftrightarrow u \\ E \leftrightarrow v \\ F \leftrightarrow w $$

같이보기


  1. Wilson. (1970). Introduction to Graph Theory: p9. ↩︎

댓글