热门问题
时间线
聊天
视角
割
将图的顶点分为两不交子集的划分 来自维基百科,自由的百科全书
Remove ads
圖論中,割(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)是真子集中沒有其他割集的割集。
Remove ads
最小割

最小割的大小或權不大於其他割。右圖展示了最小割,其大小為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的路徑相關聯的鍵中權最小的鍵。
另見
參考
Wikiwand - on
Seamless Wikipedia browsing. On steroids.
Remove ads