擬陣與圖.pdf

1、　　圖論和擬陣理論在二十世紀經(jīng)歷了空前的發(fā)展。圖的支撐樹及擬陣的基都是組合理論的基本研究對象。一個連通圖的樹圖能夠反映該圖的不同支撐樹之間的變換關(guān)系。因此,研究一個圖的樹圖有助于我們更好地了解該圖的性質(zhì)。同樣的一個擬陣的基圖能夠反映該擬陣的不同基之間的變換關(guān)系。因此,研究一個擬陣的基圖有助于我們更好地了解該擬陣的性質(zhì)。近些年來,樹圖和擬陣的基圖被推廣得到了一些新的圖。我們主要研究擬陣基圖,擬陣的基關(guān)聯(lián)圖,鄰接葉邊交換森林圖以及圖的分數(shù)蔭

2、度等。
　　一個擬陣M就是一個有限集E以及E的一個非空子集族β,且滿足以下條件：對任意的B1,B2∈β及任一元素e1∈B1\B2,存在一個元素e2∈B2\B1,使得(B1\e1)∪e2∈B,記為M=(E,β)。β中的每一個元素稱為M的一個基。M的一個基的任何子集都稱為M的一個獨立集。如果C(？)E不是一個獨立集,并且任何子集X(？)C都是一個獨立集,則稱C為M的一個圈。如果M的一個圈只有一個元素,則稱之為M的一個環(huán)。如果兩個元素的

3、集合{x,y}是M的一個圈,則稱{x,y}為一對平行元。如果M既沒有環(huán)也沒有平行元,則稱M是一個簡單擬陣。如果一個元素含在M的任一基中,則稱之為M的一個反圈。
　　如果S是E的一個子集,且對任意的圈C,都有C(？)S或者C(？)E\S。則稱S為M的一個分離集。顯然E和(？)都是M的分離集。M的極小分離集稱為M一個分支。如果擬陣M只有一個分支,則稱M為連通擬陣。設(shè)e∈E,則M·e和MΔe分別表示由擬陣M經(jīng)過收縮和刪除e后所得到的擬陣

4、。
　　擬陣M=(E,β)的基圖是這樣一個圖G,其中V(G)=β,E(G)={B1B2：B1,B2∈β,且|B1\B2|=1},這里圖G的頂點和M的基用同樣的符號表示。
　　設(shè)G是一個圖,圖G的點集和邊集分別記為V(G)和E(G),令v(G)=|V(G)|。包含G的每個點的路稱為G一條Hamilton路；同樣地,包含G的每個點的圈稱為G一個Hamilton圈。如果(？)圖存在一個Hamilton圈,則稱之為Hamilton的