📂그래프이론

그래프 컴플리먼트

정의 ¹

심플 그래프 $G$ 에 대해 다음을 만족하는 그래프 $\overline{G}$ 를 $G$ 의 컴플리먼트라 한다. $$ V \left( \overline{G} \right) = V(G) \\ vw \in E \left( \overline{G} \right) \iff vw \notin E(G) $$

설명

보통의 수학에서 컴플리먼트^complement가 그러하듯 그래프의 컴플리먼트는 補(도울 보)의 개념을 의미한다. 한국어 순화로는 여그래프^{complement Graph}가 될텐데, 다 마음에 들지 않아서 그냥 컴플리먼트라 쓴다.

그림을 보고 직관적으로 이해해보면 어려울 게 없지만, 수식으로만 설명하자면 다소 껄끄러운 부분이 있다. 이러한 표현을 도입함으로써 그래프를 조금 더 편리하고 쉽게 다룰 수 있게 된다. 컴플리먼트 그래프의 예로써 다음 그림을 살펴보자:

두 그래프 $G$ 와 $\overline{G}$ 는 같은 버텍스를 가지고 있으면서 에지는 정 반대로 가지고 있다. 이런 설명에서 ‘정 반대로’라는 표현이 수학적으로 좋다고 할 순 없을 것이다. 그렇다고 명제 $$ vw \in E \left( \overline{G} \right) \iff vw \notin E(G) $$ 로 설명하면 수학적으로는 깔끔하지만 자연스럽게 읽기가 조금 어려워진다. 대신 이를 그냥 컴플리먼트라고 표현하면 예시 하나로 이해하고 수식 없이 수학적인 논의를 이어가기가 편해진다.