编辑“︁割”︁（章节）

==最大割==
[[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>