완전 이분 그래프

그래프 이론에서 완전 이분 그래프(完全二分graph, 영어: complete bipartite graph)란 꼭짓점의 집합이 서로 겹치지 않는 두 집합 X와 Y의 합집합이고 X의 모든 꼭짓점이 Y의 각각의 꼭짓점과 하나의 변으로 연결되어 있는 이분 그래프이다.

정의

집합 $V$의 $k$조각 분할

$V=V_1\bigsqcup \cdots V_k$

가 주어졌다고 하자. 이 집합의 분할에 대응하는 완전 $k$분 그래프(영어: complete $k$-partite graph)는 위와 같은 분할에 대하여 $k$분 그래프를 이루는, 가장 변을 많이 갖는 그래프이다. 즉, 그 변의 집합은 다음과 같은 꼴이다.

$E=\underset{1\le i<j\le k}{⨆}{V}_i\times V_j$

$V_1,\dots ,V_k$의 집합의 크기가 각각 $n_1,\dots ,n_k$일 때, 이에 대응하는 완전 $k$분 그래프는 $K_{n_1,\dots ,n_k}$로 표기한다.

$k=1$일 경우, 이는 완전 그래프와 같다. $k=2$일 경우 이를 완전 이분 그래프(完全二分graph, 영어: complete bipartite graph), $k=3$일 경우 이를 완전 삼분 그래프(完全三分graph, 영어: complete tripartite graph)라고 한다.

성질

색칠

정의에 따라, 완전 $k$분 그래프는 $k$분 그래프이며, 그 채색수는 $k$ 이하이다.

$\chi (K_{n_1,\dots ,n_k})\le k$

특히, 만약 $0<\min \{n_1,\dots ,n_k\}$일 경우, 그 채색수는 $k$이다.

$0<\min \{n_1,\dots ,n_k\}⟹\chi (K_{n_1,\dots ,n_k})=k$

크기

완전 $k$분 그래프 $K_{n_1,\dots ,n_k}$의 꼭짓점의 수는

$|V(K_{n_1,\dots ,n_k})|=\sum _{i=1}^k{n}_k$

이며, 변의 수는

$|V(K_{n_1,\dots ,n_k})|=\prod _{i=1}^k{n}_k$

이다.

그래프의 평면성

섬네일을 만드는 중 오류 발생:  이 부분의 본문은 평면 그래프입니다.

평면 그래프는 $K_{3,3}$를 그래프 마이너로 가질 수 없다. 반대로, 평면 그래프가 아닌 모든 그래프는 $K_{3,3}$ 또는 $K_5$를 그래프 마이너로 갖는다 (바그너 정리 영어: Wagner’s theorem)

예

• K3,1
  K_3,1
• K3,2
  K_3,2
• 섬네일을 만드는 중 오류 발생:
  K_3,3

역사

이미 1669년에 아타나시우스 키르허가 완전 이분 그래프의 그림을 출판하였다.

외부 링크

• “Graph, bipartite” (영어). 《Encyclopedia of Mathematics》. Springer-Verlag. 2001. ISBN 978-1-55608-010-4. 
• Weisstein, Eric Wolfgang. “Complete bipartite graph” (영어). 《Wolfram MathWorld》. Wolfram Research. 
• Weisstein, Eric Wolfgang. “Complete tripartite graph” (영어). 《Wolfram MathWorld》. Wolfram Research. 
• Weisstein, Eric Wolfgang. “Complete k-partite graph” (영어). 《Wolfram MathWorld》. Wolfram Research.