网络流与匹配：最大流最小割定理及其算法

2026/05/28 14:09:29

数学图论·27 min read

图论网络流最大流最小割二部图匹配匈牙利算法

Part 0 · 学习目标

本节在图论课程中的位置

本节属于图论课程的高级应用模块。前置内容为图的连通性、欧拉路径与哈密顿路径；后续可延伸至近似算法、在线算法中的流网络技术，以及机器学习中的图神经网络。

前置知识回顾

有向图：有向边的集合与路径概念。去哪里补：图论基础章节。
图的遍历：DFS 与 BFS 的时间复杂度与适用场景。
线性规划基础：对偶理论与强对偶定理（有助于理解最大流最小割的本质）。

Part 1 · 背景问题

为什么需要网络流

从物理直观到数学抽象

考虑一个水管网络：节点是交叉路口，有向边是管道，每条管道有容量上限（单位时间能通过的水量），源点 $$s$$ 是水厂，汇点 $$t$$ 是用户。自然的问题是：从 $$s$$ 到 $$t$$ 每单位时间最多能送多少水？

这个问题看似简单——只需找到网络中的"瓶颈"，但精确描述瓶颈并给出最优解，需要一套完整的数学语言。网络流理论提供了这种语言：将物理约束（容量、守恒）转化为数学约束（不等式、守恒方程），然后用算法找到最优值。

实际问题域

场景	流网络要素	关键问题
通信网络	路由器=节点，链路带宽=容量	最大数据传输率
物流运输	仓库/港口=节点，运输通道容量=容量	货物最大吞吐量
任务分配	工人/任务=节点，分配上限=容量	最多完成的任务数
图像分割	像素=节点，超像素边=容量	前景/背景分离

Part 2 · 概念定义

网络流的基本定义与约束

流网络的数学定义

一个流网络是一个四元组 $$G=(V, E, s, t)$$ ，其中：

$$V$$ 是有限顶点集
$E \subseteq V \times V$ 是有向边集（允许平行边）
$s \in V$ 是源点（source），只有出流
$t \in V$ 是汇点（sink），只有入流

每条边 $(u, v) \in E$ 有一个容量函数 $c: E \to \mathbb{R}^+$ ，记作 $$c(u, v)$$ 或 $c_{uv}$ 。

流函数及其约束

一个流函数是映射 $f: E \to \mathbb{R}^+$ ，满足两条约束：

容量约束（Capacity Constraint）： $\forall (u, v) \in E,\ f(u, v) \leq c(u, v)$

每条边上的流量不得超过其容量上限。

守恒约束（Conservation Constraint）： $\forall v \in V \setminus \{s, t\},\ \sum_{u:(u,v)\in E} f(u, v) = \sum_{w:(v,w)\in E} f(v, w)$

中间节点的入流量等于出流量（流不凭空产生也不凭空消失）。

流的净流量（值）

流 $$f$$ 的值（value）定义为源点的总发出量：

|f| = \sum_{v:(s,v)\in E} f(s,v) = \sum_{v:(v,t)\in E} f(v,t)

守恒约束保证两端计算等价。最大流问题即：

\max\ |f| \quad \text{subject to} \quad f \text{ 满足容量与守恒约束}

一句话理解：流网络是带容量约束的有向图，流函数在每条边上分配流量，目标是让源点到汇点的总流量最大。

残余容量与残余图

给定当前流 $$f$$ ，定义残余容量 $$c_f(u, v)$$ ：

c_f(u, v) = \begin{cases} c(u, v) - f(u, v) & \text{若 } (u, v) \in E \text{ 且尚未饱和} \\ f(v, u) & \text{若 } (v, u) \in E \text{（反向边）} \\ 0 & \text{否则} \end{cases}

残余容量刻画了当前流下每条边"还能再推多少"的剩余空间，由此构成残余图 $$G_f = (V, E_f, s, t)$$ ，其中 $E_f = \{(u,v) : c_f(u,v) > 0\}$ 。

