最小割

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

无源汇的最小割问题
对于带有边权的无向图，其最小割问题可以在多项式时间内通过求解。在无边权的特殊情况下，一种高效的随机化算法可用于求解最小割。在这种情况下，最小割等于图的。

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

有源汇的最小割问题
在网络图中，流产生的起点（入度为0）称作源点（，用s表示），接受流的终点（出度为0）称作汇点（，用t表示）。

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

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

将有源汇最小割问题加以推广可得到k端点最小割问题（或），该问题即使在k=3时也是NP困难的。

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

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

参见
*最大割問題
*最大流最小割定理
*

参考文献