查看“︁最小割”︁的源代码

{{NoteTA
|G1=IT
}}

[[File:Min cut example.svg|thumb|图片上是一张图及其两个割：红色点线标出了一个包含三条边的割，绿色划线则表示了这张图的一个最小割（包含两条边）<ref>{{Cite web|url = http://www.cs.dartmouth.edu/~ac/Teach/CS105-Winter05/Notes/loomis-scribe.ps|title = 4 Min-Cut Algorithms|date = |accessdate = |website = |publisher = |last = |first = |archive-date = 2016-08-05|archive-url = https://web.archive.org/web/20160805175118/http://www.cs.dartmouth.edu/~ac/Teach/CS105-Winter05/Notes/loomis-scribe.ps|dead-url = no}}</ref>]]
在[[图论]]中，去掉其中所有边能使一张[[网络流]]图不再[[连通图|连通]]（即分成两个[[子图]]）的边集称为图的[[割]]（{{lang-en|cut}}），一张图上最小的割称为'''最小割'''（{{lang-en|minimum cut}}或{{lang|en|min-cut}}）。与最小割相关的问题称最小割问题（{{lang-en|minimum cut problem}}或{{lang|en|min-cut problem}}），其变体包括带边权、[[有向图]]、包含源点与汇点（简称有源汇），以及将原网络分为多于两个子图等问题。其中，带边权的最小割问题允许有负权边，可通过对所有边权取相反数简单地转化为[[最大流]]问题求解。

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

对无源汇最小割问题加以推广，可以得到{{link-en|最小k割问题|minimum k-cut|最小{{mvar|k}}割问题}}，即将图分为至少{{mvar|k}}个子图的最小割问题。对于一个确定的{{mvar|k}}，这个问题可以在多项式时间内完成，虽然算法在{{mvar|k}}较大时并不理想。<ref>{{cite journal |title=A Polynomial Algorithm for the k-cut Problem for Fixed k |url=https://pubsonline.informs.org/doi/pdf/10.1287/moor.19.1.24}}</ref>

== 有源汇的最小割问题 ==
在网络图中，流产生的起点（[[度 (图论)|入度]]为0）称作源点（{{lang-en|source}}，用<math>s</math>表示），接受流的终点（[[度 (图论)|出度]]为0）称作汇点（{{lang-en|sink}}，用<math>t</math>表示）。

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

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

将有源汇最小割问题加以推广可得到k端点最小割问题（{{lang-en|{{mvar|k}}-terminal cut}}或{{lang|en|multiterminal cut}}），该问题即使在<math>k=3</math>时也是[[NP困难]]的。<ref>{{cite journal |title=The Complexity of Multiterminal Cuts |url=https://pdfs.semanticscholar.org/17ff/d84480267785c6a9987211a8a86a58cea1a9.pdf |journal= |access-date=2020-11-24 |archive-date=2018-12-25 |archive-url=https://web.archive.org/web/20181225130005/https://pdfs.semanticscholar.org/17ff/d84480267785c6a9987211a8a86a58cea1a9.pdf |dead-url=no }}</ref>

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

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

== 参见 ==
*[[最大割問題]]
*[[最大流最小割定理]]
*{{link-en|点割集|Vertex separator}}

== 参考文献 ==
{{Reflist}}

{{算法}}

[[分类:网络流]]