k-限制邊連通度的存在性與上界.pdf

1、隨著社會(huì)經(jīng)濟(jì)和科技的發(fā)展，互聯(lián)網(wǎng)絡(luò)與人們的工作、日常生活等方面的關(guān)系越來越密切，自然，網(wǎng)絡(luò)的可靠性和容錯(cuò)性倍受人們的關(guān)注．研究網(wǎng)絡(luò)的可靠性和容錯(cuò)性是社會(huì)發(fā)展的必然趨勢(shì)，是近年來國(guó)內(nèi)外研究的熱點(diǎn)之一．眾所周知，邊連通度是反映圖的連通性質(zhì)的一個(gè)重要參數(shù)．而要更精確地刻畫圖的連通性質(zhì)，經(jīng)典邊連通度存在著不足之處：首先，邊連通度相同的圖的可靠度可能不同．其次，不能區(qū)分刪掉K—點(diǎn)割或λ—邊割得到的圖的不同類型，即未考慮刪掉點(diǎn)割或邊割對(duì)網(wǎng)絡(luò)的損害程

2、度．第三，默認(rèn)圖的任何子集中所有元素可能潛在地同時(shí)失效，為克服以上缺陷，自然要將經(jīng)典邊連通度的概念加以推廣．自1983年Harary[1]提出條件邊連通度的概念以來，經(jīng)過二十多年的發(fā)展，條件邊連通度所涉及的內(nèi)容日益豐富和具體，包括超級(jí)邊連通度、過邊連通度、限制邊連通度等。 設(shè)計(jì)和分析大規(guī)模網(wǎng)絡(luò)的可靠性和容錯(cuò)性時(shí)，通常涉及某些類型的圖模型，針對(duì)不同的模型，都有諸多相關(guān)理論問題需要研究．其中一個(gè)重要模型是這樣的圖G=(V，E)：假設(shè)

3、其節(jié)點(diǎn)不會(huì)失效，但節(jié)點(diǎn)間的連線相互獨(dú)立地以等概率p∈(0，1)失效．則G不連通的概率為：其中e為G的邊數(shù)，Ch表示邊數(shù)為h的邊割的數(shù)目．則圖G的可靠度為1—P(G，p)．顯然P(G，p)越小，網(wǎng)絡(luò)的可靠性越好，因此，確定P(G，p)的大小問題在網(wǎng)絡(luò)可靠度的研究中倍受關(guān)注，但Provan和Ball[2]已經(jīng)證明，對(duì)一般圖G，P(G，p)的計(jì)算是NP—困難的．為此，Esfahanian和Hakimj[3]提出了限制邊連通度的概念．本文在前人

4、工作的基礎(chǔ)上，繼續(xù)研究限制邊連通度的相關(guān)性質(zhì)．文中k總表示一個(gè)正整數(shù)，ω(G)表示圖G的最大團(tuán)的點(diǎn)數(shù)。 第一章，主要介紹了本文的研究背景和已有的一些結(jié)果，以及文中所涉及的一些概念和術(shù)語符號(hào)．1.令G=(V，E)是n(≥2k)階連通圖，S是G的一個(gè)邊子集，若G—S不連通且G—S的每個(gè)分支至少有k個(gè)頂點(diǎn)，則稱S為G的k—限制邊割，記為Rk—邊割．G的最小Rk—邊割(叫λk—邊割)所含邊數(shù)稱為G的k—限制邊連通度，記為λk(G)或λk

5、．若λk(G)存在，則稱G是λk—連通的。2.設(shè)X，Y是圖G=(V，E)的頂點(diǎn)集V的兩個(gè)不交的非空子集或G的兩個(gè)點(diǎn)不交的子圖．G的一端點(diǎn)在X中且另一端點(diǎn)在Y中的邊構(gòu)成的集合記作[X，Y]．當(dāng)X={x}時(shí)，用[x，Y]代替[X，Y]．記I(X)=[X，V—X]，稱()(x)=|I(X)|為X的外度．令ξk(G)=min{()(X)：|X|=k，且G[X]連通}，這里G[X]表示X(()V)在G中的導(dǎo)出子圖．令—X=V(G)—X．若[X，—

6、X]是圖G的一個(gè)λk—邊割，則X稱為λk—碎片．顯然，若X是一個(gè)λk—碎片，則—X亦然．圖G的含頂點(diǎn)數(shù)最少的λk—碎片稱為G的λk—原子，其頂點(diǎn)數(shù)記為rk(G)。3.設(shè)G是λk—連通的，若λk(G)=ξk(G)，則稱圖G是λk—最優(yōu)的。 第二章，討論了5—限制邊連通度的上界問題，得到以下結(jié)果：1. 3設(shè)G是階至少為18的連通圖．若G含5—限制邊割，則λ5(G)≤ξ5(G)當(dāng)且僅當(dāng)G不屬于^G5.其中^G5定義如下：階至少為18，

