2-連通圖的單圈子圖.pdf

1、由于樹圖及鄰接樹圖在通訊網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中的應(yīng)用，它的相關(guān)性質(zhì)被眾多的學(xué)者進(jìn)行了廣泛深入的研究．人們尤其對(duì)樹圖中有七個(gè)懸掛點(diǎn)的支撐樹的內(nèi)插性質(zhì)產(chǎn)生了極大的興趣．Chartrandp<'[1,p610]>曾提出過這樣的公開問題：如果一個(gè)圖G具有圈秩p，且該圖G有兩個(gè)分別含m和n個(gè)懸掛點(diǎn)的支撐樹(m

2、Lin<'[4]>也對(duì)上述問題提出了新的的辦法．但是他們只證明了這樣的支撐樹的存在性．在1988年,Katherine Heinrich和劉桂珍也給出了上述問題的詳細(xì)證明，他們不僅證明了存在這樣的支撐樹，而且還證明了這樣的支撐樹的個(gè)數(shù)與圖G的圈秩有關(guān)，并給出了它的最佳下界．類似樹圖我們可以定義2-連通圖G的Θ-圖 (G)及鄰Θ-圖A(G)．圖G的單圈支撐子圖S定義為圖G的支撐樹T再加上一條邊e(e∈G)，即S=T+e．則圖G的 -圖定義

3、為：點(diǎn)集V( (G))是把G的所有單圈支撐子圖作為Θ(G)中的點(diǎn)的集合，邊SS’∈E(Θ(G))當(dāng)且僅當(dāng)IE(S) E(S')|=2．類似地，我們定義圖G的Θ-圖A(G)如下：A(G)為Θ(G)的支撐子圖，且A(G)中有邊SS’∈E(A(G))，如果S'=S-uv+uw(其中邊uv∈S，邊UW S)． 本文從2-連通圖出發(fā)，運(yùn)用一個(gè)樹的兩個(gè)基本圈之間存在圈鏈這一性質(zhì)，研究了其鄰Θ-圖A(G)的結(jié)構(gòu)并得到以下的結(jié)果： 1．

4、利用2-連通圖G的鄰接單圈支撐子圖的定義和支撐樹的性質(zhì)，得到了兩個(gè)鄰接單圈支撐子圖S，S'具有同一支撐樹這一性質(zhì)，同時(shí)利用歸納假設(shè)的方法，證明了圖G中連接圈G<,x>C<,y> 的初等圈鏈的存在性． 2．通過分情形討論以及前面所證明的圈鏈的存在性，得出了鄰Θ-圖A(G)及其導(dǎo)出子圖H的連通性．由此證明得到定理A．即設(shè)S，S’為2-連通圖G中兩個(gè)單圈支撐子圖，則在Θ(G)中至少有2(p-1)條內(nèi)部不交路連S和S’．這里,p是G的圈

5、秩． 3．利用2-連通圖G的Θ-圖的連通性質(zhì)，得出了定理B．即如果一個(gè)2-連通圖G有兩個(gè)單圈支撐子圖，且這兩個(gè)單圈支撐子圖分別含m和n個(gè)懸掛點(diǎn)(m和定理1.6<'[5]>在射影單面上單面嵌入圖方面的推廣．沿著這一思路，我