[CE] Bipartite Graph (이분그래프)

Bipartite Graph

Node (or Vertex)들을
edges의 구성에 따라
2개의 집합으로 나눌 수 있는 Graph.

 

Nodes의 전체 set이 2개의 subset으로 나누어지며, 같은 subset에 속하는 node들 간에는 edge가 존재하지 않음.

 

Graph에 대한 건 다음 URL을 참고:

https://dsaint31.me/mkdocs_site/ML/ch08/datastructure_graph/

BME228

 

---

Definition of Bipartite Graph

Bipartite Graph $G=(N,E)$는 다음을 만족하는 Graph임.

• Node set $N$은 subset $X,Y$로 나누어짐.
• 모든 edget $e\in E$는 $X$와 $Y$의 nodes를 연결하여 $e=(x,y), \text{ where } x\in X y \in Y$가 성립.

https://www.mdpi.com/2227-7390/8/12/2132

---

Applications

Job Assignment Problem (=Bipartite Matching)

Bipartite Graph의 두 subset $X,Y$간의 matching of nodes 를 구하는 문제.

$X$의 각 nodes는 최소한 하나의 $Y$의 nodes와 edge로 연결되며 그 역도 성립.

---

Hungarian Algorithm

최적의 자원배치에 사용되는 알고리즘으로 minimum cost matching을 Bipartite Graph에서 찾아냄.

Object Tracking등에서 최적의 matching pairs를 찾는데(=Data Association)에 사용됨.

edge가 연결된 경우를 cost 1로 할당하고 연결되니 않은 경우 무한대의 cost를 할당할 경우, maximum matching을 찾는데에도 사용가능함.

2024.08.06 - [Programming/DIP] - [CV] Hungarian Algorithm: Matching on the Bipartite Graph

[CV] Hungarian Algorithm: Matching on the Bipartite Graph

---

Maximum Matching

Bipartite Graph에서 최대한 많은 matching을 찾는 문제.

SNS 나 파티 등에서 최대한 많은 사용자간에 연결(or 만남)이 이루어지는 방법을 제시.

네트워크에서 최대한 많은 기기간에 연결이 이루어지게 하거나 Distributed Computing에서 최대한 많은 자원을 작업에 연결하는 문제등에 사용됨.

(최소의 resouce를 최대의 작업에 배치)

---

Bipartite Graph 판정

Graph에서 연결된 node의 수(Connected Component)를 구하는 알고리즘과 유사한 방식을 사용함.
모든 Node를 방문하며 edge로 연결된 nodes를 검사하기 때문에 time complexity는 $O(V+E)$임.

즉, Graph Travesal Algorithm (serach algorithm)과 같은 time complexity이며, DFS와 BFS로 판정가능함.

 

Bipartite graph인지 판별하기 위해, BFS(너비 우선 탐색)나 DFS(깊이 우선 탐색)를 사용하여 graph의 모든 nodes를 방문하면서 색칠(subset 할당)하는 것을 수행함으로써 Bipartite graph의 성질을 위반하는지를 확인한다.

 

Bipartite Graph의 성질:
edge로 연결될 서로 인접한 nodes는
같은 subset이면 안됨
(같은 색으로 칠해지면 안됨)

 

https://gmlwjd9405.github.io/2018/08/23/algorithm-bipartite-graph.html

 

알고리즘은 다음과 같음:

1. subset(color로 표시) 초기화:
   • 각 node의 subset을 저장할 list나 map을 초기화.
   • 두 가지 subset을 각각 0과 1로 표시.
   • 처음에는 모든 node가 자신이 속한 subset이 할당되지 않은 상태임.
2. Traversal 시작:
   • 방문하지 않은 각 nodes에 대해 BFS나 DFS를 수행.
   • 이는 연결되지 않은 nodes에 대해서도 수행되어야 함.
3. Subset assignment(=coloring) and Traversal:
   • Start node에 임의의 subset(예: 0)을 할당.
   • BFS나 DFS를 사용하여 그래프를 탐색.
   • 각 node에 대해,  edge로 연결된 인접한 모든 node를 현재 node와 다른 subset으로 할당.
4. 이분 그래프 여부 확인:
   • 인접한 subset이 이미 현재 node와 동일한 subset으로 할당되어 있다면, Bipartite Graph가 아니라고 결론내리고 탐색 종료.
   • 그래프 전체 nodes를 탐색해도 위와 같은 사례가 없다면 Bipartite Graph 결론내림.

---

관련자료

https://gmlwjd9405.github.io/2018/08/15/algorithm-bfs.html

[알고리즘] 너비 우선 탐색(BFS)이란 - Heee's Development Blog

 

https://gmlwjd9405.github.io/2018/08/14/algorithm-dfs.html

[알고리즘] 깊이 우선 탐색(DFS)이란 - Heee's Development Blog

 

---