整数流定理（Integral Flow Theorem）

若所有边容量均为整数，则 Ford-Fulkerson 方法产生的最大流在每条边上也是整数流量。这一结论是网络流方法在组合优化中广泛应用的基础——避免了分数流量在实践中无法解释的问题。

Part 3 · 核心定理

最大流最小割定理

割的定义

设 $$G=(V,E,s,t,c)$$ 为一流网络。一个 $$s$$ - $$t$$ 割（cut）是顶点集的一个划分 $$(S, T)$$ ，满足 $s \in A,\ t \in T$ 。割的割集（cut-set）为跨越 $$A$$ 到 $$T$$ 方向的边集：

X_C = \{(u, v) \in E : u \in S,\ v \in T\}

割的容量为割集中所有边的容量之和：

c(S, T) = \sum_{(u,v) \in X_C} c(u, v)

直观理解：切断割集中的所有边后，源点

$s$

与汇点

$t$

之间不再连通——割的容量越小，系统越脆弱。

最大流最小割定理（Max-Flow Min-Cut Theorem）

定理陈述（Ford & Fulkerson, 1956）

在任意流网络 $$G=(V,E,s,t,c)$$ 中，从 $$s$$ 到 $$t$$ 的最大流的流量值等于所有 $$s$$ - $$t$$ 割中容量的最小值：

\max_{f} |f| = \min_{(S,T)} c(S, T)

证明思路（对偶性）

定理的经典证明通过残余图与增广路径的互补性展开，核心分两步：

Lemma 1（流量上界）：任意流 $$f$$ 的值不超过任意 $$s$$ - $$t$$ 割的容量，即 $|f| \leq c(S, T)$ 。

证明：对割集 $$X_C$$ 中的每条边应用容量约束，然后在 $$S$$ 中求和，利用守恒约束消去中间项，得 $|f| \leq \sum_{(u,v)\in X_C} c(u,v) = c(S,T)$ 。∎

Lemma 2（最优性条件）：若残余图 $$G_f$$ 中不存在从 $$s$$ 到 $$t$$ 的增广路径，则当前流 $$f$$ 是最大流。

证明：令 $$S$$ 为残余图中从 $$s$$ 可达的顶点集， $T = V \setminus S$ 。则 $s \in S,\ t \in T$ ，且由构造知：所有从 $$S$$ 到 $$T$$ 的边在 $$G$$ 中均已饱和。故 $$|f| = c(S, T)$$ ，由 Lemma 1 知此 $$f$$ 已达到上界，故为最大流。∎

定理证明：设 $$f^*$$ 为 Ford-Fulkerson 方法终止时产生的流， $$(S^*, T^*)$$ 为上述过程构造的割。则 $$|f^*| = c(S^*, T^*)$$ ，且对任意割 $$(S,T)$$ 有 $|f^*| \leq c(S,T)$ ，故 $$|f^*|$$ 为最大流值， $$(S^*, T^*)$$ 为最小割。∎

深层理解：上述证明揭示了流与割之间的对偶关系——等价于线性规划中的强对偶定理。从线性规划角度看，最大流问题是对偶于最小割问题的线性规划，两者最优值相等是强对偶性的直接推论。

配图：最大流最小割示意图

flowchart LR
    subgraph 流网络
        s(("s")) -->|"c=10"| v1
        s(("s")) -->|"c=8"| v2
        v1 -->|"c=4"| t(("t"))
        v2 -->|"c=6"| t(("t"))
        v1 -->|"c=5"| v2
    end

图中展示了典型的流网络，源点 $$s$$ 到汇点 $$t$$ 的最大流为 14，最小割 $(S=\{s,v_1\}, T=\{v_2,t\})$ 容量为 14。

Part 4 · 核心算法

Ford-Fulkerson 方法

增广路径

