割邊

定義

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

我們可以用下邊的例子說明：

對於該連通圖，割邊有V₃V_4，V₄V₅兩個；其他邊均不是割邊。

若對圖G中每對不同的頂點都存在某條過這兩個點的同類，則稱圖G是連通的。

如下邊的例子：

圖1，圖2都是連通的；圖3和圖4都是不連通的。

若圖G的任意兩個點都是鄰接的（及存在一條邊將這兩個點連線起來），則稱G是完全圖。

如下圖中：

圖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）。所謂極小，是指一個鍵的任意真子集都不是邊割。圖中一個邊子集是該圖的邊割若且唯若它是該圖中一些鍵的不交並。

在有向圖中也可以定義類似的概念。設 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），通常記作

。