数据结构与算法 / 系统课时

最大流最小割定理

最大流最小割定理

最大流最小割定理回答了两个看似不同的问题:网络最多能输送多少流量,以及切断源点到汇点至少要付出多少容量。理解这一定理后,你不仅能判断最大流结果是否正确,还能从残量网络中直接恢复一个最小割。

学习目标

  • 理解任意可行流都不超过任意割容量的原因。
  • 掌握“无增广路”推出“存在同值最小割”的证明链条。
  • 使用 Edmonds-Karp 算法同时求出最大流值与最小割集合。

问题定义

在有向流网络中,每条边 (u,v)(u,v) 都有非负容量 c(u,v)c(u,v)。可行流 f(u,v)f(u,v) 必须满足容量限制与除源点、汇点外的流量守恒。最大流问题希望让从源点 ss 流出的净流量 ∣f∣|f| 尽可能大。

一个 ss-tt 割把顶点集合分成 SS 与 TT,其中 s∈Ss \in S、t∈Tt \in T。割容量只统计从 SS 指向 TT 的原图边:

c(S,T)=∑u∈S, v∈Tc(u,v)c(S,T)=\sum_{u \in S,\ v \in T} c(u,v)

最大流与最小割在残量网络中的对应关系

核心原理

1. 弱对偶:流值不超过割容量

对任意可行流和任意 ss-tt 割,源点到汇点的净流量都等于跨越该割的净流量。由于从 SS 到 TT 的每条边流量不超过容量,而从 TT 回到 SS 的流量只会减少净值,因此总有 ∣f∣≤c(S,T)|f| \le c(S,T)。

这个结论给出一个天然上界:只要找到容量为 23 的割,就能断言任何可行流都不可能超过 23。

2. 强对偶:无增广路时上界可达

最大流算法结束时,残量网络中不存在从 ss 到 tt 的路径。令 SS 为残量网络中从 ss 可达的所有顶点,令 T=V−ST=V-S。此时:

  • 原图中所有从 SS 到 TT 的边都已饱和,否则还能沿剩余容量跨到 TT。
  • 原图中所有从 TT 到 SS 的边流量都为 0,否则其反向残量边会让对应顶点重新可达。
  • 因而跨割净流量正好等于该割容量,即 ∣f∣=c(S,T)|f|=c(S,T)。

结合弱对偶,可行流已经达到某个割给出的上界,所以它是最大流,该割也必然是最小割。

3. 复杂度与判定方式

Edmonds-Karp 使用 BFS 选择最短边数增广路,时间复杂度为 O(VE2)O(VE^2),空间复杂度为 O(V2)O(V^2)(本课使用容量矩阵)。实际验证时,应同时检查最大流值、最小割容量以及两者是否相等。

完整可运行示例

下面的 Java 17 程序在经典 6 个顶点网络上计算最大流,并通过最终残量网络恢复最小割。

java
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);
    }
}

运行命令:

bash
javac MaxFlowMinCutDemo.java
java MaxFlowMinCutDemo

预期输出

text
最大流: 23
最小割 S: [0, 1, 2, 4]
最小割 T: [3, 5]
最小割容量: 23

输出中的两个数值相等,既验证了程序得到的流已达到上界,也给出了容量为 23 的最小割证书。

常见错误与练习

常见错误

最常见的错误是直接把“源点可达集合”从原图中计算出来。最小割必须依据算法结束后的残量网络;原图中的容量边并不能反映哪些方向仍可继续增广。

另一个错误是只累加从 SS 到 TT 的当前流量。割容量应读取原始容量矩阵,且只统计原图中从 SS 指向 TT 的边。

练习

  1. 将边 4 -> 5 的容量从 4 改为 10,重新运行程序,记录最大流、集合 SS、集合 TT 和最小割容量,并解释割为何发生变化。
  2. 为程序增加校验:若最大流值与最小割容量不相等,则抛出异常。验收条件是原始示例正常结束,而故意破坏残量更新后能够触发异常。

本课总结

  • 任意可行流值都不超过任意 ss-tt 割容量。
  • 无增广路时,残量网络中的可达集合构造出与当前流同值的割。
  • 最大流值与最小割容量相等,是结果正确性的可验证证书。

下一课预告

下一课将学习“二分图最大匹配”,把左侧顶点、右侧顶点和候选边转换为单位容量流网络,并从最大流结果恢复具体匹配关系。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

最大流最小割定理

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通