Kuhn's Algorithm for Maximum Bipartite Matching

Kuhn's Algorithm for Maximum Bipartite Matching - Algorithms for Competitive Programming

 

분명 그래프 이론에서 배웠을 텐데 기억이 사라졌다.

 

 

먼저 용어들을 정의하자.

 

- 그래프 안에서 서로 인접하지 않은 edge들의 set을 Matching이라 한다.

 

- Matching의 cardinality는 set에 속해있는 edge들의 개수이다.

 

- 주어진 그래프에서 cardinality가 가장 큰 matching을 maximum matching이라 한다.

 

- matching의 edge에 속해있는 모든 vertex들을 이 matching에 saturated 되어있다고 한다.

 

- \( k \)길이의 path는 edge \( k \)개를 가지고 있는 simple path를 뜻한다.

 

- alternating path는 edge가 번갈아가며 matching에 속했다 속하지 않았다 하는 path를 뜻한다.

 

- augmenting path는 첫 번째 vertex와 마지막 vertex가 unsaturated인 alternating path를 뜻한다.

 

- For sets \( A \) and \( B \), \( A \bigoplus B \) = ( \( A \cup B \) ) - ( \( A \cap B \) )

 

 

Berge's lemma

 

matching \( M \)이 maximum이다 <=> matching \( M \)에 augmenting path가 없다.

 

=>

 

matching \( M \)이 maximum이라 하자.

 

만약 \( M \)에 대해, augmenting path가 있다면 짝수번째 edge들을 \( M \)의 원소로 선택하는 대신, 홀수번째 edge들을 \( M \)의 원소로 선택하여 \( M \)의 cardinality를 1 늘릴 수 있다.

 

하지만 \( M \)은 maximum matching이기 때문에 cardinality를 늘리는 것은 불가능하며 따라서 augmenting path는 없다.

 

<=

 

Matching \( M \)에 augmenting path가 없다 가정하자.

 

matching \( M' \)를 matching \( M \)보다 cardinality가 더 큰 matching이라고 하자.

 

\( M \bigoplus M' \)으로 새로운 그래프 \( Q \)를 만들자.

 

\( Q \)의 vertex들이 속해있는 connected component들은 세 가지 중 하나의 상태이다.

 

- an isolated vertex

 

- \( M \)에 속해있는 edge와 \( M' \)에 속해있는 edge가 번갈아 나오는 simple path

 

- \( M \)에 속해있는 edge와 \( M' \)에 속해있는 edge가 번갈아 나오는 cycle

 

matching \( M' \)의 cardinality가 \( M \)보다 더 크기 때문에 \( Q \)에 속한 \( M' \)의 edge 개수도 더 커야한다.

 

cycle 같은 경우 무조건 edge의 개수가 짝수이어야 하기에 simple path를 살펴보자.

 

\( Q \)안에 \( M' \)의 edge 개수가 더 많아야 하기에 pinhole's principle에 따라 처음과 마지막 edge가 \( M' \)에 속하는 홀수개의 edge를 가진 simple path가 적어도 하나 존재해야 한다.

 

하지만 그러한 simple path는 Matching \( M \)의 augmenting path이다.

 

따라서 \( M' \)은 존재할 수 없으므로 \( M \)은 maximum이다.

 

 

Kuhn's algorithm

 

 

Kuhn's algorithm은 Berge's lemma를 이용한다.

 

주어진 그래프 \( G \)에 대해 빈 matching에서 시작하여 현재의 matching에 대해 augmenting path를 계속해서 찾는다.

 

만약 augmenting path가 더 이상 존재하지 않다면 maximum matching을 구한 것이다.

 

 

 

그 밖에,

 

- Bipartite graph에서 maximum matching의 cardinality는 minimum vertex cover과 같다.

 

- maximum independent set은 minimum vertex cover의 complement와 같다.