2017년 4월 18일 (화) 03:44 판 편집 Osteologia (토론 \| 기여) 점검 면제자, 장기인증된 사용자 39,111 편집 잔글 →‎바깥 고리 ← 이전 편집		2017년 4월 18일 (화) 04:09 판 편집 편집 취소 Osteologia (토론 \| 기여) 점검 면제자, 장기인증된 사용자 39,111 편집 편집 요약 없음 다음 편집 →
1번째 줄: {{다른 뜻 넘어옴\|쾨니그의 정리\|무한 그래프에 대한 정리\|쾨니그 보조정리}} {{다른 뜻 넘어옴\|쾨니그의 정리\|[[기수 (수학)\|기수]]에 대한 정리\|쾨니그의 정리 (집합론)}} [[그림:Complete bipartite graph K3,2.svg\|thumb\|200px\|이분 그래프의 예]] [[File:Complete bipartite graph K32-001.svg\|thumb\|2색변 이분 그래프의 예]] [[그래프 이론]]에서, '''이분 그래프'''(二分graph, {{llang\|en\|bipartite graph}})란 모든 변이 X에 있는 꼭짓점과 Y의 꼭짓점을 잇는 형태로 되도록 꼭짓점의 집합을 두 개의 부분집합 X, Y로 나눌 수 있는 그래프이다. 다르게 표현하자면, 그래프의 꼭짓점을 빨강과 파랑으로 색칠하되, 모든 변이 빨강과 파랑 꼭짓점을 포함하도록 색칠할 수 있는 ~~경우 이분 그래프라고 한다~~[[그래프]]이다. == 정의 == 줄 18 ⟶ 20: * 홀수 길이의 [[순환 (그래프 이론)\|순환]]이 존재하지 않는다. 특히, 예를 들어 홀수 길이의 [[순환 그래프]]는 이분 그래프가 될 수 없다. === 쾨니그 정리 === [[파일:Koenigs-theorem-graph.svg\|thumb\|right\|쾨니그 정리에 따르면, 이분 그래프에서, [[최대 부합]]의 변(청색) 수는 최소 꼭짓점 덮개의 꼭짓점(적색) 수와 같다.]] '''쾨니그 정리'''(Kőnig定理, {{llang\|en\|Kőnig’s theorem}})에 따르면, 이분 그래프의 경우 대한 최소 꼭짓점 덮개 문제와 [[최대 부합]] 문제가 서로 [[동치]]이다. 구체적으로, 어떤 [[그래프]] <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>가 존재한다. '''최소 꼭짓점 덮개'''({{llang\|en\|minimal vertex cover}})는 포함 관계에 대하여 [[최소 원소]]인 꼭짓점 덮개이다. '''쾨니그 정리'''에 따르면, 유한 이분 그래프 <math>\Gamma</math>의 [[최대 부합]] <math>M\subset E(\Gamma)</math> 및 최소 꼭짓점 덮개 <math>C\subset V(\Gamma)</math>에 대하여, :<math>\|M\|=\|C\|</math> 이다.<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}} 조합적 집합론에서는 쾨니그 정리를 일반화하는 [[홀 결혼 정리]]가 존재한다. 쾨니그 정리와 홀의 정리 및 [[딜워스의 정리]]는 서로 [[동치]]이다. === 변별 알고리즘 === 줄 24 ⟶ 40: == 예 == 0분 그래프는 공(空)그래프~~, 즉~~ (꼭짓점과 변이 없는 그래프) 밖에 없다. 1분 그래프는 이산 그래프 (즉, 아무런 변이 없는 그래프)와 동치인 개념이다. === 완비 <math>k</math>분 그래프 === 줄 35 ⟶ 51: {{본문\|데생당팡}} [[리만 곡면]]에 대하여, 어떤 유한 [[평면 그래프\|평면]] 이분 그래프를 대응시킬 수 있다. 이를 '''[[데생당팡]]'''이라고 한다. == 역사 == 쾨니그 정리는 [[쾨니그 데네시]]<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>와 에게르바리 예뇌({{llang\|hu\|Egerváry Jenő}}, 1891~1958)가 각자 독자적으로 1931년에 증명하였다. == 참고 문헌 == {{각주}} == 바깥 고리 == * {{eom\|title=Graph, bipartite}} * {{eom\|title=König theorem}} * {{매스월드\|id=BipartiteGraph\|title=Bipartite graph}} * {{매스월드\|id=BicolorableGraph\|title=Bicolorable graph}} * {{매스월드\|id=k-PartiteGraph\|title=''k''-partite graph}} * {{매스월드\|id=k-ColorableGraph\|title=''k''-colorable graph}} * {{매스월드\|id=CompleteBipartiteGraph\|title=Complete bipartite graph}} * {{매스월드\|id=CompleteTripartiteGraph\|title=Complete tripartite graph}} * {{매스월드\|id=CompletekPartiteGraph\|title=Complete ''k''-partite graph}} * {{매스월드\|id=KoenigsLineColoringTheorem\|title=König's Line Coloring Theorem}} * {{매스월드\|id=Koenig-EgevaryTheorem\|title=König-Egeváry Theorem}} ~~== 같이 보기 ==~~ * [[쾨니그의 정리]] [[분류:그래프 이론]]

이분 그래프: 두 판 사이의 차이