Chapter 25 : Matching in Bipartite Graphs

Ford-Fullkerson 알고리즘을 통해 maximum bipartite matching을 찾는데

시간 복잡도는 O(VE)가 걸렸다.

우리는 Hopcroft-Karp 알고리즘을 통해 O(√V * E)의 시간복잡도를 알아볼것이다.

 

2~5 번째 줄은 O(√V) 만큼 반복

3번째 줄은 O(E) 만큼 반복

 

먼저 maximal set of vertex-disjoint shortest M-augmenting path를 찾는 방법을 볼것이다.

phase 1 : undirected 그래프인 G를 directed 버전인 GM을 형성한다.

phase 2 : bfs을 통해 GM에서 directed 비순환 그래프 H를 생성한다.

phase 3 : H의 전치 HT에서 dfs를 실행함으로써 maximal set of vertex-disjoint shortest M-augmenting path

를 찾는다.

directed 그래프의 전치는 각 edge의 방향을 반대로 한다.

H가 비순환이기 때문에 HT도 비순환이다.

 

Phase 1

matching M이 주어지면, 우리는 M-augmenting path P를 L의 matching이 되지않은 vertex에서

시작해 홀수개의 edge를 가로질러 R의 matching이 되지않는 vertex에서 끝나는 것으로 생각할 수 있다.

L에서 R로 가로지른 P의 edge는 E - M에 속해야 하고, R에서 L로 가로지른 P의 edge는 M에 속해야 한다.

따라서 우리는 다음과 같이 directed그래프 GM을 생성한다.

Phase 2

각 layer는 L의 vertex들만 포함하거나 R의 vertex들만 포함하여 layer간에 교대로 포함된다.

vertex가 존재하는 layer은 L에서 matching이 되지않은 vertex로 부터 GM에서 해당 vertex의 

최소 bfs거리에 의해 주어진다.

L의 vertex들은 짝수 layer에 나타나고, R의 vertex들은 홀수 layer에서 나타난다.

vertex들의 bfs거리를 결정하려면 GM에서 bfs를 실행하되, L의 matching이 되지않은 vertex에서

시작해야 한다.

layer 0의 vertex에서 later q의 matching이 되지않은 vertex까지의 H의 모든 경로는 

원래의 bipartite graph G의 가장 짧은 M-augmenting path에 해당한다.

게다가, G의 모든 shortest M-augmenting path는 H에 존재한다.

 

Phase 3

이 단계는 maximal set of vertex-disjoint shortest M-augmenting path를 식별한다.

우리는 H의 전치 HT를 만드는 것으로 시작한다.

그런 다음 우리는 layer q의 matching되지않은 vertex r에서 layer 0에 도달하거나

또는 모든 path를 다 돌아봤는데도 layer 0에 도달하지 못할 때 까지 dfs를 실행한다.

layer 0의 vertex에 도달하면, predecessor을 따라 거슬러 올라가면 M-augmenting path로 식별한다.

만약 layer 0을 찾지 못하면 더이상 M-augmenting path가 없는것으로 생각한다.

 

위의 그림으로 예를 들면 dfs는 처음에 r1에서 시작한다.

이것은 <(r1, l3), (l3, r3), (r3, l1)> 식별한다.

다음 dfs는 r4에서 시작한다.

이것은 (r4, l3)를 탐색하지만 l3가 이미 discover되기 때문에 (r4, l5)로 간다.

따라서 <(r4, l5), (l5, r7), (r7, l6)> 경로가 식별된다.

다음 dfs는 r6에서 시작한다. 

하지만 layer 0에 도달하지 못하기 때문에 실패한다.

따라서 maximal set of vertex-disjoint shortest M-augmenting path들은 

<(r1, l3), (l3, r3), (r3, l1)> 와 <(r4, l5), (l5, r7), (r7, l6)> 2개의 경로를 포함한다.

 

maximal set은 miximum set이 아니다.

maximum set은 <(r1, l2), (l2, r2), (r2, l1)>, <(r4, l3), (l3, r3), (r3, l4)>, <(r6, l5), (l5, r7), (r7, l6)>이다.

이 알고리즘은 maximum set을 찾는 것이 아니라 maximal set을 찾는 것이다.

 

The Stable-Marriage Problem

n명의 남성과 여성이 선호도를 기반으로 n개의 쌍으로 엮어주는 문제이다.

 

Gale-Shapley Algorithm

일반적으로 남성이 여자에게 프로포즈 하거나 여자가 남자에게 프로포즈 하는 부분이 있지만, 

여기서는 여자가 남자에게 프로포즈 하는 방식이다.

다음과 같은 표가 있다고 하자.

위쪽은 여자이고, 아래쪽은 남자이다.

나열된 순서는 선호도가 높은 순서이다.

1. wanda가 Brent에게 청혼한다. Brent는 free이기 때문에 Wanda와 Brent는 짝이 된다.

2. Emma가 Davis에게 청혼한다. Davis는 free이기 때문에 Emma와 Davis는 짝이 된다.

3. Lacey는 Brent에게 청혼한다. Brent는 Lacey를 더 선호하기 때문에 Brent와 Lacey가 짝이 되고 Wanda는 free가 된다.

4. Karen이 Brent에게 청혼한다. Brant는 Lacey를 더 선호하기 때문에 Brent는 Karen을 거절한다.

5. Karen은 Hank에게 청혼한다. Hank는 free이기 때문에 Karen과 Hank는 짝이 된다.

6. Wanda는 Hank에게 청혼한다. Hank는 Wanda를 더 선호하기 때문에 Wanda와 Hank가 짝이 되고, Karen은 free가 된다.

7. Karen은 Davis에게 청혼한다. Davis는 Karen을 더 선호하기 때문에 Karen과 Davis는 짝이 되고, Emma는 free가 된다.

8. Emma는 Hank에게 청혼한다. Hank는 Wanda를 더 선호하기 때문에 Hank는 Emma를 거절한다.

9. Emma는 Oscar에게 청혼한다. Oscar는 free이기 때문에 Emma와 Oscar는 짝이 된다.

여기 까지 아무도 짝이 안된 사람이 없으므로 알고리즘은 종료된다.

<Wanda-Hank>, <Emma-Oscar>, <Lacey-Brent>, <Karen-Davis> 가 되었다.

 

Gale-Shapley알고리즘은 항상 종료되고 stable matching을 return한다.

 

이 알고리즘은 여러번 반복 해도 결국 결과는 하나로 똑같다.

청혼하는 쪽이 항상 최적의 결과를 가진다.