残余图 $$G_f$$ 中一条从 $$s$$ 到 $$t$$ 的有向路径 $$P$$ 称为增广路径（augmenting path）。设路径上残余容量的最小值为 $$b$$ ，沿路径每条正向边增加 $$b$$ 的流量，每条反向边减少 $$b$$ 的流量（相当于"撤销"之前推送的流量）。增广后流值至少增加 $$b$$ 。

Ford-Fulkerson 方法算法步骤

初始化：设所有边流量 $$f(e) = 0$$
构建残余图 $$G_f$$
寻找增广路径：在 $G_f$ 中用 DFS/BFS 寻找从 $s$ 到 $t$ 的路径
- 若不存在，停止，当前流为最大流
- 若存在，记最小残余容量为 $$b$$ ，沿路径增广 $$b$$ 单位流
返回步骤 2

若容量为整数，每步增广至少使总流量增加 1，故算法必终止。复杂度为 $O(E \cdot F)$ ，其中 $$F$$ 是最大流值——对大数值容量可能极慢。

配图：Ford-Fulkerson 增广路径过程

flowchart LR
    subgraph 步骤1["步骤1：初始流"]
        s1(("s")) -->|"0/10"| a1
        s1(("s")) -->|"0/8"| b1
        a1 -->|"0/4"| t1(("t"))
        b1 -->|"0/6"| t1(("t"))
        a1 -->|"0/5"| b1
    end

    subgraph 步骤2["步骤2：增广路径 s→a→b→t"]
        s2(("s")) -->|"4/10"| a2
        s2(("s")) -->|"0/8"| b2
        a2 -->|"0/4"| t2(("t"))
        b2 -->|"6/6"| t2(("t"))
        a2 -->|"4/5"| b2
    end

    subgraph 步骤3["步骤3：增广路径 s→b→t"]
        s3(("s")) -->|"4/10"| a3
        s3(("s")) -->|"6/8"| b3
        a3 -->|"4/4"| t3(("t"))
        b3 -->|"6/6"| t3(("t"))
        a3 -->|"4/5"| b3
    end

展示了 Ford-Fulkerson 方法的两步增广过程。第一步沿路径 $s \to a \to b \to t$ 增广 4 单位流，第二步沿 $s \to b \to t$ 增广 6 单位流，最终总流量为 14。

Edmonds-Karp 算法

Edmonds-Karp（1972）是对 Ford-Fulkerson 的重要改进：使用 BFS 寻找最短增广路径。BFS 保证每次增广路径长度为当前最短距离。

关键性质：每次增广后，残余图中至少有一条边饱和，且该边到源点的最短距离严格增加。因此增广路径长度非递减，路径长度上限为 $$V-1$$ 。

由此证明复杂度为 $$O(V E^2)$$ 。

算法选择建议：Edmonds-Karp 在实际应用中比朴素 Ford-Fulkerson 更稳定，因为它避免了最坏情况下

O(E \cdot F)

的病态行为。

Part 5 · 高级算法

Dinic 算法

层次图与阻塞流

Dinic（1970）的核心思想是：每次 BFS 构建层次图（level graph），然后在该层次图上用 DFS 寻找多个增广路径——直到不存在新的 $$s$$ - $$t$$ 路径为止（此时得到阻塞流，blocking flow）。

层次图： $\text{dist}(v)$ 为残余图中从 $$s$$ 到 $$v$$ 的最短路径长度。层次图只保留那些恰好前进一个层次的有向边：

E_L = \{(u,v) \in E_f : \text{dist}(v) = \text{dist}(u) + 1\}

阻塞流：层次图中的一个流，使得删除所有饱和边后图中不再有从 $$s$$ 到 $$t$$ 的路径——即所有从 $$s$$ 到 $$t$$ 的路径都至少有一条边被饱和。

Dinic 算法步骤

初始化流 $$f = 0$$
在残余图 $$G_f$$ 上用 BFS 计算 $\text{dist}(\cdot)$ ，构建层次图 $$G_L$$ 。若 $\text{dist}(t) = \infty$ ，停止，当前流为最大流
在层次图 $$G_L$$ 上用 DFS 寻找阻塞流 $$f'$$
将 $$f$$ 与 $$f'$$ 合并（ $f \leftarrow f + f'$ ），返回步骤 2

