热门问题
时间线
聊天
视角

将图的顶点分为两不交子集的划分 来自维基百科,自由的百科全书

Remove ads

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

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

定義

是將圖的頂點V分為兩子集ST的劃分。 割割集是一端點位於S、另一端點位於T的邊的集合。 令st是圖G的兩頂點,則s–t是使得s屬於St屬於T的割。

在無權無向圖中,割的大小(size)或權(weight)是跨過割的邊數。加權圖中,割的(value)或(weight)是跨過割的邊的權重之和。

(bond)是真子集中沒有其他割集的割集。

Remove ads

最小割

Thumb
一個最小割。

最小割的大小或權不大於其他割。右圖展示了最小割,其大小為2,且沒有大小為1的割,因為這張圖沒有

最大流最小割定理指出,最大網絡流等於分割了源匯的最小割的割邊權重之和。有一些多項式時間方法可以解決最小割問題,最知名的是埃德蒙茲-卡普算法[2]

最大割

Thumb
一個最大割。

最大割的大小或權不小於其他割。右圖展示了最大割,其大小為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的路徑相關聯的鍵中權最小的鍵。

另見

參考

Loading related searches...

Wikiwand - on

Seamless Wikipedia browsing. On steroids.

Remove ads