開啟主選單

求真百科

割邊假設有連通圖G,e是其中一條邊,如果G-e是不連通的,則邊e是圖G的一條割邊。此情形下,G-e必包含兩個連通分支[1]

[]

目錄

邊割

[edge cut]

設X,Y是圖G 的兩個頂點子集,E[X,Y]是G中所有一個端點屬於 X 另一個端點屬於Y的邊構成的集合。當\X時,稱E[X,Y]是 X 在 G 中的伴隨邊割(associated edge cut),通常記作。不難看出,此時。一般地,圖 G 的邊子集是 G 的邊割當且僅當 G\的連通分支大於 G 的連通分支數。特別地,如果邊割,則稱 e 為 G 的割邊。利用邊割的概念,可以對二部圖作如下的刻畫:圖 G 是二部圖當且僅當 G 中存在頂點子集 X 使得。另外,圖中某個頂點 v 的伴隨邊割稱作平凡邊割(trivial edge cut)。顯然,這是所有與 v 關聯的邊構成的集合。圖中一個極小的非空邊割稱作鍵(bond)。所謂極小,是指一個鍵的任意真子集都不是邊割。圖中一個邊子集是該圖的邊割當且僅當它是該圖中一些鍵的不交並。

在有向圖中也可以定義類似的概念。設 D 是一個有向圖,X,Y 是 D 的兩個頂點子集,A(X,Y)是 D 中所有尾屬於 X 頭屬於 Y 的弧構成的集合。當Y=V(D)\ X 時,稱弧集A(X,Y)是 X 在 D 中的伴隨出割(associated outcut),通常記作。而弧集A(Y,X)稱作 X 在 D 中的伴隨入割(associatde incut),通常記作。

參考來源