圈擬陣

圈擬陣(circuit matroid)亦稱多邊形擬陣，是一類特殊的擬陣，它是建立在圖G=(V,E)上的一類擬陣M(G)。設G是一個圖，E=E(G)是G的邊集。定義I⊆2為這樣的一個集合： X∈I若且唯若X(作為G的子圖)不含有極小圈，那么(E，I)是一個擬陣，這個擬陣通常稱為G的圈擬陣(cycle matroid)，記作M(G)。此結論可由以下例子得出：設G是一個圖，其邊集為E=E(G)，當X⊆E是G的一個無圈子圖(即不含有極小圈的子圖)，則X的任意子集Y也是G的一個無圈子圖。當X₁，X₂⊆E是G中的兩個無圈子圖並且|X₁|<|X₂|時，則在G的子圖X₁∪X₂中， X₁也不是X₁∪X₂的極大無圈子圖。因而有e∈X₂-X₁，使得X₁∪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)。

相關性質

由於圈擬陣和上圈擬陣具有明顯的圖的特徵，所以藉助於同構的概念，可將它們延伸到其他一般擬陣，擬陣M₁=(E₁，I₁)，M₂=(E₂，I₂)同構，若且唯若在E₁和E₂之間有雙射φ，並保持獨立性，對於擬陣M，若有圖G存在，使得M與G的圈擬陣同構，則稱M是可圖的或稱M為圖擬陣.對應地，若M與G的上圈擬陣同構，則稱M是可上圖的，或稱M為上圖擬陣。例如，完全圖K₅，完全二部圖K_3，3的圈擬陣M(K₅)和M(K_3，3)是可圖的，但不是可上圖的。更一般地，G為平面圖，若且唯若它的圈擬陣M(G)是可上圖的.因此，擬陣的可圖性，本質上刻畫了圖的平面性。

圖1

特別地，當G為歐拉圖時，它的邊集能劃分為圈，而在歐拉圖上建立的圈擬陣，稱為歐拉擬陣，更一般地，對於建立在集合E上的擬陣M，若E可以表示為M的互不重疊的圈的並集，則稱M為歐拉擬陣，若M的所有圈，其中元素的個數均為偶數時，則稱M為偶擬陣，二元擬陣為歐拉擬陣若且唯若其對偶是二元擬陣，作為一個既不是圖擬陣也不是上圖擬陣的例子，它就是旋擬陣，此擬陣由輪圖W_n+1=K₁+C_n產生，它的圈對應為C_n添加一條幅，例如，對於W₅，其圈如上圖。

舉例

考慮圖G

圖2

其邊集為 。我們要確定所有無圈子圖的邊集的集族 。由於每一個無圈子圖都是一個支撐樹的子圖，因此我們只要找出G的所有的支撐樹。不難看出G的全體支撐樹對應的邊子集是

因此，