擬陣與圖.pdf

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

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

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

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