查看“︁割”︁的源代码

[[图论]]中，'''割'''（cut）是将图的[[顶点 (图论)|顶点]]分为两[[不交集|不交子集]]的[[集合划分|划分]]。<ref name="networkx.algorithms.cuts.cut_size">{{cite web | title=NetworkX 2.6.2 documentation | website=networkx.algorithms.cuts.cut_size | url=https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.cuts.cut_size.html#networkx.algorithms.cuts.cut_size | access-date=2021-12-10 | quote=A cut is a partition of the nodes of a graph into two sets. The cut size is the sum of the weights of the edges “between” the two sets of nodes. | archive-date=2021-11-18 | archive-url=https://web.archive.org/web/20211118095812/https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.cuts.cut_size.html#networkx.algorithms.cuts.cut_size | url-status=live }}</ref>割确定了'''割集'''，是两端分别在两子集中的边集，称这些边'''跨过'''（cross）了割。[[连通图]]中，割集唯一确定一个割，识别割有时是通过割集，而非顶点划分。

[[网络流]]中，'''s–t割'''指使得源与汇不在同一子集的割，其割集只含源一侧到汇一侧的边。s-t割的容量（capacity）定义为割集中所有边的容量和。

==定义==
'''割'''<math>C=(S,\ T)</math>是将图<math>G=(V,\ E)</math>的顶点''V''分为两子集''S''、''T''的划分。
割<math>C=(S,\ T)</math>的'''割集'''是一端点位于''S''、另一端点位于''T''的边的集合<math>\{(u,\ v)\in E|u\in S,\ v\in T\}</math>。
令''s''、''t''是图''G''的两顶点，则'''{{mvar|s–t}}割'''是使得''s''属于''S''、''t''属于''T''的割。

在无权无向图中，割的大小（size）或权（weight）是跨过割的边数。加权图中，割的'''值'''（value）或'''权'''（weight）是跨过割的边的权重之和。

'''键'''（bond）是[[真子集]]中没有其他割集的割集。

==最小割==
[[File:Min-cut.svg|thumb|right|一个最小割。]]
{{main|最小割}}
最小割的大小或权不大于其他割。右图展示了最小割，其大小为2，且没有大小为1的割，因为这张图没有[[桥 (图论)|桥]]。

[[最大流最小割定理]]指出，最大[[网络流]]等于分割了源汇的最小割的割边权重之和。有一些[[时间复杂度#多项式时间|多项式时间]]方法可以解决最小割问题，最知名的是[[埃德蒙兹-卡普算法]]。<ref>{{citation
 | last1 = Cormen | first1 = Thomas H. | author1-link = Thomas H. Cormen
 | last2 = Leiserson | first2 = Charles E. | author2-link = Charles E. Leiserson
 | last3 = Rivest | first3 = Ronald L. | author3-link = Ronald L. Rivest
 | last4 = Stein | first4 = Clifford | author4-link = Clifford Stein
 | edition = 2nd
 | isbn = 0-262-03293-7
 | page = 563,655,1043
 | publisher = MIT Press and McGraw-Hill
 | title = [[Introduction to Algorithms]]
 | year = 2001}}.</ref>

==最大割==
[[File:Max-cut.svg|thumb|right|一个最大割。]]
{{main|最大割}}
最大割的大小或权不小于其他割。右图展示了最大割，其大小为5，且没有大小为6的割（即边的总数，写作<math>|E|</math>），因为这张图不是[[二分图]]（有[[循环图#术语|奇环]]）。

一般来说，找最大割是很难计算的。<ref>{{citation
 | last1 = Garey
 | first1 = Michael R.
 | author1-link = Michael R. Garey
 | last2 = Johnson
 | first2 = David S.
 | author2-link = David S. Johnson
 | isbn = 0-7167-1045-5
 | at = [https://archive.org/details/computersintract0000gare/page/ A2.2: ND16, p.&nbsp;210]
 | publisher = W.H. Freeman
 | title = [[Computers and Intractability: A Guide to the Theory of NP-Completeness]]
 | year = 1979
 }}.</ref>
最大割问题是[[卡普的二十一个NP-完全问题]]之一，<ref>{{citation
 | last = Karp | first = R. M. | author-link = Richard Karp
 | editor1-last = Miller | editor1-first = R. E.
 | editor2-last = Thacher | editor2-first = J. W.
 | contribution = Reducibility among combinatorial problems
 | location = New York
 | pages = 85–103
 | publisher = Plenum Press
 | title = Complexity of Computer Computation
 | year = 1972}}.</ref>
也是[[APX问题]]之一，这是说除非P&nbsp;=&nbsp;NP，否则不会存在多项式时间复杂度的近似方法。<ref>{{citation
 | last1 = Khot
 | first1 = S.
 | author1-link = Subhash Khot
 | last2 = Kindler
 | first2 = G.
 | last3 = Mossel
 | first3 = E.
 | last4 = O’Donnell
 | first4 = R.
 | contribution = Optimal inapproximability results for MAX-CUT and other two-variable CSPs?
 | pages = 146–154
 | title = Proceedings of the 45th IEEE Symposium on Foundations of Computer Science
 | contribution-url = https://www.cs.cmu.edu/~odonnell/papers/maxcut.pdf
 | year = 2004
 | access-date = 2019-08-29
 | archive-date = 2019-07-15
 | archive-url = https://web.archive.org/web/20190715031206/http://www.cs.cmu.edu/~odonnell/papers/maxcut.pdf
 | url-status = live
 }}.</ref>
不过，可以用[[半正定规划]]，将其逼近到恒定的[[近似算法#近似比|近似比]]。<ref>{{citation
 | last1 = Goemans | first1 = M. X. | author1-link = Michel Goemans
 | last2 = Williamson | first2 = D. P. | author2-link = David P. Williamson
 | doi = 10.1145/227683.227684
 | issue = 6
 | journal = [[Journal of the ACM]]
 | pages = 1115–1145
 | title = Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
 | volume = 42
 | year = 1995| doi-access = free
 }}.</ref>

注意从[[线性规划]]的意义上讲，最小割与最大割问题虽然可以通过改换[[损失函数|目标函数]]的min、max使其变为另一个问题，但不是[[线性规划#对偶|对偶]]的：最小割问题的对偶实际上是最大流问题。<ref>{{citation
 | last = Vazirani | first = Vijay V. | author-link = Vijay Vazirani
 | isbn = 3-540-65367-8
 | pages = 97–98
 | publisher = Springer
 | title = Approximation Algorithms
 | year = 2004}}.</ref>

== 最疏割 ==
'''最疏割'''（sparsest cut）使跨过割的边数对割的较小一侧的顶点数之比最小，目标函数偏向稀疏（跨过割的边更少）与平衡（接近二分）。这是NP问题，已知的最佳近似算法是<math>O(\sqrt{\log n})</math>近似，见{{Harvtxt|Arora|Rao|Vazirani|2009}}。<ref>{{citation
 | last1 = Arora | first1 = Sanjeev | author1-link = Sanjeev Arora
 | last2 = Rao | first2 = Satish
 | last3 = Vazirani | first3 = Umesh | author3-link = Umesh Vazirani
 | doi = 10.1145/1502793.1502794
 | issue = 2
 | journal = J. ACM
 | pages = 1–37
 | publisher = ACM
 | title = Expander flows, geometric embeddings and graph partitioning
 | volume = 56
 | year = 2009| s2cid = 263871111 }}.</ref>

== 割空间==
无向图的所有割的族（family）称作图的'''割空间'''（cut space），在算术模2的二元[[有限域]]上形成[[向量空间]]，以两割集的[[对称差]]为向量加法，是[[环空间]]的[[正交补]]。<ref name="gy">{{citation
 | last1 = Gross | first1 = Jonathan L.
 | last2 = Yellen | first2 = Jay
 | contribution = 4.6 Graphs and Vector Spaces
 | edition = 2nd
 | isbn = 9781584885054
 | pages = 197–207
 | publisher = CRC Press
 | title = Graph Theory and Its Applications
 | url = https://books.google.com/books?id=-7Q_POGh-2cC&pg=PA197
 | year = 2005}}.</ref><ref name="diestel">{{citation
 | last = Diestel | first = Reinhard
 | contribution = 1.9 Some linear algebra
 | pages = 23–28
 | publisher = Springer
 | series = Graduate Texts in Mathematics
 | title = Graph Theory
 | url = https://books.google.com/books?id=eZi8AAAAQBAJ&pg=PA23
 | volume = 173
 | year = 2012}}.</ref>若给边赋予正权重，割空间的最小权[[基 (线性代数)|基]]可由与图同顶点集的[[树 (图论)|树]]描述，称作[[最小割树]]。<ref>{{citation
 | last1 = Korte | first1 = B. H. | author1-link = Bernhard Korte
 | last2 = Vygen | first2 = Jens
 | contribution = 8.6 Gomory–Hu Trees
 | isbn = 978-3-540-71844-4
 | pages = 180–186
 | publisher = Springer
 | series = Algorithms and Combinatorics
 | title = Combinatorial Optimization: Theory and Algorithms
 | volume = 21
 | year = 2008}}.</ref>树的边都关联于原图的键，两节点''s''、''t''之间的最小割也就是与树中''s''到''t''的路径相关联的键中权最小的键。

== 另见 ==
* [[连通性 (图论)]]
* [[裂 (图论)]]
* [[顶点割]]
* [[桥 (图论)]]
* [[割宽]]

== 参考 ==
{{reflist|30em}}
{{图论}}
[[Category:图的连通性]]
[[Category:组合优化]]