이분 그래프 편집하기

이분 그래프(二分graph, bipartite graph)는 그래프 이론에서 정점 집합을 두 부분으로 나눌 수 있으며, 같은 부분에 속한 정점끼리는 간선으로 연결되지 않는 그래프이다.
==정의==
이분 그래프는 정점 집합 V를 두 개의 서로소 부분 집합 U와 W로 분할할 수 있으며, 모든 간선은 U와 W를 잇는 방식으로만 존재하는 그래프이다. 즉, 간선은 같은 집합에 속한 정점끼리 연결되지 않는다. 이러한 그래프는 흔히 G = (U ∪ W, E)로 표기된다.
==성질==
*사이클이 존재하더라도 홀수 길이의 사이클은 존재하지 않으며, 이는 이분 그래프의 필요충분조건이다.
*모든 트리는 이분 그래프이다.
*이분 그래프는 2-색칠 가능하다. 즉, 인접 정점끼리 서로 다른 두 색으로 색칠할 수 있다.
*최대 매칭, 최소 커버 문제 등에 자주 응용되며, 헝가리안 알고리즘 등에서 중요한 구조로 등장한다.
*완전 이분 그래프는 U와 W 사이의 모든 가능한 간선을 포함하는 이분 그래프이며, K_{m,n}으로 표기된다.
==예시==
*K_{3,2}: 정점 집합을 각각 3개와 2개로 나누고, 각 정점 쌍을 모두 연결한 완전 이분 그래프.
*나무 구조: 루트가 있는 트리 구조는 항상 이분 그래프이다.
*정점이 짝수 개인 사이클(C2n): 이분 그래프의 성질을 만족한다.
==응용==
*작업 배정 문제: 작업과 작업자를 각각의 집합으로 두고 적절히 매칭을 구성할 때 사용됨.
*사회 연결망 분석: 두 이질적 객체(예: 사용자와 아이템) 간의 관계를 모델링하는 데 사용된다.
*컴파일러 최적화: 간섭 그래프가 이분 그래프인 경우 최소 색칠이 가능하여 레지스터 할당 최적화에 기여한다.
==같이 보기==
*[[그래프 이론]]
*[[정규 그래프]]
*[[완전 그래프]]
*[[사이클 그래프]]
*[[그래프 색칠 문제]]
==참고 문헌==
*West, D. B. (2001). *Introduction to Graph Theory* (2nd ed.). Prentice Hall.
==각주==
[[분류:그래프]]
[[분류:그래프 이론]]