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

15 바이트 제거됨 ,  11년 전
잔글
편집 요약 없음
잔글 (로봇이 더함: is:Tvíhlutanet)
잔글
[[그림:Complete bipartite graph K3,2.svg|thumb|200px|이분 그래프의 예]]
 
[[수학]]의 [[그래프 이론]]에서 '''이분 그래프'''(bipartite graph)란 [[그래프 이론]]에서 모든 변이 X에 있는 꼭지점과 Y의 꼭지점을 잇는 형태로 되도록 꼭지점의 집합을 두 개의 부분집합 X, Y로 나눌 수 있는 그래프이다.
다르게 표현하자면, 그래프의 꼭지점을 빨강과 파랑으로 색칠하되, 모든 변이 빨강과 파랑 꼭지점을 포함하도록 색칠할 수 있는 경우 이분 그래프라고 한다.
같은 말로 [[색칠수]] χ(G)가 2이하인 경우이다.
 
== 이분 그래프의 특성 ==
홀수 길이의 회로가 이분 그래프가 아니라는 점은 쉽게 증명할 수 있다. 아울러 다음과 같은 더 강력한 정리가 쉽게 증명된다. 그래프가 이분그래프일 필요충분조건은 홀수 길이의 회로가 없다는 것이다.
:그래프가 이분그래프일 필요충분조건은 홀수 길이의 회로가 없다는 것이다.
 
== 이분 그래프인지 확인하는 [[알고리즘]] ==