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

1、由于樹圖及鄰接樹圖在通訊網絡拓撲結構中的應用，它的相關性質被眾多的學者進行了廣泛深入的研究．人們尤其對樹圖中有七個懸掛點的支撐樹的內插性質產生了極大的興趣．Chartrandp<'[1,p610]>曾提出過這樣的公開問題：如果一個圖G具有圈秩p，且該圖G有兩個分別含m和n個懸掛點的支撐樹(m

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

3、為：點集V( (G))是把G的所有單圈支撐子圖作為Θ(G)中的點的集合，邊SS’∈E(Θ(G))當且僅當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ā)，運用一個樹的兩個基本圈之間存在圈鏈這一性質，研究了其鄰Θ-圖A(G)的結構并得到以下的結果： 1．

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

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