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

내용 삭제됨 내용 추가됨

인라인

2014년 12월 2일 (화) 09:11 판

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

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

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

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

|M|=|C|

이다.

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

집합족 ${\mathcal {T}}$ 의 모든 원소가 유한집합이라고 하자. 홀 결혼 정리에 따르면, 다음 두 조건이 서로 동치이다.^[1]^:289

(결혼 조건 영어: marriage condition) 모든 ${\mathcal {U}}\subset {\mathcal {T}}$ 에 대하여, $\textstyle |{\mathcal {U}}|\leq \left|\bigcup {\mathcal {U}}\right|$
(횡단의 존재) 다음 조건들을 만족시키는 순서쌍 $(S,f)$ $(S,f)$ 가 존재한다. 이러한 순서쌍을 횡단(橫斷, 영어: transversal) 또는 변별 대표원계(辨別代表元系, 영어: system of distinct representatives)라고 한다.
- $S\subset \bigcup {\mathcal {T}}$ 는 집합이다.
- $f\colon S\to T$ 는 전단사 함수이다.
- 모든 $s\in S$ 에 대하여 $s\in f(s)$ 이다.

횡단의 존재가 결혼 조건을 함의한다는 것은 자명하므로, 홀 결혼 정리에서 실제로 증명할 것은 결혼 조건이 횡단의 존재를 함의한다는 것이다.

"결혼 조건"의 어원은 다음과 같다. $n$ 명의 미혼 이성애자 남성과 $n$ 명의 미혼 이성애자 여성이 있다고 하자. 이들이 배우자에 대하여 다음 조건들을 요구한다고 하자.

복혼 없이, 모든 사람들이 결혼할 는수 있는 방법은 ${\mathcal {T}}=\{T_{i}\}_{i=1,\dots ,n}$ 의 횡단을 정의한다. 이 경우, 홀 결혼 정리는 모든 사람들이 결혼할 수 있는지 확인할 수 있는 필요충분조건을 제공한다.^[1]^:289

헝가리의 수학자 쾨니그 데네시(헝가리어: Kőnig Dénes)가 1931년에 증명하였다.^[2]^[1]^:289 영국의 필립 홀(영어: Philip Hall)이 쾨니그의 정리와 동치인 홀 결혼 정리를 1935년에 증명하였다.^[3]

↑ ^가 ^나 ^다 윤영진 (2007). 《새로운 조합수학》. 교우사. ISBN 978-89-8172-379-8.
↑ Kőnig Dénes (1931). “Gráfok és mátrixok”. 《Matematikai és Fizikai Lapok》 38: 116–119. Zbl 0003.32803.
↑ Hall, Philip (1935). “On representatives of subsets”. 《Journal of the London Mathematical Society》 10 (1): 26–30. doi:10.1112/jlms/s1-10.37.26. JFM 61.0067.01. Zbl 0010.34503.

“König theorem”. 《Encyclopedia of Mathematics》 (영어). Springer-Verlag. 2001. ISBN 978-1-55608-010-4.
“Combinatorial analysis”. 《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.
Weisstein, Eric Wolfgang. “Marriage theorem”. 《Wolfram MathWorld》 (영어). Wolfram Research.

@@ 6번째 줄: / 6번째 줄: @@
 어떤 그래프 <math>\Gamma</math>의 '''꼭지점 덮개''' <math>C\subset V(\Gamma)</math>는 다음을 만족시키는 집합이다.
 * 모든 변 <math>e\in E(\Gamma)</math>에 대하여, <math>e</math>와 접하는 <math>c\in C</math>가 존재한다.
-<math>\Gamma</math>의 꼭지점 덮개들의 집합은 포함 관계에 따라서 [[부분 순서 집합]]을 이루며, '''최소 꼭지점 덮개'''는 이 부분 순서에 대한 최소 꼭지점 덮개'''이다.
+'''최소 꼭지점 덮개'''는 크기가 최소인 꼭지점 덮개이다.
 '''쾨니그의 정리'''에 따르면, [[이분 그래프]] <math>\Gamma</math>의 최대 매칭 <math>M\subset E(\Gamma)</math> 및 최소 꼭지점 덮개 <math>C\subset V(\Gamma)</math>에 대하여,