정리
서로 다른 시작점 $s$와 도착점 $t$를 가진 유한 유향 네트워크 $G=(V,E)$를 생각하자. 각 유향 간선 $e$에는 유한한 음이 아닌 용량 $c_e$가 주어진다. 실현 가능한 유량은 각 간선에 값 $f_e$를 할당하여
\[0\leq f_e\leq c_e\]| 를 만족하고, $s,t$ 이외의 모든 정점에서 유입량과 유출량이 같도록 한 것이다. 유량의 값 $ | f | $는 $s$에서 나가는 순유량이며, 이는 $t$로 들어오는 순유량과 같다. |
$s$–$t$ 컷은 $V=S\mathbin{\dot\cup}T$, $s\in S$, $t\in T$를 만족하는 정점 집합의 분할이다. 컷의 용량은 원래 유향 간선 가운데 꼬리 정점이 $S$에, 머리 정점이 $T$에 속하는 간선들의 용량 합으로 정의한다.
\[c(S,T)=\sum_{e=(u,v)\in E:\ u\in S,\ v\in T} c_e.\]최대 유량 최소 컷 정리는 실현 가능한 유량의 최대값이 모든 $s$–$t$ 컷 용량의 최솟값과 같다고 말한다.
증명
먼저 임의의 실현 가능한 유량 $f$와 임의의 $s$–$t$ 컷 $(S,T)$를 택한다. $S$의 정점들에 대해 유량 보존식을 합하면 양 끝점이 모두 $S$에 있는 간선의 유량은 상쇄되어
\[|f|=\sum_{e=(u,v):\,u\in S,v\in T}f_e-\sum_{e=(u,v):\,u\in T,v\in S}f_e\]| 를 얻는다. 두 번째 합의 항들은 음이 아니고, 첫 번째 합에서는 각 간선의 유량이 용량 이하이므로 $ | f | \leq c(S,T)$이다. 이는 모든 실현 가능한 유량과 모든 컷에 대해 성립한다. |
네트워크가 유한하고 용량들이 유한하므로, 실현 가능한 유량들의 집합은 유한 차원 공간의 공집합이 아닌 콤팩트 집합이다. 따라서 최대 유량 $f$가 존재한다. 잔여 그래프를 만들자. 각 원래 간선 $u\to v$에 대해 정방향 잔여 간선의 용량은 $c_e-f_e$, 역방향 잔여 간선 $v\to u$의 용량은 $f_e$이다. 잔여 간선은 각각 원래 간선에 대응한다. 양의 용량을 가진 잔여 간선들을 따라 $s$에서 도달 가능한 정점들의 집합을 $S$라 하고, $T=V\setminus S$라 하자. $f$가 최대 유량이므로 $t$는 도달 가능하지 않다. 만약 도달 가능하다면 잔여 그래프에 $s$에서 $t$로 가는 경로가 있고, 그 경로에서 양수만큼 유량을 증가시켜 유량값을 높일 수 있기 때문이다.
$S$에서 $T$로 향하는 양의 용량 잔여 간선은 없다. 따라서 원래 간선 중 $S$에서 $T$로 향하는 간선은 모두 포화되어 $f_e=c_e$이다. 또한 $T$에서 $S$로 향하는 원래 간선마다 그 역방향 잔여 간선이 $S$에서 $T$로 향하므로, 그 잔여 용량은 0이어야 하고 따라서 $f_e=0$이다. 이를 앞서 얻은 컷 식에 대입하면
\[|f|=\sum_{e=(u,v):\,u\in S,v\in T}c_e=c(S,T).\]따라서 이 최대 유량은 이 컷의 용량과 같다. 모든 유량은 모든 컷 용량 이하이므로 이 유량은 최대이고 이 컷은 최소이며, 두 값은 같다. ∎