최대유량 / 이분매칭 관련 정리

최대 유량 문제 : 그래프에서 가능한 최대 유량을 구하는 문제

이분 매칭 문제 : bipartite graph에서 매칭 개수를 최대로 정하는 문제 

MCMF : 각 엣지 별 비용이 있을 때, 최대 유량을 만족하는 최소 비용을 구하는 문제 

할당 문제 : bipartite graph에서 매칭하고, 각 엣지 별 비용이 있을 때, 최대 매칭 시 최소 비용을 구하는 문제 (주로 1대1 대응 관계로 perfect matching 시 최소 비용을 계산) 

 

즉, 이분 매칭은 최대 유량에서 모든 엣지의 cap이 1인 case, 할당 문제는 MCMF에서 모든 cap이 1인 case를 의미한다. (단 bipartite graph는 만족해야 함) 

 

최대 유량 문제 계산 기법 

1. Ford-Fulkerson : 최대 유량을 계산하는 기본적인 컨셉 기법

2. Edmonds-Karp : BFS 이용해서 증강 경로 찾는 기법. 복잡도 : O(VE^2)

3. Dinic : 레벨 그래프 (BFS), Blocking Flow (DFS) 이용해서 증강 경로 처리하는 기법. 복잡도 : O(V^2 E). 하지만 unit case (cap이 0,1) 에서는 O(min(V^2/3, E^1/2) * E) 

=> 따라서 그냥 Dinic 쓰는게 제일 빠르다. (sparse한 특수한 경우 아니면 왠만하면 E = V^2 정도) 

 

MCMF 계산 기법

기본 계산 방식은 Edmonds-Karp와 유사. 단, 증강 경로 찾을 때 최소 비용 경로를 찾는 것이 특징. 

Dinic의 경우, 증강 경로를 찾고, 그 다음에 flow 계산하는 것이 아닌, Blocking Flow를 이용해서 증강 경로를 따라서 유량을 최대한 보내는 것이 목적이기 때문에 MCMF의 목적 중 하나인 최소 비용 고려가 되지 않음. 

1. SPFA : Bellman-Ford와 같이 음수 엣지가 있는 경우에도 shortest path를 빠르게 찾는 방법. SPFA가 음수 엣지 처리도 가능하기 때문에 MCMF 계산 시, 역방향 cost 처리 시 음수가 되는 것에도 대응이 가능. 

최악의 경우는 SPFA의 복잡도가 O(VE) 이지만, 일반적인 상황에서는 O(V+E) 정도로 동작. 

2. Prim-Dual : Dijkstra + 잠재 함수를 이용한 기법. 양수 엣지만 처리 가능한 Dijkstra를 활용하기 위해, 역방향 cost 처리 시 음수인 상황을 보완하는 잠재 함수를 활용해 계산 시 cost가 항상 양수가 되는 상황으로 만드는 기법. 

Dijkstra 적용하므로 O(V^2) 또는 O(E logV) 

 

종합하자면 

1. SPFA 사용하는 경우, 최악의 경우 O(fVE), 일반적으로 O(f(V+E)) (f는 최대 유량 값) 

2. Prim-Dual 방식 이용하는 경우, O(fV^2) 또는 O(f E logV) 

=> 그래프 모델링에 따라서 적합한 방식을 사용해야 함. 

 

이분 매칭 기법

1. Hopcroft-Karp : 이분 매칭에 Dinic 알고리즘을 적용한 것. 복잡도 : O(E V^1/2) (그래서 보통 O(V^5/2) 로 설명함)

2. Edmonds-Karp : 이분 매칭도 최대 유량으로 모델링 가능하므로 적용 가능. 하지만 Dinic이 더 빠르므로, 이를 이용한 Hopcroft-Karp가 더 빠름. 

=> Dinic을 쓰자! 

(source -> left set 모든 노드에 cap 1, right set 모든 노드에서 sink로 cap 1 짜리 가상의 엣지 만들고, 최대 유량 계산하는 것과 동일. 매칭되는 상대는 증강 경로로 처리된 엣지) 

 

할당 문제 기법

1. Hungarian (Kuhn-Munkres) : 완전 이분 그래프에서 최소 비용 매칭 구하는데 사용. 왼쪽, 오른쪽 집합 같은 개수로 놓고 (n, n) 행렬을 이용해 원소가 0인 지점을 vertex cover에 매칭시키는 방식. (추후 공부 예정) 

복잡도 : O(n^3) (n : 완전 이분 그래프에서 한 쪽 노드 개수) 

2. MCMF 응용 : 이분 매칭과 마찬가지로, 모든 cap이 1인 상황의 MCMF와 동일하게 모델링 가능. 

복잡도 : O(V^2E), O(V(V+E)), O(V^3), O(VE log V) 등 (그래프 상황에 맞는 걸로 계산) 

(f 대신 V 넣으면 됨. bipartite graph 관점으로 보면 매칭되는 최대 개수는 왼쪽 노드 집합의 개수이고, 헝가리안처럼 완전 이분 그래프로 생각하면 f = V/2 이므로 복잡도 계산 시 대충 f=V 정도)

(사실 상 헝가리안의 n = MCMF의 V/2 이므로 헝가리안이 제일 효율적)

 

 

정리

최대 유량, 이분 매칭은 Dinic 이용

MCMF는 상황에 맞는 걸로 

할당 문제는 헝가리안 / MCMF 기법 중 상황 맞는 걸로