Bipartite Maximum Matching

이분 그래프에서 Maximum matching에서 가장 중요한 아이디어 중 하나는 alternating path이다.

매칭중인 상황에서, 기존의 간선을 몇 개 끊고 다른 방법으로 이으면 더 많이 매칭시킬 수 있는 경우가 있다.
이 때 이러한 '개선'을 어떻게 생각할 수 있을까?

매칭되지 않는 간선으로 시작하고 끝나며, 매칭되지 않은 간선과 매칭된 간선을 번갈아가며 사용하는 경로를 생각해보자.
이 경로에는 매칭되지 않은 간선이 매칭된 간선보다 하나 더 많다.
만약 시작점과 끝점이 매칭되지 않은 점들이라면, 여기서 매칭을 늘릴 수 있겠다.
매칭되지 않은 간선을 매칭시키고, 매칭된 간선들의 매칭을 풀면 된다.
매칭은 한 개 늘어나게 된다.

(이는 그래프를 모든 간선의 플로우를 1로 생각한 네트워크 플로우에서의 augmenting path로도 생각할 수 있는 부분이다. 이 때 bipartite한 양쪽을 각각 source와 sink로 설정하면 된다.)

alternating path가 존재하지 않는 매칭은 maximum matching이다. 즉 greedy하게 alternating path를 찾아나가면 maximum matching을 찾을 수 있다.