1. 概述
本文将介绍如何通过计算图的最大流来求解图的最小割。我们会讲解最大流与最小割之间的关系，介绍经典的 Ford-Fulkerson 算法，并通过一个示例演示其运行过程，最后分析其时间复杂度。
2. 图中的最小割
在图论中，一个割（Cut）是指一组边，移除这些边后可以将图分为两个互不相交的子图。割分为最大割和最小割。我们关注的是最小割：即边权值之和最小的割。
✅ 定义：
图的最小割是使得图被分割为两个部分的边集，其边权之和最小。
示例：
如下图所示：
图中 CUT 3 是一个最小割，它移除了边 E8 和 E9，这两个边的总权重是所有可能割中最小的。
3. 图中的最大流
最大流问题的核心在于：在给定源点和汇点的图中，找出从源点到汇点可以流过的最大流量。
✅ 关键点：
- 每条边都有一个容量（Capacity）。
- 流量必须满足容量限制。
- 满足流守恒（Kirchhoff 定律）：进入节点的总流量等于离开节点的总流量。
示例图：
该图中，边的流量为 [3, 3, -2, 2, 1]，满足流守恒条件。
4. 最大流-最小割定理
这是网络流理论中最重要的定理之一。
✅ 定理内容：
从源点到汇点的最大流等于将源点和汇点分离的最小割的容量。
换句话说，最大流的值等于最小割的总权重。
这个定理可以通过 Ford-Fulkerson 算法来验证和实现。
5. Ford-Fulkerson 算法
5.1 核心概念
Ford-Fulkerson 算法基于以下三个核心概念：
| 概念 | 说明 |
|---|---|
| 残差网络（Residual Network） | 表示当前图中还可以增加多少流 |
| 增广路径（Augmented Path） | 从源点到汇点的一条路径，可以继续增加流 |
| 流量图（Netflow Graph） | 展示每条边当前的流量和剩余容量 |
5.2 算法思路
- 初始化所有边的流量为 0。
- 在残差图中查找增广路径。
- 找到后，沿该路径增加流量。
- 重复步骤 2 和 3，直到无法找到新的增广路径。
5.3 伪代码
algorithm FordFulkerson(G, s, t):
// INPUT
// G = a directed connected graph
// s = source node
// t = sink node
// OUTPUT
// Maximum flow of the graph G
for edge (u, v) in E(G):
f(u, v) <- 0
f(v, u) <- 0
while there exists an augmenting path p in G_f:
c_f(p) <- min {c_f(u, v): (u, v) in p} // residual capacity
for edge (u, v) in p:
f(u, v) <- f(u, v) + c_f(p)
f(v, u) <- -f(u, v)
6. 示例演示
我们以一个有向图为例，运行 Ford-Fulkerson 算法：
步骤说明：
- 选择路径
a-b-d-f，最小容量为 4。 - 选择路径
a-b-e-f，最小容量为 3。 - 选择路径
a-c-f，最小容量为 5。 - 选择路径
a-c-e-f，最小容量为 1。
最终，残差图中无法再找到从源点 a 到汇点 f 的路径，算法终止。
结果验证：
- 汇点
f的总出流为 13 - 源点
a的总入流也为 13
✅ 验证了最大流等于最小割的定理。
因此，该图的最小割值为 13。
7. 时间复杂度分析
Ford-Fulkerson 算法的效率取决于如何寻找增广路径。
| 方法 | 时间复杂度 |
|---|---|
| BFS | O(E × f*) |
| DFS | O(E × f*) |
其中：
E是图中边的数量f*是最大流值
⚠️ 注意：如果使用 BFS 实现（即 Edmonds-Karp 算法），则时间复杂度为 O(V × E²)，可在多项式时间内完成。
8. 小结
本文重点讲解了：
- 最小割的定义与作用
- 最大流的概念及其守恒性
- 最大流-最小割定理
- Ford-Fulkerson 算法原理与实现
- 示例演示与时间复杂度分析
通过最大流算法，我们可以高效地求解图的最小割问题，这在网络优化、社区划分、图像分割等领域都有广泛应用。