最小割
在图论中,去掉其中所有边能使一张网络流图不再连通(即分成两个子图)的边集称为图的割(英语:cut),一张图上最小的割称为最小割(英语:minimum cut或min-cut)。与最小割相关的问题称最小割问题(英语:minimum cut problem或min-cut problem),其变体包括带边权、有向图、包含源点与汇点(简称有源汇),以及将原网络分为多于两个子图等问题。其中,带边权的最小割问题允许有负权边,可通过对所有边权取相反数简单地转化为最大流问题求解。
![](http://upload.wikimedia.org/wikipedia/commons/thumb/c/c0/Min_cut_example.svg/220px-Min_cut_example.svg.png)
无源汇的最小割问题
编辑对于带有边权的无向图,其最小割问题可以在多项式时间内通过Stoer-Wagner算法求解。在无边权的特殊情况下,一种高效的随机化算法Karger算法可用于求解最小割。在这种情况下,最小割等于图的边连通度。
对无源汇最小割问题加以推广,可以得到最小k割问题,即将图分为至少k个子图的最小割问题。对于一个确定的k,这个问题可以在多项式时间内完成,虽然算法在k较大时并不理想。[2]
有源汇的最小割问题
编辑在网络图中,流产生的起点(入度为0)称作源点(英语:source,用 表示),接受流的终点(出度为0)称作汇点(英语:sink,用 表示)。
在带有边权的有向网络流中,最小割被定义为切断所有边后能使源汇不连通且边权和最小的边集。根据最大流最小割定理,此时的最小割边权和等于网络上能从源点流到汇点的最大流量,或简称“最小割等于最大流”。
在带有边权的无向网络流中,任意点对的最小割则被定义为切断所有边后能使这两个点不连通且边权和最小的边集,且可用最小割树求出。该数据结构以一棵带边权的树表示了所有源-汇点对(或 - 对),可以以 次最大流计算求解。
将有源汇最小割问题加以推广可得到k端点最小割问题(英语:k-terminal cut或multiterminal cut),该问题即使在 时也是NP困难的。[3]
应用
编辑计数
编辑若一张图带有 个节点,则它上面最小割数有 的严格上限,因为有 个节点的简单环上有着恰好 个不同的最小割(每两条边组成的边集恰好出现一次)。
参见
编辑参考文献
编辑- ^ 4 Min-Cut Algorithms. (原始内容存档于2016-08-05).
- ^ A Polynomial Algorithm for the k-cut Problem for Fixed k.
- ^ The Complexity of Multiterminal Cuts (PDF). [2020-11-24]. (原始内容存档 (PDF)于2018-12-25).