이분 그래프

쾨니그의 정리는 여기로 연결됩니다. 무한 그래프에 대한 정리에 대해서는 쾨니그 보조정리 문서를 참고하십시오.

쾨니그의 정리는 여기로 연결됩니다. 기수에 대한 정리에 대해서는 쾨니그의 정리 (집합론) 문서를 참고하십시오.

이분 그래프의 예

위 그래프의 그래프 색칠

2색변 이분 그래프의 예

그래프 이론에서, 이분 그래프(二分graph, 영어: bipartite graph)란 모든 꼭짓점을 빨강과 파랑으로 색칠하되, 모든 변이 빨강과 파랑 꼭짓점을 포함하도록 색칠할 수 있는 그래프이다.

정의

그래프 $\Gamma =(V,E)$와 자연수 $k\in \mathbb {N}$가 주어졌다고 하자. 만약 $V$가 다음과 같은 조건을 만족시키는 집합의 분할

$V=V_{1}\sqcup V_{2}\sqcup \dotsb \sqcup V_{k}$

을 가질 수 있다면, $\Gamma$를 $k$분 그래프(-分graph, 영어: $k$-partite graph)라고 한다.

• 변으로 연결된 두 꼭짓점은 서로 다른 분할 성분에 속한다. 즉, 임의의 변 $(u,v)\in E$에 대하여, 만약 $u\in V_{i}$이며 $v\in V_{j}$라면, $i\neq j$이다.

즉, $\Gamma$의 색칠수가 $k$ 이하이어야 한다.

$k=2$일 때, 이를 이분 그래프라고 한다. 마찬가지로, $k=3$일 때, 이를 삼분 그래프(三分graph, 영어: tripartite graph)라고 한다.

성질

임의의 유한 그래프 $\Gamma$에 대하여 다음 두 조건이 서로 동치이다.

• 이분 그래프이다.
• 홀수 길이의 순환이 존재하지 않는다.

특히, 예를 들어 홀수 길이의 순환 그래프는 이분 그래프가 될 수 없다.

이분 그래프의 색칠수는 2 이하이므로, 비징의 정리에 대하여, 이분 그래프는 항상 1종 그래프이다. (꼭짓점의 최대 차수가 1 이하인 그래프는 자명하게 1종 그래프이다.)

쾨니그 정리

쾨니그 정리에 따르면, 이분 그래프에서, 최대 부합의 변(청색) 수는 최소 꼭짓점 덮개의 꼭짓점(적색) 수와 같다.

쾨니그 정리(Kőnig定理, 영어: Kőnig’s theorem)에 따르면, 이분 그래프의 경우 대한 최소 꼭짓점 덮개 문제와 최대 부합 문제가 서로 동치이다.

구체적으로, 어떤 그래프 $\Gamma$의 꼭짓점 덮개(영어: vertex cover) $C\subset V(\Gamma )$는 다음을 만족시키는 집합이다.

• 모든 변 $e\in E(\Gamma )$에 대하여, $e$와 접하는 $c\in C$가 존재한다.

최소 꼭짓점 덮개(영어: minimal vertex cover)는 포함 관계에 대하여 최소 원소인 꼭짓점 덮개이다.

쾨니그 정리에 따르면, 유한 이분 그래프 $\Gamma$의 최대 부합 $M\subset E(\Gamma )$ 및 최소 꼭짓점 덮개 $C\subset V(\Gamma )$에 대하여,

$|M|=|C|$

이다.^:289

조합적 집합론에서는 쾨니그 정리를 일반화하는 홀 결혼 정리가 존재한다. 쾨니그 정리와 홀의 정리 및 딜워스의 정리는 서로 동치이다.

변별 알고리즘

주어진 그래프가 이분 그래프인지 확인하는 것은 어렵지 않다. 그래프의 꼭짓점들을 깊이 우선 탐색으로 나열한 뒤, 각 꼭짓점들을 이웃 꼭짓점들과 다른 색으로 계속해서 칠해 나가면서, 같은 색깔의 꼭짓점이 서로 연결되어 있는 모순이 발생하는지 여부를 확인하면 된다. 이 알고리즘은 O(|V|+|E|)이다.

예

0분 그래프는 공 그래프 (꼭짓점과 변이 없는 그래프) 밖에 없다. 1분 그래프는 이산 그래프 (즉, 아무런 변이 없는 그래프)와 동치인 개념이다.

모든 나무는 (순환이 없으므로) 이분 그래프이다. 짝수 길이의 순환은 이분 그래프이지만, 홀수 길이의 순환은 이분 그래프가 아니다.

완전 $k$분 그래프

 이 부분의 본문은 완전 이분 그래프입니다.

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

$V=V_{1}\sqcup \dotsb V_{k}$

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

$E=\bigsqcup _{1\leq i<j\leq k}V_{i}\times V_{j}$

데생당팡

 이 부분의 본문은 데생당팡입니다.

리만 곡면에 대하여, 어떤 유한 평면 이분 그래프를 대응시킬 수 있다. 이를 데생당팡이라고 한다.

역사

쾨니그 정리는 쾨니그 데네시와 에게르바리 예뇌가 각자 독자적으로 1931년에 증명하였다.

외부 링크

• “Graph, bipartite”. 《Encyclopedia of Mathematics》 (영어). Springer-Verlag. 2001. ISBN 978-1-55608-010-4. 
• “König theorem”. 《Encyclopedia of Mathematics》 (영어). Springer-Verlag. 2001. ISBN 978-1-55608-010-4. 
• Weisstein, Eric Wolfgang. “Bipartite graph”. 《Wolfram MathWorld》 (영어). Wolfram Research. 
• Weisstein, Eric Wolfgang. “Bicolorable graph”. 《Wolfram MathWorld》 (영어). Wolfram Research. 
• Weisstein, Eric Wolfgang. “Three-colorable graph”. 《Wolfram MathWorld》 (영어). Wolfram Research. 
• Weisstein, Eric Wolfgang. “k-partite graph”. 《Wolfram MathWorld》 (영어). Wolfram Research. 
• Weisstein, Eric Wolfgang. “k-colorable graph”. 《Wolfram MathWorld》 (영어). Wolfram Research. 
• Weisstein, Eric Wolfgang. “König's Line Coloring Theorem”. 《Wolfram MathWorld》 (영어). Wolfram Research. 
• Weisstein, Eric Wolfgang. “König-Egeváry Theorem”. 《Wolfram MathWorld》 (영어). Wolfram Research. 
• “Bipartite graph”. 《nLab》 (영어).