将图的顶点分为两不交子集的划分

圖論中,(cut)是將圖的頂點分為兩不交子集劃分[1]割確定了割集,是兩端分別在兩子集中的邊集,稱這些邊跨過(cross)了割。連通圖中,割集唯一確定一個割,識別割有時是通過割集,而非頂點劃分。

網絡流中,s–t割指使得源與匯不在同一子集的割,其割集只含源一側到匯一側的邊。s-t割的容量(capacity)定義為割集中所有邊的容量和。

定義

 是將圖 的頂點V分為兩子集ST的劃分。 割 割集是一端點位於S、另一端點位於T的邊的集合 。 令st是圖G的兩頂點,則s–t是使得s屬於St屬於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]樹的邊都關聯於原圖的鍵,兩節點st之間的最小割也就是與樹中st的路徑相關聯的鍵中權最小的鍵。

另見

參考

  1. ^ 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. 
  2. ^ 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 .
  3. ^ 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 .
  4. ^ Karp, R. M., Reducibility among combinatorial problems, Miller, R. E.; Thacher, J. W. (編), Complexity of Computer Computation, New York: Plenum Press: 85–103, 1972 .
  5. ^ 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) .
  6. ^ 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  .
  7. ^ Vazirani, Vijay V., Approximation Algorithms, Springer: 97–98, 2004, ISBN 3-540-65367-8 .
  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 .
  9. ^ Gross, Jonathan L.; Yellen, Jay, 4.6 Graphs and Vector Spaces, Graph Theory and Its Applications 2nd, CRC Press: 197–207, 2005, ISBN 9781584885054 .
  10. ^ Diestel, Reinhard, 1.9 Some linear algebra, Graph Theory, Graduate Texts in Mathematics 173, Springer: 23–28, 2012 .
  11. ^ 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 .