高階限制邊連通度的最優(yōu)性和超級(jí)性.pdf

1、目前，互聯(lián)網(wǎng)絡(luò)已經(jīng)與人們的工作、日常生活等方面息息相關(guān)．網(wǎng)絡(luò)的可靠性和容錯(cuò)性是近年來(lái)國(guó)內(nèi)外研究的熱點(diǎn)之一．我們知道，邊連通度是反映圖的連通性質(zhì)的一個(gè)重要參數(shù)，而要精確地刻畫(huà)圖的連通性質(zhì)，它存在著不足之處：首先，邊連通度相同的圖可靠度可能不同；其次，不能區(qū)分刪掉K個(gè)割斷點(diǎn)或λ條割斷邊得到的圖的不同類型，即未考慮對(duì)網(wǎng)絡(luò)的傷害程度；第三，默認(rèn)圖的任何子集中所有元素可能潛在地同時(shí)失效．為克服以上缺陷，自然要將其加以推廣．自1983年Harary

2、[1]提出條件連通度的概念以來(lái)，經(jīng)過(guò)二十多年的發(fā)展，條件連通度所涉及的內(nèi)容日益豐富和具體，包括超級(jí)連通度、過(guò)邊連通度、限制邊連通度等． 設(shè)計(jì)和分析大規(guī)模網(wǎng)絡(luò)的可靠性和容錯(cuò)性時(shí)，通常包括某些類型的圖模型，其中—個(gè)重要模型是這樣的網(wǎng)絡(luò)[2]： 設(shè)圖G=(V，E)，其節(jié)點(diǎn)不會(huì)失效，每一條邊是獨(dú)立失效的，失效概率為p．用Ni(G)表示邊數(shù)為i的邊割的數(shù)目，則G連通的概率R(G，p)為：其中ε是G的邊數(shù)，λ(G)為邊連通度．對(duì)于一

3、般圖，確定Ni(G)是NP—困難的[3]．Bauer et al[4]提出了最優(yōu)性的概念，稱G是λ—最優(yōu)的，如果λ(G)=δ(G)．進(jìn)一步，若G的每個(gè)最小邊割孤立一個(gè)點(diǎn)，稱G是超級(jí)—λ的． 為了更好地刻畫(huà)圖的連通性，Esfahanian和Hakimi[8]提出了限制邊連通度的概念．G的一個(gè)邊割U()E稱為限制邊割，如果G—U的每個(gè)分支不包含孤立點(diǎn)．如果這樣的邊割存在，限制邊連通度λ'(G)為限制邊割中最小的階，并且稱G為λ'—連

4、通的．他們證明了階至少是4的除星K1，n-1外的連通圖是λ'—連通的，并且滿足λ'(G)≤ζ(G)，這里ζ(G)=min{dG(u)+dG(v)—2：uv∈E(G)}是G的最小邊度．如果λ'(G)=ζ(G)，稱G是λ'—最優(yōu)的．進(jìn)一步，若G的每個(gè)最小限制邊割孤立一條邊，稱G是超級(jí)—λ'的． 令k是正整數(shù)．對(duì)于連通圖G=(V，E)，—個(gè)邊割U()E稱為k—限制邊割，如果G—U的每個(gè)分支至少有k個(gè)點(diǎn)，如果這樣的邊割存在，k—限制邊連

5、通度λk(G)為k—限制邊割中最小的階，并且稱G為λk—連通的，k—限制邊連通度在容錯(cuò)性研究中是一個(gè)非常重要的參數(shù)，令ζk(G)=min{()(F)：F是G的k階連通子圖}，這里()(F)表示恰好有一個(gè)端點(diǎn)在F中的邊的集合，在多數(shù)圖中λk(G)≤ζk(G)[28]．如果λk(G)=ζk(G)，稱G是λk—最優(yōu)的．進(jìn)一步，若G的每個(gè)最小k—限制邊割孤立一個(gè)k階連通子圖，稱G是超級(jí)—λk的． 在本文中，我們?cè)谇叭说幕A(chǔ)上繼續(xù)討論k—

6、限制邊連通度的相關(guān)性質(zhì)． 在第一章中，我們主要介紹本文中的相關(guān)概念，定理和符號(hào)．同時(shí)，我們給出了相關(guān)的研究背景和前人的結(jié)果， 在第二章中，我們用直徑和圍長(zhǎng)來(lái)刻畫(huà)圖的λk最優(yōu)性和超級(jí)性的充分條件，得到如下的結(jié)果： 定理2.2.令k≥3是正整數(shù)．對(duì)圖G，如果|G|≥2k，D≤g—(k+1)且k≤δ+1，這里D，g，δ分別表示G的直徑、圍長(zhǎng)和最小度，則G是λk—最優(yōu)的， 定義設(shè)G1，G2是兩個(gè)階至少是k的圖．含

