-
割邊
鎖定
假設有連通圖G,e是其中一條邊,如果G-e是不連通的,則邊e是圖G的一條割邊。此情形下,G-e必包含兩個連通分支。
- 中文名
- 割邊
- 外文名
- cut edge
- 適用領域
- 數理科學
- 定 義
- 假設有連通圖G,e是其中一條邊,如果G-e是不連通的,則邊e是圖G的一條割邊。
割邊定義
假設有連通圖G,e是其中一條邊,如果G-e是不連通的,則邊e是圖G的一條割邊。此情形下,G-e必包含兩個連通分支。
我們可以用下邊的例子説明:
對於該連通圖,割邊有V3V4,V4V5兩個;其他邊均不是割邊。
割邊連通圖
若對圖G中每對不同的頂點都存在某條過這兩個點的同類,則稱圖G是連通的。
如下邊的例子:
圖1,圖2都是連通的;圖3和圖4都是不連通的。
割邊完全圖
若圖G的任意兩個點都是鄰接的(及存在一條邊將這兩個點連接起來),則稱G是完全圖。
如下圖3中:
圖1不連通;圖2,圖3是連通的,但不完全;圖4是完全圖。
定理:若圖G是完全的,則G一定是連通的。
割邊邊割
[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)。所謂極小,是指一個鍵的任意真子集都不是邊割。圖中一個邊子集是該圖的邊割當且僅當它是該圖中一些鍵的不交併。