백과

그래프 G=(V, E)에 있어서 노드의 집합 V를 2개의 부분집합 V₁, V₂로 분할(V₁∪V₂=V, V₁∩V₂=Φ)해서 G의 어느 가지도 한쪽 끝점이 V₁에 속하고, 다른 쪽 끝점이 V₂에 속하게 될 때 G를 2부 그래프라고 한다. G는 G=(V₁, V₂, E) 라고도 쓸 수 있다.

그림 (a)의 그래프는 그림 (b)와 같이 V를 둘로 분할할 수 있기 때문에 2부 그래프이다. 무향 그래프 G가 2부 그래프가 되기 위한 필요충분 조건은 G가 홀수 길이의 단순 폐로(경로 참고)를 포함하지 말아야 한다. 또는 G의 채색수가 2 이하일 경우라 해도 좋다. G=V₁,V₂, E)에 있어서 V₁의 어느 노드나 V₂의 모든 노드와 인접하고 있을 때 G를 완전 2부 그래프(complete bipartite graph)라 하고 K_{n, m}라고 적는다. 단 |V₁|=n, |V₂|=m이다. 〈참조어〉 케니구에게르발리의 정리, 할당 문제, 수송 문제, 홀의 정리, 완전 2부 그래프