쾨니그의 정리: 두 판 사이의 차이
내용 삭제됨 내용 추가됨
이분 그래프에 대한 넘겨주기를 제거함 태그: 넘겨주기 제거 |
잔글 봇: 문단 이름 변경 (바깥 고리 → 외부 링크) |
||
| 26번째 줄: | 26번째 줄: | ||
{{각주}} |
{{각주}} |
||
== |
== 외부 링크 == |
||
* {{eom|title=König theorem}} |
* {{eom|title=König theorem}} |
||
* {{매스월드|id=KoenigsLineColoringTheorem|title=König's Line Coloring Theorem}} |
* {{매스월드|id=KoenigsLineColoringTheorem|title=König's Line Coloring Theorem}} |
||
2021년 1월 22일 (금) 14:26 판
이 문서는 그래프의 꼭짓점 덮개와 최대 부합에 관한 것입니다. 무한 그래프에 대한 정리에 대해서는 쾨니그 보조정리 문서를, 기수에 대한 정리에 대해서는 쾨니그의 정리 (집합론) 문서를 참고하십시오.그래프 이론 및 조합론에서, 쾨니그의 정리(Kőnig의定理, 영어: Kőnig’s theorem)는 이분 그래프에 대한 최소 꼭짓점 덮개 문제와 최대 부합 문제가 서로 동치라는 정리다.
정의
어떤 그래프 의 꼭짓점 덮개(영어: vertex cover) 는 다음을 만족시키는 집합이다.
- 모든 변 에 대하여, 와 접하는 가 존재한다.
최소 꼭짓점 덮개는 크기가 최소인 꼭짓점 덮개이다.
쾨니그의 정리에 따르면, 이분 그래프 의 최대 부합 및 최소 꼭짓점 덮개 에 대하여,
이다.
조합적 집합론에서는 쾨니그의 정리를 일반화하는 홀 결혼 정리가 존재한다. 쾨니그의 정리와 홀의 정리는 서로 동치이며, 이들은 딜워스의 정리와도 동치이다.
역사
헝가리의 수학자 쾨니그 데네시가 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.