flow · max-flow min-cut · 群流

流：网络流、最大流-最小割与群流

一张有向带容量网络有一个源 s 与一个汇 t；每条边 (u,v) 有容量 cap(u,v)。一个 flow 给每条边赋一个 ${0 \le f(u,v) \le cap(u,v)}$ 的值（容量约束），并且除 s、t 外每个顶点流入等于流出（守恒约束）。问的是：从 s 能往 t 推多大的总流量？本页用 Ford–Fulkerson 在残量网络上反复找增广路，单步看流如何长大，并在终态揭示它恰好被一道最小割卡住。

残量网络 (residual graph): 给定当前 flow，边 (u,v) 的残量为 $cap(u,v) - f(u,v)$ ；此外每条已有正流的边都生出一条反向边 (v,u)，残量为 f(u,v)——它允许「撤销」已经推过的流。一条从 s 到 t 的增广路 (augmenting path) 就是残量网络里一条所有边残量都 > 0 的有向路；取路上最小残量为瓶颈 (bottleneck)，沿路把正向边的流 +bottleneck、反向边的流 $-bottleneck$ ，总流量就涨 bottleneck。残量全部为 0 时无路可增，算法停。

最大流-最小割定理 (max-flow min-cut): 一道 s-t 割 是顶点集的一个划分 (S, T)， $s \in S$ 、 $t \in T$ ；它的容量是所有从 S 指向 T 的边的容量之和（只数 $S\to T$ 方向，不数反向）。定理断言：最大流的值 = 最小割的容量。证明的关键正是：当残量网络里再也找不到增广路时，令 S = 残量网络中从 s 可达的顶点集，则 $t \notin S$ ，且所有 $S\to T$ 边都满载（残量 0）、所有 $T\to S$ 边零流——此时流值恰好等于这道割的容量，两边互为上下界，于是双双达到最优。终态图中顶点按 S / T 两色染开，即是这道最小割。

同源的对偶定理： 最大流-最小割是一族「max-min」对偶里最有名的一个，它的若干特例正是图论里的经典定理。取所有容量为 1、问点不相交（或边不相交）的 s-t 路最多几条，就得到 Menger 定理（最大不相交路数 = 最小分隔集大小）；把它架在二部图上，又退化成 König 定理（二部图最大匹配 = 最小顶点覆盖）。它们与本页的流-割对偶共享同一套「增广 / 阻塞」论证骨架。

群流与 Tutte 的流-着色对偶： 把流的取值从整数推广到一个有限交换群 Γ，得到群流 (group-valued flow)：给每条（定向）边赋 Γ 中的值，要求每个顶点处流守恒，且每条边取值非零，即处处非零流 (nowhere-zero flow)。Tutte 证明：一张图存在处处非零的 k-流，只与 k 有关、与具体群无关；并且对平面图而言，这与对偶图的面着色精确对偶——平面图的流数 (flow number) 等于其对偶图的色数。于是「四色定理」也可等价地表述成「无桥平面图都有处处非零 4-流」。详见图着色与平面对偶。