최대 유량 문제 (Maximum Flow) 최대 유량 문제(Maximum Flow)란 방향 그래프에서 각 간선의 용량이 정해져 있을 때, 정해진 출발점에서 도착점까지 보낼 수 있는 최대의 유량을 계산하는 문제를 말한다. 위와 같이 생긴 방향 그래프의 1번 정점에서 7번 정점까지의 최대 유량인 상황은 아래 그림과 같다. 간선에 적힌 a/b는 용량이 b인 간선에 현재 a의 유량이 흐르고 있다는 것을 말한다. 이 경우의 유량은 11이다. 더 이상의 유량이 없다는 것은 어떻게 알 수 있을까? 최소 1의 유량이 흐를 수 있는 출발점에서 도착점까지 가는 경로를 증가경로(Augmented Path)라고 한다. 위 그래프에서 증가경로는 없다는 사실을 눈으로도 쉽게 확인할 수 있으며, 임의의 그래프에 대해서도 DFS/B..
