2017년 10월 9일 (월) 11:44 판 편집 TedBot (토론 \| 기여) 봇, 업로더 2,771,231 편집 잔글 봇: 틀 이름 및 스타일 정리 ← 이전 편집		2018년 9월 15일 (토) 17:32 판 편집 편집 취소 TedBot (토론 \| 기여) 봇, 업로더 2,771,231 편집 잔글 봇: 틀 이름 및 스타일 정리 다음 편집 →
1번째 줄: {{다른 뜻 넘어옴\|쾨니그의 정리\|무한 그래프에 대한 정리\|쾨니그 보조정리}} {{다른 뜻 넘어옴\|쾨니그의 정리\|[[기수 (수학)\|기수]]에 대한 정리\|쾨니그의 정리 (집합론)}} [[파일:Complete bipartite graph K3,2.svg\|~~thumb~~섬네일\|200px\|이분 그래프의 예]] [[파일:Complete bipartite graph K32-RG001.svg\|~~thumb~~섬네일\|위 그래프의 [[그래프 색칠]]]] [[파일:Complete bipartite graph K32-001.svg\|~~thumb~~섬네일\|2색변 이분 그래프의 예]] [[그래프 이론]]에서, '''이분 그래프'''(二分graph, {{llang\|en\|bipartite graph}})란 모든 꼭짓점을 빨강과 파랑으로 색칠하되, 모든 변이 빨강과 파랑 꼭짓점을 포함하도록 색칠할 수 있는 [[그래프]]이다. 25번째 줄: === 쾨니그 정리 === [[파일:Koenigs-theorem-graph.svg\|~~thumb~~섬네일\|right\|쾨니그 정리에 따르면, 이분 그래프에서, [[최대 부합]]의 변(청색) 수는 최소 꼭짓점 덮개의 꼭짓점(적색) 수와 같다.]] '''쾨니그 정리'''(Kőnig定理, {{llang\|en\|Kőnig’s theorem}})에 따르면, 이분 그래프의 경우 대한 최소 꼭짓점 덮개 문제와 [[최대 부합]] 문제가 서로 [[동치]]이다.

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