复杂度分析

每轮阻塞流计算后， $\text{dist}(t)$ 至少增加 1（因为所有从 $$s$$ 到 $$t$$ 的短路径均被阻塞）。而 $\text{dist}(t) \leq V-1$ ，故阻塞流轮数不超过 $$V-1$$ 轮。

每轮中：

BFS 构建层次图： $$O(E)$$
DFS 寻找阻塞流： $$O(VE)$$

总体复杂度： $$O(V^2 E)$$ 。

在单位容量图（所有边容量为 1）上，阻塞流可在 $$O(E)$$ 内找到，且轮数不超过 $O(\sqrt{E})$ 和 $O(V^{2/3})$ 中的较小值。特别地，二部图匹配对应的网络轮数不超过 $O(\sqrt{V})$ ，对应 Hopcroft-Karp 算法的 $O(E\sqrt{V})$ 复杂度。

Part 6 · 二部图匹配

二部图最大匹配

基本概念

二部图（bipartite graph） $G = (L \cup R, E)$ 的顶点分为左右两部分，边只在跨部分之间出现。匹配（matching）是边的子集，其中任意两条边不共享端点。最大匹配是边数最多的匹配。

König 定理（1931）

在任意二部图中，最大匹配的边数等于最小顶点覆盖的顶点数：

\nu(G) = \tau(G)

其中 $\nu(G)$ 为最大匹配基数， $\tau(G)$ 为最小顶点覆盖的基数。

证明（基于最大流）：构造流网络 $G'_{\infty}$ ：源点 $$s$$ 连向每个 $l \in L$ （容量 1），每个 $r \in R$ 连向汇点 $$t$$ （容量 1）， $$L$$ 与 $$R$$ 之间的边容量为 $\infty$ 。在该网络中，最大流的流量等于最大匹配的边数。由最大流最小割定理，最大流 = 最小割。设最小割将顶点划分为 $$(S, T)$$ ，则最小割容量为 $|L \cap T| + |R \cap S|$ ，恰好是 $K = (L \cap T) \cup (R \cap S)$ 的大小，而 $$K$$ 是一个顶点覆盖。∎

Hall 婚配定理（1935）

设 $G = (L \cup R, E)$ 为一二部图。对任意子集 $X \subseteq L$ ，记其邻域为 $N(X) = \{v \in R : \exists u \in X, (u,v) \in E\}$ 。则存在完美匹配的充要条件是：

\forall X \subseteq L:\ |N(X)| \geq |X|

即：左侧任意 $$k$$ 个人的邻居集合至少包含 $$k$$ 个人，则所有人可以两两匹配。

配图：二部图匹配过程

flowchart LR
    subgraph 左["L（左侧）"]
        l1(("L1"))
        l2(("L2"))
        l3(("L3"))
    end

    subgraph 右["R（右侧）"]
        r1(("R1"))
        r2(("R2"))
        r3(("R3"))
    end

    l1 -->|"边"| r1
    l1 -->|"边"| r2
    l2 -->|"边"| r2
    l2 -->|"边"| r3
    l3 -->|"边"| r3

    style l1 fill:#90EE90
    style l2 fill:#90EE90
    style r1 fill:#90EE90
    style r3 fill:#90EE90

展示了二部图匹配的增广路径过程。绿色顶点表示已匹配的顶点。最大匹配为 $\{(L1,R1), (L2,R2), (L3,R3)\}$ ，共 3 条边。

匈牙利算法（Kuhn-Munkres）

对于带权二部图的最大权匹配（即 assignment problem），使用匈牙利算法，复杂度 $$O(V^3)$$ 。核心思想是在势函数（potential）下保持最优性，将权重匹配转化为一系列等价的最小费用最大流问题。

未加权情形的增广路径算法：对每个左顶点，用 BFS 寻找增广路径。若找到则翻转匹配（增广）；否则重复。该算法在最坏情况下复杂度 $$O(VE)$$ 。