7、G1∪G2，且對(duì)于每個(gè)點(diǎn)x∈V(G1)．|x，G2]|=1的圖所組成類記作Gx． 定理2.4.令k≥4是正整數(shù)．對(duì)圖G，如果|G|≥2k，D≤g—(k+2)且k≤δ+1，這里D，g，δ分別表示G的直徑、圍長(zhǎng)和最小度，則G是超級(jí)—λk的，除非G∈Gx． 在第三章中，我們用局部結(jié)構(gòu)來(lái)刻畫(huà)圖的λk最優(yōu)性和超級(jí)性的充分條件，得到下面的結(jié)果： 定理3.8.設(shè)G是n階λ3—連通圖，最小度δ≥[n/2]—2，且(a)每個(gè)導(dǎo)出四

8、圈中至少有一個(gè)點(diǎn)x，滿足d(x)≥[n/2]；(b)每個(gè)K4—e中至少有一個(gè)點(diǎn)y，滿足d(y)≥[n/2]+2，則G是λ3—最優(yōu)的． 定理3.9.設(shè)G是一個(gè)n階λk—連通圖，λk(G)≤ζk(G)，對(duì)G的任意一個(gè)k階連通子圖Fk及恰好在Fk中有s(1≤s≤k)個(gè)鄰點(diǎn)的u∈V(G)\V(Fk)，d(u)≥[n/2]—k+2s-1，則G是λk—最優(yōu)的． 定理3.11.設(shè)G是一個(gè)n階Ak—連通圖，λk(G)≤ζk(G)，對(duì)G的

9、任意一個(gè)k階連通子圖Fk及恰好在Fk中有s(1≤s≤k)個(gè)鄰點(diǎn)的u∈V(G)\V(Fk)，d(u)＞[n/2]—k+2s-1，則G是超級(jí)—λk的， 在第四章中，我們用鄰域結(jié)構(gòu)來(lái)刻畫(huà)圖的λk—連通性，上界以及圖的λk最優(yōu)性和超級(jí)性，得到下面的結(jié)果： 定理4.2.設(shè)G是階至少是2k的圖，每—對(duì)不相鄰的點(diǎn)u，v滿足|N(u)∩N(v)|≥k+1，則G是λk—連通的且λk(G)≤ζk(G)． 定義．設(shè)H1是[n/2]+i

10、階連通圖，H2是[n/2]—i階連通圖，其中0≤i≤k-1.把含H1∪H2，滿足|[H1，H2]|≤[n/2]+k-1，且每個(gè)u∈V(H1)滿足|N(u)∩V(H2)|≥1，每個(gè)口∈V(H2)滿足IN(v) flV(Hi)I≥1的圖類記作G1. 定理4.3.設(shè)G是n階(n≥2k)圖且G()G1.每一對(duì)不相鄰的點(diǎn)u，v滿足N(u)∩N(v)|≥k+1，且ζk(G)≤[n/2]+k，則G是λk—最優(yōu)的． 定理4.4.設(shè)G是n

11、階(n＞2k)圖且Fk是G的任意一個(gè)k階連通子圖，每一對(duì)不相鄰的點(diǎn)u，v滿足|N(u)∩N(v)|≥k+1，恰好在Fk中有s(2≤s≤k)個(gè)鄰點(diǎn)的點(diǎn)x∈V(G)\V(Fk)滿足d(x)≥[n/2]—k十2s-1，則G是λk—最優(yōu)的． 在第五章中，我們用一定距離的兩點(diǎn)的度和來(lái)刻畫(huà)圖的λk最優(yōu)性和超級(jí)性，得到以下如下的結(jié)果： 定理5.1.設(shè)G是n階k≤δ+1的λk—連通圖，滿足如下兩個(gè)條件，則G是λk—最優(yōu)的：(a)對(duì)于每對(duì)

12、距離為k—s+1，(k-1≥s≥1)的點(diǎn)x，y，有(b)對(duì)于每個(gè)k階連通子圖Fk，若z是Fk的k個(gè)點(diǎn)的公共鄰點(diǎn)，則 定理5.3.設(shè)G是n階k≤δ+1的λk—連通圖，滿足如下兩個(gè)條件，則G是超級(jí)—λk的：(a)對(duì)于每對(duì)距離為k—s+1，(k-1≥s≥1)的點(diǎn)x，g，有(b)對(duì)于每個(gè)k階連通子圖Fk，若z是Fk的k個(gè)點(diǎn)的公共鄰點(diǎn)，則在第六章中，我們主要研究圖的λk最優(yōu)性和超級(jí)性的關(guān)系，證明了下面的結(jié) 定理6.1.設(shè)是正整數(shù)，