이분 매칭 (Bipartite graph)

이분 매칭에 앞서 이분 그래프의 정의부터 알아보자. 이분 그래프란 아래 조건을 만족하는 그래프이다.

• 노드를 두 그룹으로 나누는데
• 각 그룹이 간선을 공유하지 않는 그래프

예를 들면 이런 그래프가 있다.

 

이분 매칭

이분 매칭이란 이분 그래프에서 서로 다른 그룹에 속한 노드를 매칭 할 때, 최대한 많이 매칭 하는 것을 말한다. 이때 하나의 노드는 최대 하나의 간선만 가지도록 구성되어야 한다.

 

예제 그래프를 가지고 이분 매칭을 하는 방법을 하나씩 살펴보자.

예제

1. 초기 그래프

왼쪽 그룹에서 오른쪽 그룹으로 방향 그래프를 만든다

 

2. 첫번째 매칭

위 그래프에서 이분 매칭을 하기 위해 먼저 빨간 노드를 차례대로 순회하면서 파란 노드랑 연결시켜주는 작업을 시작한다.

한번에 찾았다!

 

2-1. 첫번째 매칭 후처리

첫 번째 빨간 노드에서 그래프를 순회하다가 매칭 할 수 있는 파란 노드를 만났으므로 매칭(체크)시킨다.
이때 단순히 체크만 하는 것이 아니라 지금까지 달려온 경로를 전부 뒤집어 역간선으로 만든다. 이 경우에는 한 번에 찾았기 때문에 하나의 간선만 뒤집으면 된다.

파판 노드를 체크한 후 왔던 경로를 뒤집는다

 

3. 두번째 매칭

두번째 빨간 노드에서 출발해서 다시 매칭 가능한 파란 노드를 찾아 탐색한다. 첫 번째 파란 노드는 이미 매칭이 되었기 때문에 더 탐색을 진행한다. 이 전에 뒤집었던 간선이 마침 있으니 이쪽으로도 탐색을 진행하다가 아직 체크되지 않은 두 번째 파란 노드를 발견한다.

 

3-1. 두번째 매칭 후처리

발견한 파란 노드를 매칭(체크)시키고 지금까지 온 경로를 모두 뒤집는다.

 

4. 세번째 매칭

마지막으로 세 번째 빨간 노드에서 출발해서 매칭 가능한 파란 노드를 찾는다.
역시 파란색 두번째 노드는 이미 매칭 되었기 때문에 통과하고 세 번째 파란색 노드를 발견한다.

 

 

4-1. 세번째 매칭 후처리

발견한 파란 노드를 매칭(체크)시키고 지금까지 온 경로를 모두 뒤집는다. 

마지막 빨간색 노드까지 탐색을 마쳤으므로 종료한다.

 

5. 최종 상태

 

 

---

 

단순히 매칭할 수 있는 노드를 찾아 매칭 하고, 간선을 뒤집는 행동을 반복해서 최종 상태 그래프를얻었다.
최종 상태의 그래프에서는 몇 개가 매칭 되었는지 뿐만 아니라 역간선을 통해 파란색 노드가 어느 빨간색 노드와 연결되었는지도 확인할 수 있다.

 

이 단순한 반복을 좀 더 익숙한 그래프로 바꿔 일반화해볼 수 있다.

 

일반화

1. S와 E를 추가하고 각 그룹에 있는 모든 정점과 연결
2. S에서 E까지 길이 있는지 탐색
3. 발견하면 경로를 뒤집어줌
4. S에서 E까지 가는 길이 없을 때까지 2-3 반복

 

이분 매칭은 최대한 매칭 시킨다는 그 자체로도 의미가 있지만 최소 정점 커버(vertex cover) 문제로도 해석할 수 있다.
최소 정점 커버는 일반적으로 그래프에서 NP-complete지만 이분 그래프라는 특수한 형태에서는 최대 매칭과 같은 의미를 가진다.