Hopcroft-Karp 通过分层多路增广（每次 BFS 寻找所有最短增广路径）将复杂度降至 $O(E\sqrt{V})$ 。

Part 7 · 扩展主题

最小费用最大流

问题定义

在最大流问题的基础上，每条边增加费用函数 $a: E \to \mathbb{R}$ （单位流量穿过边的成本）。目标变为：在达到最大流的前提下，最小化总费用：

\min \sum_{(u,v)\in E} a(u,v) \cdot f(u,v) \quad \text{s.t.} \quad f \text{ 满足容量与守恒约束}

若只需最小费用而不强求最大流，则给定目标流量 $$d$$ ，约束 $\sum f(s,v) = d$ 。

与线性规划的关系

最小费用最大流可以写成线性规划：

\begin{aligned} \min\ & \sum_{(u,v)\in E} a(u,v) \cdot f(u,v) \\ \text{s.t. } & f(u,v) \leq c(u,v) && \forall (u,v) \in E \\ & f(u,v) = -f(v,u) && \forall (u,v) \in E \\ & \sum_{w \in V} f(u,w) = 0 && \forall u \neq s,t \\ & \sum_{w \in V} f(s,w) = d,\ \sum_{w \in V} f(w,t) = d \end{aligned}

这是线性规划的特殊形式，可以用网络单纯形法（network simplex）高效求解——比通用 LP 求解器快几个数量级。

最短增广路径算法

最小费用最大流的最自然算法是对偶于 Ford-Fulkerson 的最短增广路径算法（successive shortest path）：

在残余图上用 Bellman-Ford（支持负费用边）找到从 $$s$$ 到 $$t$$ 的最短路径
沿该路径增广尽可能多的流量
重复，直到达到目标流量

若所有费用非负，则可用 Dijkstra 算法（更高效）。

应用连接：二部图的最大权匹配（匈牙利算法）可转化为最小费用最大流问题。具体做法：为每个

$L$

顶点设置供给 1，每个

$R$

顶点设置需求 1，所有匹配边设置单位容量与负权重（费用 = -收益），在所得网络上求最小费用最大流。

Part 8 · 例题与计算

例题与算法演示

例题 1：计算最大流

题目：给定如下流网络，计算从 $$s$$ 到 $$t$$ 的最大流值。

flowchart LR
    s(("s")) -->|"c=10"| v1
    s(("s")) -->|"c=8"| v2
    v1 -->|"c=4"| t(("t"))
    v2 -->|"c=6"| t(("t"))
    v1 -->|"c=5"| v2

解答：

观察：从 $$s$$ 出去的边总容量为 $$10 + 8 = 18$$ ，进入 $$t$$ 的边总容量为 $$4 + 6 = 10$$ ，所以最大流不会超过 10。
验证上界：割 $(S=\{s\}, T=\{v_1,v_2,t\})$ 的容量为 $$c(s,v_1) + c(s,v_2) = 10 + 8 = 18$$ （不是紧上界）。
寻找紧割：割 $(S=\{s, v_1\}, T=\{v_2, t\})$ 的容量为 $$c(v_1,v_2) + c(v_2,t) = 5 + 6 = 11$$ 。
继续优化：割 $(S=\{s, v_1\}, T=\{v_2, t\})$ 的容量为 11，仍可增广。
最小割：割 $(S=\{s, v_1\}, T=\{v_2, t\})$ 中 $v_1 \to t$ 容量为 4， $v_2 \to t$ 容量为 6， $v_1 \to v_2$ 容量为 5。但我们需要从 $$S$$ 到 $$T$$ 的边： $v_1 \to v_2$ (5) 和 $v_1 \to t$ (4)，容量和为 9。
最大流构造：沿 $s \to v_1 \to t$ 发送 4 单位流，沿 $s \to v_2 \to t$ 发送 6 单位流，总流量为 10。

答案：最大流值为 10。

