네트워크 통신에는 대역폭이 있기 때문에 하나의 최단 경로로 보내는 것보다, 일부가 더 긴 경로를 돌아오더라도 패킷을 여러 경로로 나눠서 보내는 것이 더 이득일 수 있다.

그림을 보면 s → a → c → t 로 보내면 s→a 에서 16을 보낸다고 해도 c → t 의 대역폭이 10이기 때문에 10만 전송된다.

그림 (b)처럼 보내면 17을 보낼 수 있다.

이처럼 얼마나 많은 유량(흐름)을 보낼 수 있는지 계산하는 문제이다.

정점 u에서 v로 가는 간선의 용량을 c(u,v), 실제 흐르는 유량을 f(u,v)라고 할 때,

• 용량 제한 속성 : f(u,v) ≤ c(u,v), 각 간선의 유량은 해당 간선의 용량을 초과할 수 없다.
• 유량의 대칭성 : f(u,v) = -f(v,u), u에서 v로 유량이 흘러올 경우, v의 입장에서는 u로 음수의 유량을 보내는 것이라고 생각하도록 하자.
• 유량의 보존 : 각 정점에 들어오는 유량과 나가는 유량의 양은 정확히 같아야 한다.

포드-풀커슨 알고리즘