이분 매칭(Bipartite Matching)

1. 개념

이분 그래프에서 A 그룹의 정점으로부터 B 그룹의 정점으로 간선을 연결할 때,

A 그래프 하나의 정점이 B 그래프 하나의 정점만 가지도록 구성된 것을 뜻한다.

*이분 그래프 : 정점을 두 개의 그룹으로 나누었을 때, 존재하는 모든 간선의 양 끝 정점이 서로 다른 그룹에 속하는 형태의 그래프

2. 구현

그림을 잘 못그려서 설명하기가 어려운데 (다른 블로그의 그림들을 참조하면 이해가 더 빠를듯)

A 그래프의 정점을 하나씩 순서대로 방문해서 B 그래프의 정점 하나와 연결해준다.

만약 A 그래프의 n번째 정점이 방문하는 B 그래프의 노드에 이미 A 그래프의 이전 정점에서 방문했다면

B 그래프의 정점을 뺏어서 n번째 정점이 가져오고, 이전 정점은 다시 자신이 방문할 수 있는

B 그래프의 정점을 찾는다. 이런 식으로 마지막까지 진행해서 정점끼리 연결시킨다.

[이분 매칭 예제 : http://gyutts.tistory.com/69]