7、恰含一個(gè)5階完全圖K5，且K5的每個(gè)頂點(diǎn)上通過恰好一條邊連接一個(gè)階至多為3的連通圖得到的圖．2.設(shè)G是階至少為18的λ5—連通且無三角形的圖，若G不是λ5—最優(yōu)的，則r5(G)≥max{6，28(G)—4}．3.設(shè)G是λ5—連通的，δ(G)≥6，U是G的λ5—原子，若G不是λ5—最優(yōu)的，則對(duì)于任意的v∈U，有dG[U](v)≥4。 第三章，研究了正則圖k—限制邊連通度的存在性，得到下面的結(jié)果：1.設(shè)G是階至少為2k的(k—3)—

8、正則連通圖(k≥5)，則G的k—限制邊連通度λk(G)存在當(dāng)且僅當(dāng)G不屬于G～k—3∪Gk—2k—3；且k—7時(shí)，G不同構(gòu)于G417.將階至少為2k，(k—3)—正則連通(k≥5)，包含割點(diǎn)b使得刪掉頂點(diǎn)b后每個(gè)分支的階為k-1或k—2的圖類記為G～k—3.將階為3k—3或3k—4的(k—3)—正則連通(k≥5)，由在三角形的每個(gè)頂點(diǎn)上各粘合一個(gè)階≤k—2的連通圖得到的圖類記為Gk—2k—3.將階為17的4—正則連通，包含一條邊e和三個(gè)

9、5階連通圖G1，G2，G3(Gi為5階完全圖去掉關(guān)聯(lián)同一點(diǎn)的兩條邊得到，i=1，2，3)，且e的每個(gè)端點(diǎn)均與G1，G2，G3的2度點(diǎn)恰通過一條邊相連得到的圖記為G417.2.設(shè)G是階至少為2k的(k—4)—正則連通圖(k≥6)，則G的k—限制邊連通度λk(G)存在當(dāng)且僅當(dāng)G不屬于Gok—4∪Gk—2k—4且k=8時(shí)， G不同構(gòu)于G417.將階至少為2k，(k—4)—正則連通(k≥6)，包含割點(diǎn)b使得刪掉頂點(diǎn)b后每個(gè)分支的階為k-1，k—

10、2或k—3的圖類記為Gok—4.將階為3k—3，3k—4，3k—5或3k—6的(k—4)—正則連通(k≥4)，由三角形的每個(gè)頂點(diǎn)上各粘合一個(gè)階≤k—2的連通圖得到的圖類記為Gk—2k—4。 第四章，研究了圖是k—限制邊連通度最優(yōu)的充分條件，得到下面的結(jié)果：1.設(shè)G是一個(gè)n(≥2k)階連通圖，假設(shè)對(duì)G中任意一對(duì)不相鄰的頂點(diǎn)x和y，都有d(x)+d(y)≥n+2k—4，若G不是G*k圖，則G是λk—最優(yōu)的．其中，圖G*k是這樣的n(

11、≥2k)階連通圖，它的頂點(diǎn)集可剖分成兩部分V1，V2，使得|V1|，|V2|≥k且若存在xi∈Vi，使得d(xi)=|Vi|+k—2且xi是[V1，V2]的k-1飽和點(diǎn)(即xi與[V1，V2]的k-1條邊關(guān)聯(lián))，i=1，2，則x1，x2不相鄰。2.設(shè)G是n階λ3—連通無三角圖，度序列為d1≥d2≥…≥dn=δ．若則G是λ3—最優(yōu)的。3.設(shè)p≥3是一個(gè)整數(shù)，G是n階λ3—連通圖且ω(G)≤p，度序列d1≥d2≥…≥dn=δ．若則G是λ3—