圖的K階限制邊連通度的若干性質(zhì).pdf

1、隨著經(jīng)濟(jì)和科技的迅猛發(fā)展，互聯(lián)網(wǎng)絡(luò)與人們的關(guān)系越來(lái)越密切，對(duì)于網(wǎng)絡(luò)的各項(xiàng)研究備受人們的關(guān)注，其中對(duì)于可靠性和容錯(cuò)性的研究已經(jīng)是國(guó)內(nèi)外的研究熱點(diǎn)之一．對(duì)于大規(guī)模網(wǎng)絡(luò)的可靠性和容錯(cuò)性的分析通常引入各種圖論模型，利用圖的點(diǎn)和邊來(lái)代替網(wǎng)絡(luò)的節(jié)點(diǎn)和連線，以此構(gòu)成相互連通的網(wǎng)絡(luò)的基礎(chǔ)拓?fù)洌娝苤?，傳統(tǒng)邊連通度可以估計(jì)網(wǎng)絡(luò)的可靠程度，但這一重要參數(shù)在對(duì)于相同邊連通度的不同網(wǎng)絡(luò)可靠性的判斷中卻失效了．為了更好地刻畫(huà)圖的連通情況，F(xiàn)．Harary[1]

2、于1983年提出條件邊連通度的概念，為這一領(lǐng)域的研究開(kāi)辟了新的道路．自此，網(wǎng)絡(luò)的可靠性及容錯(cuò)性的綜合分析快速發(fā)展起來(lái)，成為圖論研究中一個(gè)很熱門(mén)的課題．
　　在設(shè)計(jì)和分析大規(guī)模網(wǎng)絡(luò)的可靠性和容錯(cuò)性時(shí),通常涉及這樣一種著名的圖模型G=(V,E)：節(jié)點(diǎn)不會(huì)失效,但邊獨(dú)立地以概率ρ∈(0,1)等可能地失效.若G的邊數(shù)是ε,Gi表示邊數(shù)為i的邊割的數(shù)目,則G不連通的概率為：易知網(wǎng)絡(luò)保持連通的概率為1-P(G,ρ).顯然P(G,ρ)越小,網(wǎng)絡(luò)

3、的可靠性越好.因此,若要確定網(wǎng)絡(luò)的可靠性,需要確定所有的系數(shù)Ci,但J.S.Provan和M.O.Ball證明了對(duì)于一般圖這是NP-困難問(wèn)題.為了更加精確地估計(jì)網(wǎng)絡(luò)的可靠性,A.H.Esfahanian和S.L.Hakimi提出了限制邊連通度的概念.更進(jìn)一步,李喬良和李喬提出了超級(jí)限制邊連通度的概念.目前,對(duì)于這一領(lǐng)域已有了廣泛而深入的研究。
　　本文在前人工作的基礎(chǔ)上,繼續(xù)研究限制邊連通度的若干性質(zhì). 在第一章中,我們主要介紹了