最小割

在图论中，去掉其中所有边能使一张网络流图不再连通（即分成两个子图）的边集称为图的割（英语：cut），一张图上最小的割称为最小割（英语：minimum cut或min-cut）。与最小割相关的问题称最小割问题（英语：minimum cut problem或min-cut problem），其变体包括带边权、有向图、包含源点与汇点（简称有源汇），以及将原网络分为多于两个子图等问题。其中，带边权的最小割问题允许有负权边，可通过对所有边权取相反数简单地转化为最大流问题求解。

图片上是一张图及其两个割：红色点线标出了一个包含三条边的割，绿色划线则表示了这张图的一个最小割（包含两条边）^[1]

无源汇的最小割问题

对于带有边权的无向图，其最小割问题可以在多项式时间内通过Stoer-Wagner算法（英语：Stoer-Wagner algorithm）求解。在无边权的特殊情况下，一种高效的随机化算法Karger算法（英语：Karger's algorithm）可用于求解最小割。在这种情况下，最小割等于图的边连通度（英语：k-edge-connected graph）。

对无源汇最小割问题加以推广，可以得到最小k割问题（英语：minimum k-cut），即将图分为至少k个子图的最小割问题。对于一个确定的k，这个问题可以在多项式时间内完成，虽然算法在k较大时并不理想。^[2]

有源汇的最小割问题

在网络图中，流产生的起点（入度为0）称作源点（英语：source，用${\displaystyle s}$表示），接受流的终点（出度为0）称作汇点（英语：sink，用${\displaystyle t}$表示）。

在带有边权的有向网络流中，最小割被定义为切断所有边后能使源汇不连通且边权和最小的边集。根据最大流最小割定理，此时的最小割边权和等于网络上能从源点流到汇点的最大流量，或简称“最小割等于最大流”。

在带有边权的无向网络流中，任意点对的最小割则被定义为切断所有边后能使这两个点不连通且边权和最小的边集，且可用最小割树（英语：Gomory–Hu tree）求出。该数据结构以一棵带边权的树表示了所有源-汇点对（或${\displaystyle s}$-${\displaystyle t}$对），可以以${\displaystyle (|V|-1)}$次最大流计算求解。

将有源汇最小割问题加以推广可得到k端点最小割问题（英语：k-terminal cut或multiterminal cut），该问题即使在${\displaystyle k=3}$时也是NP困难的。^[3]

应用

• 图的拆分（英语：graph partition）是统称，指将图带条件（如平衡割两侧子图大小）拆成多个子图的一系列最优化问题。
• 基于分块的对象分类（英语：Segmentation-based object）可以看作归一化的最小割谱聚类算法应用于图像分割的具体案例。
• 根据最大流最小割定理，双节点的最小割等于最大流，故求解最小割时也会使用最大流算法求解。

计数

若一张图带有${\displaystyle n}$个节点，则它上面最小割数有${\displaystyle {\frac {n(n-1)}{2}}}$的严格上限，因为有${\displaystyle n}$个节点的简单环上有着恰好${\displaystyle {\binom {n}{2}}={\frac {n(n-1)}{2}}}$个不同的最小割（每两条边组成的边集恰好出现一次）。

参见

• 最大割问题
• 最大流最小割定理
• 点割集（英语：Vertex separator）

参考文献

1. 4 Min-Cut Algorithms. （原始内容存档于2016-08-05）.
2. A Polynomial Algorithm for the k-cut Problem for Fixed k.
3. The Complexity of Multiterminal Cuts (PDF). [2020-11-24]. （原始内容存档 (PDF)于2018-12-25）.