이분 매칭(bipartite matching) 알고리즘 공부를 해보면서 이해하기 어려운 부분이 많아 알고리즘과 그 증명을 간략하게만 정리 해두려 한다.

관련 문제 : https://www.acmicpc.net/problem/11375

이분 매칭이란

이분 매칭 알고리즘이란 이분 그래프에서 양 그룹을 매칭하는 방법에 관한 알고리즘이다.

이분 그래프란 모든 꼭짓점을 빨강과 파랑으로 색칠하되, 모든 변이 빨강과 파랑 꼭짓점을 포함하도록 색칠할 수 있는 그래프이다. (위키)

즉 그래프에서 정점을 두 그룹으로 나눴을 때, 같은 그룹 간에 연결된 선이 없으면 이분 그래프이다.

이제 이 두 그룹을 간선으로 연결된 정점끼리만 1:1로 연결하려고 할 때, 최대한 많이 매칭을 성사시키는 것이 최대 이분 매칭 문제이다.

알고리즘

최대 이분 매칭 문제를 위한 알고리즘의 동작을 간단히 살펴본다.

점선은 간선, 실선은 성사된 매칭이라고 할 때, 우선 정점1과 연결된 정점 A, B, D 중 첫 번째로 연결된 정점A와 연결한다.

두 번째로 정점2의 매칭을 시도한다. 하지만 정점2와 연결된 정점A는 이미 매칭이 되어있다. 정점A와 정점1 간의 매칭을 끊은 후, 정점1을 다시 정점B와 매칭한다.

(주황색 선이 새로 이어지는 매칭, 파랑색이 끊어지는 매칭)

매칭 결과는 이렇게 진행 될 것이다. 정점3도 정점B와 정점1의 매칭을 끊은 후, 정점1을 다시 정점D와 매칭시키고, 남은 정점B를 정점3과 매칭한다.

만약 새롭게 이어줄 매칭이 없다면 매칭을 끊지 않고 다음 순서의 정점으로 넘어간다.

이를 반복하는 것으로 가장 많이 매칭이 성사되는 조합을 찾을 수 있다.

Augmenting Path

알고리즘의 각 단계에서 새로운 정점을 매칭 시키고, 기존 정점과의 매칭을 끊고, 매칭이 끊어진 정점을 다른 정점과 매칭시키고, 그 다른 정점과 원래 연결되었던 기존 정점과의 .... 의 동작이 반복된다.

이런 새로운 연결 - 기존 연결 끊기 - 새로운 연결 - ... - 기존 연결 끊기 - 새로운 연결의 경로를 Augmenting Path라고 한다. (기존 연결을 끊지 않고 새롭게 연결만 하는 것도 물론 포함된다.)

단계마다 새로운 augmenting path를 찾을 수록 매칭의 개수는 하나씩 늘어난다.
이는 새롭게 연결되는 매칭 수가 끊어지는 매칭 수보다 하나 많으므로 당연하다.

이분 매칭 알고리즘은 더이상 augmenting path를 찾을 수 없을 때 매칭 개수가 최대가 된다는 원리를 기반으로 한다.

증명

더 이상의 augmenting path를 찾을 수 없을 때 매칭 개수가 최대가 되는지에 대해 증명해보자.

(거창하게 증명이라고 써놨지만 풀어서 글 쓴 것에 불과하고 제대로 된 이론은 참고 글들 확인 바랍니다.)

이분그래프에서 매칭 $M$과, $M$보다 매칭 개수가 많은 매칭 $M'$이 있다고 가정해보자.
이때 $(M-M')\cup(M'-M)$, 두 매칭에서 겹치는 부분을 제외하고 합쳐진 그래프를 보면

이 예시와 같이 될 것이다. 파란색은 $M'$에서 온 간선, 주황색은 $M$에서 온 간선이다.

1.
이 그래프에서 모든 정점의 차수는 2 이하이다. 차수가 3 이상이 되려면 한 정점에 연결된 간선이 3개 이상이 되어야한다. 그림으로 설명하면 한 정점에 주황색 또는 파랑색 선이 두 개이상 연결되어야 한다. 이는 $M'$이나 $M'$에서 한 정점에 두 개 이상의 매칭이 성사되었다는 뜻이므로 조건에 어긋난다.

2.
모든 정점의 차수가 2 이하이므로 이 그래프는 단순 경로와 사이클로 이루어져 있다.

3.
그리고 이분그래프에서 사이클은 반드시 짝수 개의 간선으로 이루어진다. 예시 그림에서 홀수 개의 간선 사이클을 만드려면 같은 색 정점끼리의 연결도 필요하다. 이는 이분그래프가 아니므로 모순이다.

그리고 위에서 보았듯, 한 정점에 같은 색 간선이 두 개 연결될 수 없으므로 사이클은 주황색 선 - 파란색 선... 의 반복이 될 것이다. 즉 사이클에서 $M$ 출신 간선과 $M'$ 출신 간선의 개수는 같다.

4.
매칭 $M'$은 $M$ 보다 매칭 개수가 더 많은 매칭이다. 둘의 매칭 개수는 달라야하고, 사이클을 이루는 주황색 선과 파랑색 선은 개수가 똑같으므로, 단순 경로에서 선(매칭)의 개수가 차이 나게 된다.

단순 경로도 같은 색 선이 연속으로 연결될 수 없으므로, 다음 3가지 종류에 속하게 된다.

1) 파란색 선이 하나 더 많다.
2) 주황색 선이 하나 더 많다.
3) 두 선 개수가 같다.

$M'$의 매칭 개수가 더 많으므로 종류 1에 속하는 단순 경로가 최소 $|M'|-|M|$ 만큼은 존재한다는 것을 알 수 있다.

5.
위에서 종류1에 속하는 단순 경로를 살펴보면 파란색 선 - 주황색 선 - ... - 파란색 선의 반복이다. 빨리 위로 올려서 agumenting path 정의 부분을 보자. 그렇다. 이 경로는 매칭 $M$의 agumenting path이다.

즉 매칭 $M$보다 매칭 개수가 많은 $M'$가 존재할 경우, 그래프에는 반드시 최소 $|M'|-|M|$ 개의 agumenting path가 존재한다.

역으로 말하면, 매칭 $M$의 agumenting path가 존재하지 않을 경우, 매칭 $M$은 최대 매칭이다!

---

이분 매칭 알고리즘을 공부하다 내용이나 증명을 정리해둔 글도 나한텐 어려워서 나중에 내가 다시 읽어도 이해할 수 있게 내 수준에 맞게 정리를 해두었다. 틀린 부분 좀 많을듯.

---

참고

• 알고리즘 증명, 출처 : https://cookiehcl.tistory.com/4
• 호프크로프트-카프 알고리즘 : https://gazelle-and-cs.tistory.com/35