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

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

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

3、般圖，確定Ni(G)是NP—困難的[3]．Bauer et al[4]提出了最優(yōu)性的概念，稱G是λ—最優(yōu)的，如果λ(G)=δ(G)．進一步，若G的每個最小邊割孤立一個點，稱G是超級—λ的． 為了更好地刻畫圖的連通性，Esfahanian和Hakimi[8]提出了限制邊連通度的概念．G的一個邊割U()E稱為限制邊割，如果G—U的每個分支不包含孤立點．如果這樣的邊割存在，限制邊連通度λ'(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)的．進一步，若G的每個最小限制邊割孤立一條邊，稱G是超級—λ'的． 令k是正整數(shù)．對于連通圖G=(V，E)，—個邊割U()E稱為k—限制邊割，如果G—U的每個分支至少有k個點，如果這樣的邊割存在，k—限制邊連

5、通度λk(G)為k—限制邊割中最小的階，并且稱G為λk—連通的，k—限制邊連通度在容錯性研究中是一個非常重要的參數(shù)，令ζk(G)=min{()(F)：F是G的k階連通子圖}，這里()(F)表示恰好有一個端點在F中的邊的集合，在多數(shù)圖中λk(G)≤ζk(G)[28]．如果λk(G)=ζk(G)，稱G是λk—最優(yōu)的．進一步，若G的每個最小k—限制邊割孤立一個k階連通子圖，稱G是超級—λk的． 在本文中，我們在前人的基礎上繼續(xù)討論k—

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

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

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

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

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

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

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