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

2,248 바이트 제거됨 ,  4년 전
짧은 글을 본문인 이분 그래프로 합침
(→‎역사: 봇: 인용 틀 변수 이름 수정)
(짧은 글을 본문인 이분 그래프로 합침)
태그: 넘겨주기 생성
#넘겨주기 [[이분 그래프]]
{{두 다른 뜻|[[그래프]]의 꼭짓점 덮개와 [[최대 부합]]|무한 그래프에 대한 정리|쾨니그 보조정리|[[기수 (수학)|기수]]에 대한 정리|쾨니그의 정리 (집합론)}}
[[그래프 이론]] 및 [[조합론]]에서, '''쾨니그의 정리'''(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>e\in E(\Gamma)</math>에 대하여, <math>e</math>와 접하는 <math>c\in C</math>가 존재한다.
'''최소 꼭짓점 덮개'''는 크기가 최소인 꼭짓점 덮개이다.
 
'''쾨니그의 정리'''에 따르면, [[이분 그래프]] <math>\Gamma</math>의 [[최대 부합]] <math>M\subset E(\Gamma)</math> 및 최소 꼭짓점 덮개 <math>C\subset V(\Gamma)</math>에 대하여,
:<math>|M|=|C|</math>
이다.
 
조합적 집합론에서는 쾨니그의 정리를 일반화하는 [[홀 결혼 정리]]가 존재한다. 쾨니그의 정리와 홀의 정리는 서로 [[동치]]이며, 이들은 [[딜워스의 정리]]와도 동치이다.
 
== 역사 ==
[[헝가리]]의 수학자 [[쾨니그 데네시]]가 [[1931년]]에 증명하였다.<ref>{{저널 인용
| 저자 = Kőnig Dénes | 저자고리=쾨니그 데네시 | 제목 = Gráfok és mátrixok
| journal = Matematikai és Fizikai Lapok
| volume = 38
| 날짜 = 1931
| pages = 116–119 | zbl = 0003.32803 | 언어=hu}}</ref><ref name="윤영진">{{서적 인용|저자=윤영진|제목=새로운 조합수학|출판사=교우사|날짜=2007|isbn=978-89-8172-379-8|url=http://www.kyowoo.co.kr/02_sub/view.php?p_idx=334|언어=ko}}</ref>{{rp|289}}
 
== 참고 문헌 ==
{{각주}}
 
== 바깥 고리 ==
* {{eom|title=König theorem}}
* {{매스월드|id=KoenigsLineColoringTheorem|title=König's Line Coloring Theorem}}
 
[[분류:그래프 이론]]
[[분류:조합적 집합론]]
[[분류:수학 정리]]