최근 수정: 6년 전
1. 개요
Bipartite Graph
그래프를 다음과 같이 A와 B로 나눌 수 있다면 이분 그래프라고 한다.
쉽게 말해 정점 덩어리들을 두 묶음으로 나눌 수 있으면 이분 그래프이다. 초등학교 때 왼쪽과 오른쪽을 알맞게 연결하는 문제도 이분 그래프이었다. 그 당시에는 몰랐겠지만...
또한, 네트워크 플로우 중에서 이분 그래프 형태의 문제를 이분 매칭이라고 한다. 자세한 건 해당 문서 참고.