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

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

2、于1983年提出條件邊連通度的概念，為這一領(lǐng)域的研究開辟了新的道路．自此，網(wǎng)絡(luò)的可靠性及容錯性的綜合分析快速發(fā)展起來，成為圖論研究中一個很熱門的課題．
　　在設(shè)計和分析大規(guī)模網(wǎng)絡(luò)的可靠性和容錯性時,通常涉及這樣一種著名的圖模型G=(V,E)：節(jié)點不會失效,但邊獨立地以概率ρ∈(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證明了對于一般圖這是NP-困難問題.為了更加精確地估計網(wǎng)絡(luò)的可靠性,A.H.Esfahanian和S.L.Hakimi提出了限制邊連通度的概念.更進一步,李喬良和李喬提出了超級限制邊連通度的概念.目前,對于這一領(lǐng)域已有了廣泛而深入的研究。
　　本文在前人工作的基礎(chǔ)上,繼續(xù)研究限制邊連通度的若干性質(zhì). 在第一章中,我們主要介紹了