📂그래프이론

그래프의 아이소멀피즘

정의 ¹

두 그래프 $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)$$

예시

예로써 다음 두 그래프를 살펴보자:

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

같이보기

• 추상대수학에서의 아이소멀피즘
• 그래프 호메오멀피즘