圈擬陣(circuit matroid)亦稱多邊形擬陣，是一類特殊的擬陣，它是建立在圖G=(V,E)上的一類擬陣M(G)。設G是一個圖，E=E(G)是G的邊集。定義I⊆2E為這樣的一個集合： X∈I若且唯若X(作為G的子圖)不含有極小圈，那么(E，I)是一個擬陣，這個擬陣通常稱為G的圈擬陣(cycle matroid)，記作M(G)。此結論可由以下例子得出：設G是一個圖，其邊集為E=E(G)，當X⊆E是G的一個無圈子圖(即不含有極小圈的子圖)，則X的任意子集Y也是G的一個無圈子圖。當X1，X2⊆E是G中的兩個無圈子圖並且|X1|<|X2|時，則在G的子圖X1∪X2中， X1也不是X1∪X2的極大無圈子圖。因而有e∈X2-X1，使得X1∪e也是G中的一個無圈子圖。
基本介紹
- 中文名：圈擬陣
- 外文名：circuit matroid
- 所屬學科：數學
- 所屬問題：組合學（組合序）
- 別稱：多邊形擬陣
- 簡介：建立在圖G=(V,E)上的一類擬陣
基本介紹,相關性質,舉例,
基本介紹
圈擬陣是建立在圖G=(V，E)上的一類擬陣M(G)，其獨立集為不含圈的邊集E的子集，因此，圈擬陣的直觀形象十分鮮明，由於不同構的圖會有相同的圈擬陣，對圈擬陣的研究並不能取代圖的研究，它只能看做圖的一種延伸，對於圈擬陣M(G)，其圈正是圖G的圈，所以圈擬陣亦稱多邊形擬陣。
圖G的上圈是E的子集A，將A從G中移去以後會增加G的連通分支的數目，正如G的圈構成M(G)的圈一樣，以G的上圈為圈，對應地得到G上的另一類擬陣，稱為上圈擬陣，上圈擬陣亦稱鍵擬陣，圈擬陣和上圈擬陣互為對偶，且在任何域上均可表示，記上圈擬陣為M(G)。
相關性質
由於圈擬陣和上圈擬陣具有明顯的圖的特徵，所以藉助於同構的概念，可將它們延伸到其他一般擬陣，擬陣M1=(E1，I1)，M2=(E2，I2)同構，若且唯若在E1和E2之間有雙射φ，並保持獨立性，對於擬陣M，若有圖G存在，使得M與G的圈擬陣同構，則稱M是可圖的或稱M為圖擬陣.對應地，若M與G的上圈擬陣同構，則稱M是可上圖的，或稱M為上圖擬陣。例如，完全圖K5，完全二部圖K3，3的圈擬陣M(K5)和M(K3，3)是可圖的，但不是可上圖的。更一般地，G為平面圖，若且唯若它的圈擬陣M(G)是可上圖的.因此，擬陣的可圖性，本質上刻畫了圖的平面性。
圖1特別地，當G為歐拉圖時，它的邊集能劃分為圈，而在歐拉圖上建立的圈擬陣，稱為歐拉擬陣，更一般地，對於建立在集合E上的擬陣M，若E可以表示為M的互不重疊的圈的並集，則稱M為歐拉擬陣，若M的所有圈，其中元素的個數均為偶數時，則稱M為偶擬陣，二元擬陣為歐拉擬陣若且唯若其對偶是二元擬陣，作為一個既不是圖擬陣也不是上圖擬陣的例子，它就是旋擬陣，此擬陣由輪圖Wn+1=K1+Cn產生，它的圈對應為Cn添加一條幅，例如，對於W5，其圈如上圖。
舉例
考慮圖G
圖2其邊集為
。我們要確定所有無圈子圖的邊集的集族
。由於每一個無圈子圖都是一個支撐樹的子圖，因此我們只要找出G的所有的支撐樹。不難看出G的全體支撐樹對應的邊子集是
