쾨니그의 정리

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

정의 

어떤 그래프 의 꼭짓점 덮개() 는 다음을 만족시키는 집합이다.
 모든 변 에 대하여, 와 접하는 가 존재한다.
최소 꼭짓점 덮개는 크기가 최소인 꼭짓점 덮개이다.

쾨니그의 정리에 따르면, 이분 그래프 의 최대 부합  및 최소 꼭짓점 덮개 에 대하여,

이다.

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

역사 
헝가리의 수학자 쾨니그 데네시가 1931년에 증명하였다.

참고 문헌

외부 링크 
 
 

그래프 이론 정리
조합적 집합론