이분 그래프

이분 그래프(二分graph, bipartite graph)는 그래프 이론에서 정점 집합을 두 부분으로 나눌 수 있으며, 같은 부분에 속한 정점끼리는 간선으로 연결되지 않는 그래프이다.

1 정의

이분 그래프는 정점 집합 V를 두 개의 서로소 부분 집합 U와 W로 분할할 수 있으며, 모든 간선은 U와 W를 잇는 방식으로만 존재하는 그래프이다. 즉, 간선은 같은 집합에 속한 정점끼리 연결되지 않는다. 이러한 그래프는 흔히 G = (U ∪ W, E)로 표기된다.

2 성질

• 사이클이 존재하더라도 홀수 길이의 사이클은 존재하지 않으며, 이는 이분 그래프의 필요충분조건이다.
• 모든 트리는 이분 그래프이다.
• 이분 그래프는 2-색칠 가능하다. 즉, 인접 정점끼리 서로 다른 두 색으로 색칠할 수 있다.
• 최대 매칭, 최소 커버 문제 등에 자주 응용되며, 헝가리안 알고리즘 등에서 중요한 구조로 등장한다.
• 완전 이분 그래프는 U와 W 사이의 모든 가능한 간선을 포함하는 이분 그래프이며, K_{m,n}으로 표기된다.

3 예시

• K_{3,2}: 정점 집합을 각각 3개와 2개로 나누고, 각 정점 쌍을 모두 연결한 완전 이분 그래프.
• 나무 구조: 루트가 있는 트리 구조는 항상 이분 그래프이다.
• 정점이 짝수 개인 사이클(C2n): 이분 그래프의 성질을 만족한다.

4 응용

• 작업 배정 문제: 작업과 작업자를 각각의 집합으로 두고 적절히 매칭을 구성할 때 사용됨.
• 사회 연결망 분석: 두 이질적 객체(예: 사용자와 아이템) 간의 관계를 모델링하는 데 사용된다.
• 컴파일러 최적화: 간섭 그래프가 이분 그래프인 경우 최소 색칠이 가능하여 레지스터 할당 최적화에 기여한다.

5 같이 보기

• 그래프 이론
• 정규 그래프
• 완전 그래프
• 사이클 그래프
• 그래프 색칠 문제

6 참고 문헌

• West, D. B. (2001). *Introduction to Graph Theory* (2nd ed.). Prentice Hall.