Bipartite graph는 그래프 이론에서 사용되는 특별한 유형의 그래프이다. Bipartite graph는 정점들을 두 개의 독립된 집합으로 분할할 수 있는 그래프를 말한다. 즉, 그래프의 모든 간선은 한 집합의 정점과 다른 집합의 정점을 연결한다.
예를 들어, V1과 V2라는 두 개의 정점 집합으로 구성된 Bipartite graph를 생각해보겠다. 간선은 V1의 정점과 V2의 정점을 연결하며, V1에 속한 정점은 V2에 속한 정점과만 연결되고 V2에 속한 정점은 V1에 속한 정점과만 연결된다. Bipartite graph에서 같은 집합 내의 정점들 사이에는 간선이 존재하지 않는다.
Bipartite graph는 다양한 분야에서 활용될 수 있다. 예를 들면, 작업자와 작업의 할당, 학생과 강의의 할당, 국가와 자원의 할당 등 다양한 할당 문제를 모델링할 때 사용될 수 있다. 또한, 그래프 이론에서의 매칭 문제와 관련이 있다. Bipartite graph에서 최대 매칭(Maximum Matching)이나 완전 매칭(Perfect Matching)을 찾는 문제가 중요한 예시이다.
간단히 말하면, Bipartite graph는 두 개의 독립된 집합으로 구성되며, 집합 내의 정점들은 다른 집합의 정점들과만 연결되는 그래프이다.
