📂그래프이론

널 그래프와 컴플리트 그래프

정의 ¹

심플 그래프 $G$ 가 주어져 있다고 하자.

1. $E(G) = \emptyset$ 이면 $G$ 를 널 그래프라고 한다.
2. $E \left( \overline{G} \right) = \emptyset$ 이면 $G$ 를 컴플리트 그래프라고 한다.

설명

널 그래프는 말 그대로 비어있는 그래프를 의미한다. 여기서 Empty(빌 공, 空)이 아니라 Null(영 영, 零)이라는 표현을 쓴 이유는 실제로 $G \ne \emptyset$ 일지라도 그래프로써 아무런 의미가 없기 때문이다. 예컨대 다음의 그림처럼 버텍스만 있다면 딱히 그래프라고 부를 이유가 없다. 하지만 $0$ 이라는 수가 수학에서 엄청나게 중요한 것과 비슷하게, 널 그래프 그래프 이론 전반에서 매우 자주 언급된다.

컴플리트 그래프는 원래 그래프 $G$ 의 컴플리먼트 $\overline{G}$ 로 정의된다. $\overline{G}$ 가 널 그래프라는 것은 원래 그래프 $G$ 의 모든 버텍스들이 빠짐없이 연결되어 있음을 의미한다. 가령 위 그래프의 컴플리먼트인 다음과 같다.

따름 정의

특히 버텍스의 수가 $n$ 인 컴플리트 그래프를 $K_{n}$ 과 같이 표기하기도 한다.

• 어떤 그래프의 서브 그래프로써 컴플리트 그래프인 경우엔 클리크^clique라 부른다.
• 그래프 $G$ 의 클리크 $K_{n}$ 중 가장 큰 $n$ 을 $G$ 의 클리크 수^{clique number} $\omega (G)$ 라 하고,
• $G$ 의 컴플리먼트 $\overline{G}$ 의 클리크 수를 $G$ 의 독립 수^{independence number} $\beta (G) := \omega \left( \overline{G} \right)$ 라 한다.
• 한편 방향이 있는 컴플리트 그래프를 토너먼트^tournament라 부른다.