쾨니그의 정리: 두 판 사이의 차이

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

[[파일:Koenigs-theorem-graph.svg|thumb|right|[[최대 부합]]의 변(청색) 수는 최소 꼭지점꼭짓점 덮개의 꼭지점꼭짓점(적색) 수와 같다.]]

어떤 그래프 <math>\Gamma</math>의 '''꼭지점꼭짓점 덮개'''({{llang|en|vertex cover}}) <math>C\subset V(\Gamma)</math>는 다음을 만족시키는 집합이다.

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

'''쾨니그의 정리'''에 따르면, [[이분 그래프]] <math>\Gamma</math>의 [[최대 부합]] <math>M\subset E(\Gamma)</math> 및 최소 꼭지점꼭짓점 덮개 <math>C\subset V(\Gamma)</math>에 대하여,