最小割计算器

伪代码

最小割并不是直接算出来的。先求最大流，再在残量图上做一次遍历，把割读出来。

最小割(图, s, t):
    先用任意最大流算法跑到饱和

    // S = 在残量图中仍能从 s 抵达的全部结点
    S = 从 s 出发做 BFS/DFS，只走
        残量容量 > 0 的边
    T = 其余全部结点

    割 = { 原图中的边 (u,v) :
           u 属于 S 且 v 属于 T }
    返回该割以及这些边原始容量之和

有两个事实使这一做法成立。任何从 S 跨到 T 的边都必然饱和，否则它的残量容量为正，其端点就会可达并因而落在 S 中。而任何从 T 回到 S 的边都不承载流量。于是跨越割的流量恰好等于割的容量；又因为任何流都不可能超过任何一个割，两者必定同时最优。

分步示例演算

在与最大流示例相同的网络上求最小割：流饱和之后，直接读取残量图。

示例图: 有向容量 S 到 A (10)、S 到 B (10)、A 到 B (2)、A 到 T (4)、B 到 T (9)。

1. 先求最大流. 沿 S 到 A 到 T 增广推送 4，沿 S 到 B 到 T 增广推送 9。总流量为 13，且已不存在增广路径。
2. 查看残量图. S-A 还剩 10 - 4 = 6。S-B 还剩 10 - 9 = 1。A-B 未被使用，2 全部保留。A-T 与 B-T 都已完全饱和，剩余为 0。
3. 用遍历求出 S. 从 S 出发。边 S-A 尚有余量，因此 A 加入 S。从 A 出发，边 A-B 尚有余量，因此 B 加入 S。从 B 出发，唯一的出边 B-T 已饱和。再无其他可达结点，因此 S 就是集合 {S, A, B}。
4. 读出割. T 是剩下的结点集合，也就是 {T}。原图中从 S 跨到 T 的边是容量 4 的 A-T 与容量 9 的 B-T。
5. 验证. 割的容量为 4 + 9 = 13，恰好等于最大流。删去这两条边后，T 就无法从 S 抵达，这证实它确实是一个割。

最小割是边对 A-T 与 B-T，总容量 13，与最大流 13 相等。注意 S-A 与 S-B 的容量合计为 20，它们同样构成一个割，只是更昂贵。瓶颈位于汇点一侧，而残量图上的这次遍历无需在候选割之间搜索就把它找了出来。

复杂度及其来源

时间: 与所采用的最大流算法同阶 · 空间: O(V + E)

提取割本身只是一次 O(V + E) 的图遍历，可以忽略不计。全部开销都在它之前的最大流计算上：用 Edmonds-Karp 是 O(V 乘以 E 的平方)，用 Dinic 是 O(V 的平方乘以 E)。这一点值得说清楚，因为它解释了为什么最小割不被当作一个独立问题来处理。目前没有任何已知方法能比计算最大流更快地渐进求出最小 s-t 割，因为按照最大流最小割定理，二者本就是同一个计算从相反两侧看过去的结果。

何时使用最小割，何时不宜

「割」这个词涵盖了好几个实质不同的问题。选错问题是这里最常见的失误。

常见陷阱

• 遍历原图而不是残量图. 割是由「凭借剩余容量还能到达哪里」定义的，而不是由原始边定义的。在原图上做遍历通常会一直走到汇点，结果得不到任何割。这是最常见的实现错误。
• 把最小 s-t 割与全局最小割混为一谈. s-t 割分离的是两个指定结点。全局最小割则把图分成任意两个非空部分，需要 Stoer-Wagner 或 Karger。解错了问题，等于给一个无人提出的问题交出了一份正确答案。
• 以为最小割唯一. 它的容量是唯一的，边集往往不是。多个不同的割可能具有相同的最小容量，你最终得到哪一个取决于所找到的流。测试应当检查容量，而不是某一份具体的边列表。
• 把从 T 回到 S 的边也算进去. 只有从 S 一侧跨到 T 一侧的边才计入割的容量。反向边跨越割时不承载任何流量，不作贡献。把它们算进去会让答案超过最大流，也就破坏了该定理。
• 忘记容量必须非负. 最大流与最小割的对应关系以非负容量为前提。负容量并不是有意义的吞吐概念，缺了这个前提，关于残量图的整套推理就会崩塌。

常见问题

图中的最小割是什么？

割是把结点分成两个集合的一种划分，一侧含源点、另一侧含汇点，其容量是所有从源点一侧跨到汇点一侧的边的容量之和。最小割就是最便宜的这样一种划分，它指出了瓶颈所在：为切断源点与汇点之间的联系所需删去的代价最低的一组边。

如何求最小割？

先算出最大流，然后从源点出发在残量图上做一次 BFS 或 DFS，只沿仍有剩余容量的边前进。能够到达的结点构成割的一侧，其余结点构成另一侧，跨在两者之间的原始边就是最小割。

什么是最大流最小割定理？

它指出从源点到汇点的最大流量始终等于分离二者的最小割的容量。任何流都不可能超过任何一个割，因为一切都必须跨过它；而当不再存在增广路径时，残量图中可达的结点集合恰好定义了一个割，其容量正好被该流达到，于是两个数值相等。

最小割和全局最小割有什么区别？

最小 s-t 割分离两个指定的结点，通过最大流求得。全局最小割则在不预先指定任何结点的情况下把图分成任意两个非空部分，需要用 Stoer-Wagner 或 Karger 求解。全局割可能比任何一个特定的 s-t 割都便宜得多。

最小割有什么用途？

用于识别网络脆弱点与单点故障；用于图像分割，其中像素是结点、割把前景与背景分开；用于聚类与社区发现；用于项目选择问题；以及用于通信或交通基础设施的可靠性分析。