임의의 Directed Graph 가 주어졌을 때, 시작점 S에서 끝점 E까지 흐를 수 있는 최대 유량을 구하는 Algorithm.
Network Flow(Maximum Flow) 를 해결하는 방법 중 하나로 Ford-Fulkerson 알고리즘이 있다.
Ford-Fulkerson 알고리즘 :
시작점 -> 끝점까지 하나의 경로를 찾는다. (이 때 BFS로 찾아 간선수를 최소로 해야 효율적임 : Edmond-Karp Algorithm)
경로 중 가중치가 최소인 간선을 찾아 아까 찾은 경로의 정방향에서 빼주고 역방향에서 더해준다.
(이것은 정방향으로 일정한 유량을 흘리고 흘릴 수 있는 가중치를 다시 계산해주는 과정이다.)
유량 그래프 역시 갱신해준다.
더 이상 경로를 찾을 수 없을 때까지 위의 과정을 반복한다.
=> Network Flow 알고리즘의 응용으로 Bipartite Matching(이분 매칭) 문제를 해결 할 수 있다.
임의의 시작점 s를 만들어 이분 매칭의 한쪽 집합을 모두 연결한다. (모든 가중치 1)
Matching 가능한 두 원소를 가중치 1인 Edge로 연결한다.
임의의 끝점 e를 만들어 다른쪽 집합을 모두 연결한다. (가중치 1)
이 그래프에 대하여 Network Flow를 실행한다.
이 때의 Flow가 최대 이분 매칭 쌍의 수이다.
=> 제거되는 그래프 간선의 가중치의 합을 최소로 하여 그래프를 두 부분으로 분리하는 Minimum Cut 문제 역시 전체 간선 가중치의 합에서 Maximum Flow를 제거하면 된다는 것이 증명되어 있다.