본문으로 이동

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

33 바이트 추가됨 ,  10개월 전
잔글
+분류:이분 그래프; 예쁘게 바꿈
잔글 (→‎성질)
잔글 (+분류:이분 그래프; 예쁘게 바꿈)
임의의 유한 [[그래프]] <math>\Gamma</math>에 대하여 다음 두 조건이 서로 [[동치]]이다.
* 이분 그래프이다.
* 홀수 길이의 [[순환 (그래프 이론)|순환]]이 존재하지 않는다.
특히, 예를 들어 홀수 길이의 [[순환 그래프]]는 이분 그래프가 될 수 없다.
 
 
=== 쾨니그 정리 ===
[[파일:Koenigs-theorem-graph.svg|섬네일|right오른쪽|쾨니그 정리에 따르면, 이분 그래프에서, [[최대 부합]]의 변(청색) 수는 최소 꼭짓점 덮개의 꼭짓점(적색) 수와 같다.]]
'''쾨니그 정리'''(Kőnig定理, {{llang|en|Kőnig’s theorem}})에 따르면, 이분 그래프의 경우 대한 최소 꼭짓점 덮개 문제와 [[최대 부합]] 문제가 서로 [[동치]]이다.
 
* {{nlab|id=bipartite graph|title=Bipartite graph}}
 
[[분류:이분 그래프| ]]
[[분류:그래프 이론]]

편집

1,449,175