易错点：不能简单地将进入

$t$

的边容量相加就认为是最大流——还需要考虑中间节点是否形成了瓶颈。

例题 2：应用 Ford-Fulkerson 算法

题目：使用 Ford-Fulkerson 方法求解下图的最大流，每步记录残余网络。

flowchart LR
    s(("s")) -->|"c=16"| a
    s(("s")) -->|"c=13"| b
    a -->|"c=10"| c
    a -->|"c=9"| d
    b -->|"c=4"| c
    b -->|"c=3"| d
    c -->|"c=12"| t
    d -->|"c=7"| t
    c -->|"d"| d

解答：

初始化：所有边流量为 0，残余网络等于原网络。
增广路径 1： $s \to a \to c \to t$ ，瓶颈容量为 $\min(16, 10, 12) = 10$ 。增广后流量 = 10。
增广路径 2： $s \to b \to d \to t$ ，瓶颈容量为 $\min(13, 3, 7) = 3$ 。增广后流量 = 13。
增广路径 3： $s \to a \to d \to t$ ，在残余网络中检查： $s \to a$ 剩余 6， $a \to d$ 剩余 9， $d \to t$ 剩余 4，瓶颈为 $\min(6, 9, 4) = 4$ 。增广后流量 = 17。
增广路径 4： $s \to b \to c \to t$ ，在残余网络中检查： $s \to b$ 剩余 10， $b \to c$ 剩余 4， $c \to t$ 剩余 2，瓶颈为 $\min(10, 4, 2) = 2$ 。增广后流量 = 19。
检查残余网络：从 $$s$$ 可达顶点为 $\{s, a, b\}$ ， $$t$$ 不可达。算法终止。

答案：最大流值为 19，最小割为 $(S=\{s,a,b\}, T=\{c,d,t\})$ 。

易错点：在寻找增广路径时，不仅要考虑正向边，还要考虑反向边（用于"撤销"之前推送的流量）。第 3 步和第 4 步增广都利用了之前建立的反向边。

例题 3：应用 Hall 婚配定理

题目：某公司有 4 名员工 $\{E_1, E_2, E_3, E_4\}$ 和 5 项任务 $\{T_1, T_2, T_3, T_4, T_5\}$ 。每名员工能完成的任务集合如下，问是否可以实现完美匹配？

$$E_1$$ : $\{T_1, T_2, T_3\}$
$$E_2$$ : $\{T_2, T_3, T_4\}$
$$E_3$$ : $\{T_3, T_4, T_5\}$
$$E_4$$ : $\{T_4, T_5\}$

解答：

根据 Hall 婚配定理，需要检查任意 $X \subseteq \{E_1, E_2, E_3, E_4\}$ 是否满足 $|N(X)| \geq |X|$ 。

单点检查：每名员工的邻居数至少为 3 或 2，均 $\geq 1$ 。
两点组合：
- $\{E_1, E_2\}$ : $N = \{T_1, T_2, T_3, T_4\}$ ， $|N| = 4 \geq 2$ ✓
- $\{E_2, E_3\}$ : $N = \{T_2, T_3, T_4, T_5\}$ ， $|N| = 4 \geq 2$ ✓
- $\{E_3, E_4\}$ : $N = \{T_3, T_4, T_5\}$ ， $|N| = 3 \geq 2$ ✓
三点组合：
- $\{E_1, E_2, E_3\}$ : $N = \{T_1, T_2, T_3, T_4, T_5\}$ ， $|N| = 5 \geq 3$ ✓
- $\{E_1, E_2, E_4\}$ : $N = \{T_1, T_2, T_3, T_4, T_5\}$ ， $|N| = 5 \geq 3$ ✓
- $\{E_1, E_3, E_4\}$ : $N = \{T_1, T_2, T_3, T_4, T_5\}$ ， $|N| = 5 \geq 3$ ✓
- $\{E_2, E_3, E_4\}$ : $N = \{T_2, T_3, T_4, T_5\}$ ， $|N| = 4 \geq 3$ ✓
全集检查： $N(\{E_1, E_2, E_3, E_4\}) = \{T_1, T_2, T_3, T_4, T_5\}$ ， $|N| = 5 \geq 4$ ✓

