문제. 집이 하나 있고, 그 집의 물은 수도관을 따라 강으로 흘러갑니다. 수도관은 단방향 파이프들의 집합이며, 각 파이프의 양 끝은 집, 강, 또는 $n$개의 연결 지점 중 하나에 연결되어 있습니다. 또한 각 파이프마다 강도, 즉 그 파이프가 견딜 수 있는 물의 양이 알려져 있습니다. 단위 시간당 집에서 흘러나올 수 있는 물의 최대 양을 구해야 합니다.
문제를 좀 더 형식적으로 정의해 봅시다. 집 $s$와 강 $t$에 해당하는 두 정점이 지정된 그래프가 있으며, 나머지 정점은 연결 지점에 해당합니다. 이 그래프의 간선은 수도관에 해당하며, 각 간선에는 용량, 즉 그 간선을 통해 흐를 수 있는 물의 최대량이 있습니다. $v$에서 $u$로 가는 간선의 용량을 $c(v, u)$로, 그 간선을 통해 흐르는 물의 양을 $f(v, u)$로 표기합시다.
수도관을 따라 흐르는 물의 몇 가지 성질을 살펴봅시다. 예를 들어, 연결 지점에 해당하는 모든 정점에 대해 그 정점으로 흘러 들어오는 물의 양은 그 정점에서 흘러 나가는 물의 양과 같습니다.
$$ \sum_u f(u, v) = \sum_u f(v, u) $$이는 물이 아무 데서나 갑자기 생겨나거나 어디론가 사라질 수 없다는 뜻입니다.
또한 모든 간선에는 정확히 하나의 역방향 간선이 있고 $f(v, u) = -f(u, v)$라고 생각하면 편리합니다. 즉, $v$에서 $u$로 가는 간선을 따라 $x$만큼의 유량이 흐르면, $u$에서 $v$로 가는 간선을 따라서는 $-x$만큼의 유량이 흐릅니다.
이제 유입량과 유출량에 대한 관찰은 원천 $s$와 싱크 $t$를 제외한 모든 정점 $v$에 대해 다음과 같이 표현됩니다.
$$ \sum_u f(v, u) = 0 $$ 그러면 우리의 과제는 앞의 등식들을 만족하고 어떤 용량도 초과하지 않으면서 $\sum f(s, u) = \sum f(u, t)$를 최대화하는 함수 $f$를 찾는 것입니다: $$ f(v, u) \leq c(v, u) $$ 이 어려운 문제에는 여러 가지 해법이 있으며, 이 장에서 그 해법들을 살펴보겠습니다.