割集

設S是G的邊集E的一個子集，如果在連通圖G中刪除S的所有邊．則G-S不連通，並且不存在S的真子集使G-S不連通，就稱邊集S是圖G的一個割集。

上述定義可以這樣理解，即割集是連通圖G的邊的集合，把這些邊移去將使G分離為兩個部分，但是，如果少移去其中一條邊，圖仍將是連通的。

如圖1中的圖G，邊集{c,d,f,g}是一個割集，其他割集還有{d，e}，{g，h}，{b，c，d)，{b，c，e}等。邊集{a}也是一個割集，而邊集{b．c，d，e}和{b，c，d，h)都不是割集(因為它們分別含有割集作為其真子集)。

在上述有關割集的定義中，有兩點值得注意。其一，割集是一種極小集合，即如果少移去其中一條邊，圖仍將是連通的。例如1中。{b，c，d，e}就不構成一個割集，因為如果少移去一條邊e，仍將使圖分離，但是{b,c,d}是一個割集。其二．對於圖2，用虛線所示的邊集合{a，b，c，d，e}移去後將使圖分離為三個部分，這種邊的集合也不是割集。若一個割集僅含一條邊．則稱該邊為割邊。如圖1中的邊a。一個樹的每一條邊都是它的割邊。 ^[1] 

若一個割集僅含一條邊．則稱該邊為橋或割邊。如圖1中的邊a。一個樹的每一條邊都是它的割邊。 ^[1] 

樹與割集的概念具有互補的性質。樹是連通一個圖的全部頂點的極小邊集合．割集則是把某些頂點與其他頂點分離的極小邊集合，因此它們之間存在着一定的聯繫是不難理解的。下面的定理將充分説明這一點。

定理： 連通圖G的一個割集C至少包含G的任意生成樹的一個樹枝。

如果把C移去而仍有一棵樹T存在，則圖是連通的，那麼C將不是一個割集。 ^[1] 

由於KCI適用於任一個閉合面，所以屬於同一割集的所有支路上的電流滿足KCL。當割集中的所有支路都連接在同一結點上時，割集上的KCI方程就變成了結點上的KCL方程。如圖3中(b)所示的割集

。對於一個連通圖，可以列出與割集數目相等的KCI方程，但這些方程並非都是線性獨立的。對於結點數為n支路數為b的連通圖來説，其獨立的KCI方程數為n-1個。如果在圖中分別選和所有結點相連的支路為割集，則獨立割集數就是n-1個。下面介紹如何藉助“樹”的概念，尋找獨立的割集。

觀察連通圖G中的任意一個樹及其餘樹(由連支構成)，不難發現：一個單樹支總能與某些連支構成一個割集，稱為單樹支割集；對於結點數為n，支路數為b的連通圖，樹支數為n-1個，所以圖G的獨立割集數也是n-1個。通常將單樹支割集稱為基本割集。例如在圖4中(a)所示的有向圖中，選支路3、6、5為樹支，則3個獨立割集分別為

(1，2，3)、

(1，4，5)和

(1，2，6，4)，如圖4中(b)、(c)和(d)所示。注意：在圖中每一個割集都被賦予了一個方向，用於考察支路與割集的方向關係。

順便指出，一個連通圖G有許多樹，因此所選的樹不同，其基本割集也不同。巧妙地選樹及其基本割集組，可使電路矩陣方程稀疏易解。注意．獨立割集不見得是單樹支割集，如同獨立迴路不全是單連支迴路一樣。 ^[2]