圈基(circuit basis)圖G的循環空間的一組基，循環空間的維數稱為圈秩或簡稱上秩。上循環空間的一組基稱為上圈基，上循環空間的維數稱為上圈秩或簡稱秩。
基本介紹
- 中文名：圈基
- 外文名：circuit basis
- 所屬學科：數學
- 所屬問題：圖論（循環空間）
- 相關概念：循環空間，點空間等
基本介紹,相關概念,點空間,生成樹,秩多項式,
基本介紹
圈基是圖G的循環空間(參見下文“點空間”)的一組基，循環空間的維數稱為圈秩或簡稱上秩，記為
，
相關概念
點空間
點空間(vertex space)是一類組合構形，指由圖G=(V，E)的頂點集V生成的域F(通常取二元域)上的向量空間，記為
。由邊集E生成的域F上的向量空間稱為邊空間，記為
。中的向量稱為0鏈，中的向量稱為1鏈。邊緣運算元是由到的一個線性變換，它將任一邊映射為其兩端點的和。上邊緣運算元是由F到F的一個線性變換，它將任一頂點映射為與其關聯的所有邊的和，邊緣運算元的像空間稱為邊緣空間希笑提，它的核空間稱為循環空間。上邊緣運算元的像空間稱為上循環空間，循環空間與上循環空間的交空間稱為雙循環空間。若兩個0鏈 在上邊緣運算元作用下具有相同的像，則稱它們寒嘗檔遷上同調。若兩個1鏈在邊緣運算元作用下具有相同的像，則稱它們同調。
生成樹
連通且無簡單迴路的無向圖稱為無向樹，簡稱樹。樹中度數為1的頂點稱為樹葉，度數大於1的頂點稱為分支點求巴或內點，僅含一個孤立點的樹稱為平凡樹，無簡單迴路的無向圖稱為森林。
定理1設圖T有n個頂點，則下述命題相互等價。
(1)T是樹；
(2)T是無迴路的圖，且e=n-1，其中e是圖的邊數；
(3)T是連通圖且e=n-1；
(4)T是無同路圖，且在T中任意兩個不相鄰的頂點之間添加一邊後，恰得一條迴路(這時稱T為最大無迴路圖)；
(5)T連通，但是刪去任何一邊後便不再連通(這時稱T為最小連通圖)；
(6)T的每一對不同頂點之間有唯一的一條路。
若連通圖G的生舉堡危成子圖是一棵樹，則稱這棵樹為G的生成樹。
設G是一個
-連通圖，則相對於它的任何一個生成樹T，含有m-(n-1)個補樹邊，根據定理1中命題(4)，對每條補樹邊e，T+e有且僅有一個圈，因此G中至少含有m-n+1個圈，這m-n+1個圈是G的基本圈，構成G的圈空間的基，因而又稱m-n+1為G的圈秩。
定理2 設T是連通圖的G的察蒸蜜生成樹。則(1)G的任何邊割集與T至少有一公共樂滲潤己邊；(2)G的任何勸說乃圈與補樹至少有一條公共邊。
秩多項式
對於圖
，記