所有条件满足，故存在完美匹配。

答案：存在完美匹配。例如： $E_1 \to T_1,\ E_2 \to T_2,\ E_3 \to T_3,\ E_4 \to T_4$ 。

Part 9 · 应用场景

网络流与匹配的实际应用

通信网络路由优化

互联网自治域间路由（BGP 层面的流量工程）中，可将网络建模为流网络，容量为链路带宽。最大流算法用于评估网络的单点故障脆弱性（最小割对应最关键的链路组），以及规划多路径路由使负载均衡。

图像分割（Graph Cut）

计算机视觉中的交互式图像分割（Boykov & Jolly, 2001）将像素建模为图节点，添加源点（前景）和汇点（背景），边权重反映像素属于前景/背景的代价。通过最大流最小割找到能量函数的最小化解——割集恰好对应于像素的二分类。

任务分配与指派问题

在人员-任务匹配问题中，若有数量约束（每个工人最多完成 $$c_i$$ 个任务），可构造流网络：源点→工人（容量 $$c_i$$ ），工人→任务（容量 1），任务→汇点（容量 1），求最大流即最大匹配人数。带权版本（收益矩阵）使用最小费用最大流或匈牙利算法。

运动规划

多机器人路径规划（multi-agent path finding）中，最大流用于评估地图中各通道的瓶颈，规划避免冲突的路线。在网格地图上，可将每个格子视为节点，通过最大流判断是否能同时容纳所有机器人。

复习速查

核心定义：流网络 $$G=(V,E,s,t,c)$$ ，流函数满足容量约束和守恒约束，流的值为源点总发出量。
关键定理：最大流最小割定理 $\max_f |f| = \min_{(S,T)} c(S,T)$ ，König 定理 $\nu(G) = \tau(G)$ ，Hall 婚配定理。
核心算法：
- Ford-Fulkerson： $O(E \cdot F)$ ，容量为整数时正确
- Edmonds-Karp： $$O(VE^2)$$ ，使用 BFS 找最短路径
- Dinic： $$O(V^2E)$$ ，阻塞流分层
- Hopcroft-Karp： $O(E\sqrt{V})$ ，用于二部图最大匹配
重要技巧：残余图构建、反向边用于"撤销"、层次图加速阻塞流搜索。

参考来源

Ford, L. R., & Fulkerson, D. R. (1956). Maximal flow through a network. Canadian Journal of Mathematics, 8, 399-404.
Kuhn, H. W. (1955). The Hungarian method for the assignment problem. Naval Research Logistics Quarterly, 2, 83-97.
Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press. Ch. 26.
Ahuja, R. K., Magnanti, T. L., & Orlin, J. B. (1993). Network Flows: Theory, Algorithms, and Applications. Prentice-Hall.
Dinic, E. A. (1970). Algorithm for solution of a problem of maximum flow in a network with power estimation. Doklady Akademii Nauk SSSR, 11, 1277-1280.
Edmonds, J., & Karp, R. M. (1972). Theoretical improvements in algorithmic efficiency for network flow problems. JACM, 19(2), 248-264.
Hopcroft, J. E., & Karp, R. M. (1973). An $n^{5/2}$ algorithm for maximum matchings in bipartite graphs. SIAM J. Comput., 2(4), 225-231.
Kőnig, D. (1931). Über Graphen und ihre Anwendung auf Determinantentheorie und Invariantentheorie. Mathematische Annalen.
Boykov, Y., Veksler, O., & Zabih, R. (2001). Fast approximate energy minimization via graph cuts. IEEE TPAMI, 23(11), 1222-1239.
Goldberg, A. V., & Tarjan, R. E. (1989). Finding minimum-cost circulations by canceling negative cycles. JACM, 36(4), 873-886.