数据结构与算法 / 系统课时
最大流最小割定理
最大流最小割定理
最大流最小割定理回答了两个看似不同的问题:网络最多能输送多少流量,以及切断源点到汇点至少要付出多少容量。理解这一定理后,你不仅能判断最大流结果是否正确,还能从残量网络中直接恢复一个最小割。
学习目标
- 理解任意可行流都不超过任意割容量的原因。
- 掌握“无增广路”推出“存在同值最小割”的证明链条。
- 使用 Edmonds-Karp 算法同时求出最大流值与最小割集合。
问题定义
在有向流网络中,每条边 都有非负容量 。可行流 必须满足容量限制与除源点、汇点外的流量守恒。最大流问题希望让从源点 流出的净流量 尽可能大。
一个 - 割把顶点集合分成 与 ,其中 、。割容量只统计从 指向 的原图边:

核心原理
1. 弱对偶:流值不超过割容量
对任意可行流和任意 - 割,源点到汇点的净流量都等于跨越该割的净流量。由于从 到 的每条边流量不超过容量,而从 回到 的流量只会减少净值,因此总有 。
这个结论给出一个天然上界:只要找到容量为 23 的割,就能断言任何可行流都不可能超过 23。
2. 强对偶:无增广路时上界可达
最大流算法结束时,残量网络中不存在从 到 的路径。令 为残量网络中从 可达的所有顶点,令 。此时:
- 原图中所有从 到 的边都已饱和,否则还能沿剩余容量跨到 。
- 原图中所有从 到 的边流量都为 0,否则其反向残量边会让对应顶点重新可达。
- 因而跨割净流量正好等于该割容量,即 。
结合弱对偶,可行流已经达到某个割给出的上界,所以它是最大流,该割也必然是最小割。
3. 复杂度与判定方式
Edmonds-Karp 使用 BFS 选择最短边数增广路,时间复杂度为 ,空间复杂度为 (本课使用容量矩阵)。实际验证时,应同时检查最大流值、最小割容量以及两者是否相等。
完整可运行示例
下面的 Java 17 程序在经典 6 个顶点网络上计算最大流,并通过最终残量网络恢复最小割。
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Queue;
public class MaxFlowMinCutDemo {
private static boolean bfs(int[][] residual, int source, int sink, int[] parent) {
Arrays.fill(parent, -1);
boolean[] visited = new boolean[residual.length];
Queue<Integer> queue = new ArrayDeque<>();
queue.offer(source);
visited[source] = true;
while (!queue.isEmpty()) {
int u = queue.poll();
for (int v = 0; v < residual.length; v++) {
if (!visited[v] && residual[u][v] > 0) {
parent[v] = u;
visited[v] = true;
if (v == sink) {
return true;
}
queue.offer(v);
}
}
}
return false;
}
private static int maxFlow(int[][] capacity, int source, int sink, int[][] residual) {
for (int i = 0; i < capacity.length; i++) {
residual[i] = Arrays.copyOf(capacity[i], capacity[i].length);
}
int[] parent = new int[capacity.length];
int totalFlow = 0;
// 每轮 BFS 找到一条增广路,再统一更新正向与反向残量。
while (bfs(residual, source, sink, parent)) {
int pathFlow = Integer.MAX_VALUE;
for (int v = sink; v != source; v = parent[v]) {
pathFlow = Math.min(pathFlow, residual[parent[v]][v]);
}
for (int v = sink; v != source; v = parent[v]) {
int u = parent[v];
residual[u][v] -= pathFlow;
residual[v][u] += pathFlow;
}
totalFlow += pathFlow;
}
return totalFlow;
}
private static boolean[] reachableFromSource(int[][] residual, int source) {
boolean[] reachable = new boolean[residual.length];
Queue<Integer> queue = new ArrayDeque<>();
queue.offer(source);
reachable[source] = true;
while (!queue.isEmpty()) {
int u = queue.poll();
for (int v = 0; v < residual.length; v++) {
if (!reachable[v] && residual[u][v] > 0) {
reachable[v] = true;
queue.offer(v);
}
}
}
return reachable;
}
public static void main(String[] args) {
int[][] capacity = new int[6][6];
capacity[0][1] = 16;
capacity[0][2] = 13;
capacity[1][2] = 10;
capacity[2][1] = 4;
capacity[1][3] = 12;
capacity[3][2] = 9;
capacity[2][4] = 14;
capacity[4][3] = 7;
capacity[3][5] = 20;
capacity[4][5] = 4;
int[][] residual = new int[6][6];
int maximumFlow = maxFlow(capacity, 0, 5, residual);
boolean[] reachable = reachableFromSource(residual, 0);
List<Integer> setS = new ArrayList<>();
List<Integer> setT = new ArrayList<>();
int cutCapacity = 0;
// 最终残量网络中从源点可达的顶点构成集合 S。
for (int u = 0; u < capacity.length; u++) {
if (reachable[u]) {
setS.add(u);
} else {
setT.add(u);
}
}
for (int u = 0; u < capacity.length; u++) {
for (int v = 0; v < capacity.length; v++) {
if (reachable[u] && !reachable[v]) {
cutCapacity += capacity[u][v];
}
}
}
System.out.println("最大流: " + maximumFlow);
System.out.println("最小割 S: " + setS);
System.out.println("最小割 T: " + setT);
System.out.println("最小割容量: " + cutCapacity);
}
}运行命令:
javac MaxFlowMinCutDemo.java
java MaxFlowMinCutDemo预期输出
最大流: 23
最小割 S: [0, 1, 2, 4]
最小割 T: [3, 5]
最小割容量: 23输出中的两个数值相等,既验证了程序得到的流已达到上界,也给出了容量为 23 的最小割证书。
常见错误与练习
常见错误
最常见的错误是直接把“源点可达集合”从原图中计算出来。最小割必须依据算法结束后的残量网络;原图中的容量边并不能反映哪些方向仍可继续增广。
另一个错误是只累加从 到 的当前流量。割容量应读取原始容量矩阵,且只统计原图中从 指向 的边。
练习
- 将边
4 -> 5的容量从 4 改为 10,重新运行程序,记录最大流、集合 、集合 和最小割容量,并解释割为何发生变化。 - 为程序增加校验:若最大流值与最小割容量不相等,则抛出异常。验收条件是原始示例正常结束,而故意破坏残量更新后能够触发异常。
本课总结
- 任意可行流值都不超过任意 - 割容量。
- 无增广路时,残量网络中的可达集合构造出与当前流同值的割。
- 最大流值与最小割容量相等,是结果正确性的可验证证书。
下一课预告
下一课将学习“二分图最大匹配”,把左侧顶点、右侧顶点和候选边转换为单位容量流网络,并从最大流结果恢复具体匹配关系。