이분 그래프

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

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

이분 그래프의 예

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$에 대하여 다음 두 조건이 서로 동치이다.

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

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

쾨니그 정리

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

쾨니그 정리(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

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

변별 알고리즘

이분 그래프의 변별 알고리즘 적용

주어진 그래프가 이분 그래프인지 확인하는 것은 어렵지 않다. 꼭짓점 하나를 빨강으로 칠한 후 이웃 꼭짓점들은 녹색으로 칠하고 그 이웃들은 빨강으로 칠하는 것들을 반복하면서, 같은 색깔의 꼭짓점이 서로 연결되어 있는 모순이 발생하는지 아닌지 확인만 하면 된다. 예를 들어, 크기가 3인 순환 그래프는 이분 그래프가 아니다.

예

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}$

데생당팡

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

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

역사

쾨니그 정리는 쾨니그 데네시와 에게르바리 예뇌(헝가리어: Egerváry Jenő, 1891~1958)가 각자 독자적으로 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. “k-partite graph”. 《Wolfram MathWorld》 (영어). Wolfram Research. 
• Weisstein, Eric Wolfgang. “k-colorable graph”. 《Wolfram MathWorld》 (영어). Wolfram Research. 
• 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. 
• 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.