📂그래프이론

그래프의 호메오멀피즘

정의 ¹

두 그래프 $G_{1}$ 와 $G_{2}$ 가 주어져 있다고 하자. $G_{1}$ 의 어떤 세분 $G_{1} '$ 과 $G_{2}$ 의 어떤 세분 $G_{2} '$ 에 대해 그래프 아이소멀피즘이 존재하면 $G_{1}$ 와 $G_{2}$ 가 호메오멀픽^homeomorphic하다고 한다.

---

• 그래프 $G$ 에 다음과 같은 조건을 만족하는 버텍스 $w$ 들을 차례로 추가한 그래프를 $G$ 의 세분^subdivision $G'$ 이라 한다. $$\begin{align*} u \sim_{G} v & \implies \begin{cases} u \nsim_{G'} v \\ u \sim_{G'} w \\ w \sim_{G'} v \\ \deg w = 2 \end{cases} \end{align*}$$
• $x \sim_{A} y$ 는 그래프 $A$ 에서 두 버텍스 $x,y$ 가 인접함을 의미한다.

설명

쉽게 말해, 원래 그래프에서 이어져있던 에지를 끊고 그 사이에 $w$ 가 추가된 그래프를 말한다. 다음의 그림으로 보면 이해하기 한결 더 쉽다.

그림에서 오른쪽에 있는 두 개의 그래프는 왼쪽에 주어진 그래프 $G$ 의 세분 중 두가지 예시를 나타낸 것이다. 추가되는 버텍스는 꼭 하나일 필요도 없고 동시에 한 에지에 들어가도 좋다.

다음은 호메오멀픽한 두 그래프의 예시다.

이러한 세분을 잘 살펴보면 버텍스를 추가하든 말든 원래 그래프에서 곧게 관통하는 연결 관계는 변하지 않았음을 확인할 수 있다. 이 개념을 사용하면 다음과 같은 두 그래프가 사실상 같다는 이야기를 할 수 있다. 그래프 호메오멀피즘은 정확하게 구조적인 같음에 대한 그래프 아이소멀피즘과 달리 실질적으로 공간적인 같음을 다루며, 단어 자체도 위상수학의 호메오멀피즘에서 왔다.

같이보기

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