图论中,去掉其中所有边能使一张网络流图不再连通(即分成两个子图)的边集称为图的(英语:cut),一张图上最小的割称为最小割(英语:minimum cutmin-cut)。与最小割相关的问题称最小割问题(英语:minimum cut problemmin-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,用 表示),接受流的终点(出度为0)称作汇点(英语:sink,用 表示)。

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

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

将有源汇最小割问题加以推广可得到k端点最小割问题(英语:k-terminal cutmultiterminal cut),该问题即使在 时也是NP困难的。[3]

应用

计数

若一张图带有 个节点,则它上面最小割数有 的严格上限,因为有 个节点的简单环上有着恰好 个不同的最小割(每两条边组成的边集恰好出现一次)。

参见

参考文献

  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).