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

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

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

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