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

내용 삭제됨 내용 추가됨

인라인

2021년 2월 7일 (일) 22:00 판

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

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

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

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

|M|=|C|

이다.

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

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

↑ Kőnig Dénes (1931). “Gráfok és mátrixok”. 《Matematikai és Fizikai Lapok》 (헝가리어) 38: 116–119. Zbl 0003.32803.
↑ 윤영진 (2007). 《새로운 조합수학》. 교우사. ISBN 978-89-8172-379-8.

“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.

@@ 17번째 줄: / 17번째 줄: @@
 == 역사 ==
 [[헝가리]]의 수학자 [[쾨니그 데네시]]가 [[1931년]]에 증명하였다.<ref>{{저널 인용
-  | 저자 = Kőnig Dénes  | 저자고리=쾨니그 데네시 | 제목 = Gráfok és mátrixok
+  | 저자 = Kőnig Dénes  | 저자링크=쾨니그 데네시 | 제목 = Gráfok és mátrixok
   | journal = Matematikai és Fizikai Lapok
   | volume = 38