圖的四階限制邊連通度的研究.pdf

1、圖的限制性邊連通度問(wèn)題及許多理論都是源自大型網(wǎng)絡(luò)的設(shè)計(jì)和可靠性分析．另外限制性邊連通度在實(shí)際問(wèn)題中有著廣泛的應(yīng)用，是圖論研究中一個(gè)很活躍的課題，各類(lèi)限制邊連通度問(wèn)題被相繼提出并加以發(fā)展、應(yīng)用． 如果不是特別說(shuō)明，本文中談及的所有圖都是簡(jiǎn)單連通的，階至少是8.當(dāng)研究網(wǎng)絡(luò)可靠性的時(shí)候，經(jīng)?？紤]這樣一種圖模型，它的節(jié)點(diǎn)不失效，但是它的連線(xiàn)，也就是邊可以獨(dú)立地等可能地失效，失效的概率是p ∈ (0，1)．這就是非常有名的Moore-Sh

2、annon網(wǎng)絡(luò)模型[1，2]．令G是—個(gè)Moore-Shannon網(wǎng)絡(luò)模型，邊數(shù)為h的邊割的數(shù)目用Ch表示，如果G恰好有e條邊，則它不連通的概率P(G，p)就可以表示為； P(G,p)=∑eh=1Chph(1-p)e-h. 顯然，P(G，p)的值越小，網(wǎng)絡(luò)的可靠性越好．如果能確定所有的系數(shù)Ch，那么這個(gè)網(wǎng)絡(luò)的可靠性就是確定的．但是對(duì)于任意圖，Provan和Ball在文獻(xiàn)[3]中指出，確定所有的系數(shù)Ch是一個(gè)NP-hard

3、問(wèn)題． 用Ω(n，e)表示n個(gè)點(diǎn)e條邊的圖的集合，當(dāng)p充分小時(shí)，在Ω(n，e)中，為了最小化P(G，p)，邊連通度λ(G)起了非常重要的作用． Bauer et al.在文獻(xiàn)[6]中指出，當(dāng)p充分小時(shí)，對(duì)G1，G2∈Q(n，e)，如果λ(G1)>λ(G2)，則P(G1，p)

4、通度的概念進(jìn)一步推廣，提出了k階限制邊割和k階限制邊連通度的概念[5]．目前，對(duì)于k=1，2，3的情況已經(jīng)有了廣泛而深入的研究． 在本文第一章中，我們主要介紹了文章所涉及的一些概念、術(shù)語(yǔ)和符號(hào)．記圖G的頂點(diǎn)集為V(G),邊集為E(G).對(duì)于X ∈ V(G),令G[X]表示X的導(dǎo)出子圖,X=V(G)-X，[X,-X]表示G中一端在X中，另一端在-X中的邊的集合．如果G是一個(gè)連通圖，S ∈E(G)使得G-S不連通，且G—S的每一個(gè)分

5、支至少有4個(gè)點(diǎn)，則S稱(chēng)為是G的一個(gè)四階限制邊割．G中所有四階限制邊割的最小階稱(chēng)為是G的四階限制邊連通度，用λ4(G)表示．如果λ4(G)存在，則稱(chēng)G是λ4-連通的．如果G中的一個(gè)四階限制邊割滿(mǎn)足|S|=λ4，則S稱(chēng)為λ4-割．在第二章中，我們研究圖的四階限制邊連通度的存在性問(wèn)題．階至少為8的連通圖F若含有一個(gè)割點(diǎn)s使得F-s的每—個(gè)分支的階至多是3，則稱(chēng)F為4-花．三角形每個(gè)頂點(diǎn)粘合一個(gè)3階完全圖的子圖所構(gòu)成的圖，稱(chēng)為三角支撐圖．利用這

6、兩類(lèi)圖我們刻畫(huà)了階至少是9的非λ4-連通的圖． 在文獻(xiàn)[20]中，歐見(jiàn)平證明了階至少是11的λ4-連通圖G滿(mǎn)足λ4(G)≤ξ4(G)，其中ξ4(G)=min{|(X，-X)|：X ∈ V(G)，|X|=4，G[X]是連通的)，本文第三章對(duì)這個(gè)定理給出了一個(gè)簡(jiǎn)潔的證明． 滿(mǎn)足λ4(G)=ξ4(G)的λ4-連通圖G稱(chēng)為是λ4-最優(yōu)的．如果X ∈ V(G)，[X，-X]是一個(gè)λ4-割，則X稱(chēng)為G的一個(gè)λ4-碎片．令T4(G)=