bipartite matching (1) 썸네일형 리스트형 141. Bipartite Matching 플로우 문제를 풀다 보면 특수한 형태의 그래프가 자주 등장하는 것을 알 수 있다. 아래의 그래프를 보자. 소스에서 첫 번째 그룹의 정점들로 가는 간선들이 있고, 첫 번째 그룹의 정점들에서 두 번째 그룹의 정점들로 가는 간선이 있고, 두 번째 그룹의 정점들에서 싱크로 가는 간선이 있다. 각 간선의 용량은 전부 $1$이다. 위 그래프에서 소스와 싱크를 없애고 간선의 방향 표시도 없애면 아래와 같은 이분 그래프가 된다. 간선의 용량이 전부 $1$이므로, 이 그래프에서 최대 유량을 구하는 문제는 첫 번째 그룹에 속하는 정점들과 두 번째 그룹에 속하는 정점들 간의 최대 매칭(Maximum Matching)의 크기를 찾는 문제로 생각할 수 있다. 앞서 소스와 싱크에 연결된 간선들의 용량도 전부 $1$이었으므로 각각.. 이전 1 다음
