割
圖論中，割（cut）是將圖的頂點分為兩不交子集的劃分。[1]割確定了割集，是兩端分別在兩子集中的邊集，稱這些邊跨過（cross）了割。連通圖中，割集唯一確定一個割，識別割有時是通過割集，而非頂點劃分。
網絡流中，s–t割指使得源與匯不在同一子集的割，其割集只含源一側到匯一側的邊。s-t割的容量（capacity）定義為割集中所有邊的容量和。
定義
割是將圖的頂點V分為兩子集S、T的劃分。 割的割集是一端點位於S、另一端點位於T的邊的集合。 令s、t是圖G的兩頂點，則s–t割是使得s屬於S、t屬於T的割。
在無權無向圖中，割的大小（size）或權（weight）是跨過割的邊數。加權圖中，割的值（value）或權（weight）是跨過割的邊的權重之和。
鍵（bond）是真子集中沒有其他割集的割集。
最小割
最小割的大小或權不大於其他割。右圖展示了最小割，其大小為2，且沒有大小為1的割，因為這張圖沒有橋。
最大流最小割定理指出，最大網絡流等於分割了源匯的最小割的割邊權重之和。有一些多項式時間方法可以解決最小割問題，最知名的是埃德蒙茲-卡普算法。[2]
最大割
最大割的大小或權不小於其他割。右圖展示了最大割，其大小為5，且沒有大小為6的割（即邊的總數，寫作），因為這張圖不是二分圖（有奇環）。
一般來說，找最大割是很難計算的。[3] 最大割問題是卡普的二十一個NP-完全問題之一，[4] 也是APX問題之一，這是說除非P = NP，否則不會存在多項式時間複雜度的近似方法。[5] 不過，可以用半正定規劃，將其逼近到恆定的近似比。[6]
注意從線性規劃的意義上講，最小割與最大割問題雖然可以通過改換目標函數的min、max使其變為另一個問題，但不是對偶的：最小割問題的對偶實際上是最大流問題。[7]
最疏割
最疏割（sparsest cut）使跨過割的邊數對割的較小一側的頂點數之比最小，目標函數偏向稀疏（跨過割的邊更少）與平衡（接近二分）。這是NP問題，已知的最佳近似算法是近似，見Arora, Rao & Vazirani (2009)。[8]
割空間
無向圖的所有割的族（family）稱作圖的割空間（cut space），在算術模2的二元有限域上形成向量空間，以兩割集的對稱差為向量加法，是環空間的正交補。[9][10]若給邊賦予正權重，割空間的最小權基可由與圖同頂點集的樹描述，稱作最小割樹。[11]樹的邊都關聯於原圖的鍵，兩節點s、t之間的最小割也就是與樹中s到t的路徑相關聯的鍵中權最小的鍵。
另見
參考
- ^ NetworkX 2.6.2 documentation. networkx.algorithms.cuts.cut_size. [2021-12-10]. （原始內容存檔於2021-11-18）.
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.
- ^ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford, Introduction to Algorithms 2nd, MIT Press and McGraw-Hill: 563,655,1043, 2001, ISBN 0-262-03293-7.
- ^ Garey, Michael R.; Johnson, David S., Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, A2.2: ND16, p. 210, 1979, ISBN 0-7167-1045-5.
- ^ Karp, R. M., Reducibility among combinatorial problems, Miller, R. E.; Thacher, J. W. (編), Complexity of Computer Computation, New York: Plenum Press: 85–103, 1972.
- ^ Khot, S.; Kindler, G.; Mossel, E.; O』Donnell, R., Optimal inapproximability results for MAX-CUT and other two-variable CSPs? (PDF), Proceedings of the 45th IEEE Symposium on Foundations of Computer Science: 146–154, 2004 [2019-08-29], （原始內容存檔 (PDF)於2019-07-15）.
- ^ Goemans, M. X.; Williamson, D. P., Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, Journal of the ACM, 1995, 42 (6): 1115–1145, doi:10.1145/227683.227684
.
- ^ Vazirani, Vijay V., Approximation Algorithms, Springer: 97–98, 2004, ISBN 3-540-65367-8.
- ^ Arora, Sanjeev; Rao, Satish; Vazirani, Umesh, Expander flows, geometric embeddings and graph partitioning, J. ACM (ACM), 2009, 56 (2): 1–37, S2CID 263871111, doi:10.1145/1502793.1502794.
- ^ Gross, Jonathan L.; Yellen, Jay, 4.6 Graphs and Vector Spaces, Graph Theory and Its Applications 2nd, CRC Press: 197–207, 2005, ISBN 9781584885054.
- ^ Diestel, Reinhard, 1.9 Some linear algebra, Graph Theory, Graduate Texts in Mathematics 173, Springer: 23–28, 2012.
- ^ Korte, B. H.; Vygen, Jens, 8.6 Gomory–Hu Trees, Combinatorial Optimization: Theory and Algorithms, Algorithms and Combinatorics 21, Springer: 180–186, 2008, ISBN 978-3-540-71844-4.
