编辑“︁割”︁（章节）

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