[科普中國]-圈基

圈基(circuit basis)圖G的循環(huán)空間的一組基，循環(huán)空間的維數(shù)稱為圈秩或簡稱上秩。上循環(huán)空間的一組基稱為上圈基，上循環(huán)空間的維數(shù)稱為上圈秩或簡稱秩。

基本介紹圈基是圖G的循環(huán)空間(參見下文“點空間”)的一組基，循環(huán)空間的維數(shù)稱為圈秩或簡稱上秩，記為，

其中為的連通片數(shù)。上循環(huán)空間的一組基稱為上圈基，上循環(huán)空間的維數(shù)稱為上圈秩或簡稱秩，記為。若為圖的一個支撐樹，為相應(yīng)的上樹，則任何一個上樹邊與樹恰形成一個圈，稱為樹的一個基本圈。相仿地，每一個樹邊與上樹恰形成一個上圈，稱為樹T的一個基本上圈。支撐樹T的所有基本圈構(gòu)成圖G的一個圈基，所有基本上圈構(gòu)成圖G的一個上圈基。雙循環(huán)空間的一組基稱為雙圈基，雙循環(huán)空間的維數(shù)稱為雙圈秩，與某一雙圈基中的每一個圈恰有一條公共邊的邊集，稱為雙樹1。

相關(guān)概念點空間點空間(vertex space)是一類組合構(gòu)形，指由圖G=(V，E)的頂點集V生成的域F(通常取二元域)上的向量空間，記為。由邊集E生成的域F上的向量空間稱為邊空間，記為。中的向量稱為0鏈，中的向量稱為1鏈。邊緣算子是由到的一個線性變換，它將任一邊映射為其兩端點的和。上邊緣算子是由F到F的一個線性變換，它將任一頂點映射為與其關(guān)聯(lián)的所有邊的和，邊緣算子的像空間稱為邊緣空間，它的核空間稱為循環(huán)空間。上邊緣算子的像空間稱為上循環(huán)空間，循環(huán)空間與上循環(huán)空間的交空間稱為雙循環(huán)空間。若兩個0鏈 在上邊緣算子作用下具有相同的像，則稱它們上同調(diào)。若兩個1鏈在邊緣算子作用下具有相同的像，則稱它們同調(diào)1。

生成樹連通且無簡單回路的無向圖稱為無向樹，簡稱樹。樹中度數(shù)為1的頂點稱為樹葉，度數(shù)大于1的頂點稱為分支點或內(nèi)點，僅含一個孤立點的樹稱為平凡樹，無簡單回路的無向圖稱為森林。

定理1設(shè)圖T有n個頂點，則下述命題相互等價。

(1)T是樹；

(2)T是無回路的圖，且e=n-1，其中e是圖的邊數(shù)；

(3)T是連通圖且e=n-1；

(4)T是無同路圖，且在T中任意兩個不相鄰的頂點之間添加一邊后，恰得一條回路(這時稱T為最大無回路圖)；

(5)T連通，但是刪去任何一邊后便不再連通(這時稱T為最小連通圖)；

(6)T的每一對不同頂點之間有唯一的一條路。

若連通圖G的生成子圖是一棵樹，則稱這棵樹為G的生成樹。

設(shè)G是一個-連通圖，則相對于它的任何一個生成樹T，含有m-(n-1)個補樹邊，根據(jù)定理1中命題(4)，對每條補樹邊e，T+e有且僅有一個圈，因此G中至少含有m-n+1個圈，這m-n+1個圈是G的基本圈，構(gòu)成G的圈空間的基，因而又稱m-n+1為G的圈秩。

定理2 設(shè)T是連通圖的G的生成樹。則(1)G的任何邊割集與T至少有一公共邊；(2)G的任何圈與補樹至少有一條公共邊2。

秩多項式對于圖，記

其中，分別為以S為邊集的G的支撐子圖的秩和上秩，稱為圖G的秩多項式2。

本詞條內(nèi)容貢獻者為:

王海俠 - 副教授 - 南京理工大學(xué)