쾨니그의 정리

이 문서는 그래프의 꼭짓점 덮개와 최대 부합에 관한 것입니다. 무한 그래프에 대한 정리에 대해서는 쾨니그 보조정리 문서를, 기수에 대한 정리에 대해서는 쾨니그의 정리 (집합론) 문서를 참고하십시오.

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

어떤 그래프 ${\displaystyle \Gamma }$의 꼭짓점 덮개(영어: vertex cover) ${\displaystyle C\subset V(\Gamma )}$는 다음을 만족시키는 집합이다.

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

최소 꼭짓점 덮개는 크기가 최소인 꼭짓점 덮개이다.

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

${\displaystyle |M|=|C|}$

이다.

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

헝가리의 수학자 쾨니그 데네시가 1931년에 증명하였다.^[1][2]:289

• “König theorem”. 《Encyclopedia of Mathematics》 (영어). Springer-Verlag. 2001. ISBN 978-1-55608-010-4. 
• Weisstein, Eric Wolfgang. “König's Line Coloring Theorem”. 《Wolfram MathWorld》 (영어). Wolfram Research.