이분 매칭 알고리즘 (Bipartite Matching) 두 개의 정점 그룹이 존재할 때 모든 간선(경로)의 용량이 1이면서 양쪽 정점이 서로 다른 그룹에 속하는 그래프를 이분 그래프(Bipartite Graph)라고 말합니다. 이러한 이분 그래프에서 예를 들어, 한쪽 그룹은 X 그룹, 다른 한쪽 그룹은 Y 그룹이라고 할 때 모든 경로의 방향은 X->Y인 그래프의 최대 유량을 구하는 것이 이분 매칭(Bipartite Matching)입니다. 이분 매칭을 통해 구하고자 하는 것은 최대 매칭 수입니다. 매칭을 한다는 것은 어떤 정점이 그것이 가리키는 위치의 다른 정점을 점유한 상태를 말하며 각 정점은 한 개씩만 점유 가능하고 여러개의 정점을 점유할 수 없습니다. 간선의 용량이 1인 것은 바로 이러한 이유에서..