圖的k-限制邊連通度的最優(yōu)性和超級(jí)性的充分條件.pdf

1、在當(dāng)今經(jīng)濟(jì)和科技蓬勃發(fā)展的信息時(shí)代，互聯(lián)網(wǎng)絡(luò)在人們的工作、日常生活等方面凸顯越來(lái)越重要的地位．對(duì)于網(wǎng)絡(luò)的各項(xiàng)研究倍受人們的關(guān)注，其中對(duì)于網(wǎng)絡(luò)的可靠性和容錯(cuò)性研究已經(jīng)成為近年來(lái)國(guó)內(nèi)外研究的熱點(diǎn)之一．眾所周知，邊連通度是反映圖的連通性質(zhì)的一個(gè)重要參數(shù)．而要精確地刻畫(huà)圖的連通性質(zhì)，經(jīng)典邊連通度存在著不足之處：首先，邊連通度相同的圖可靠度可能不同；其次，不能區(qū)分刪掉κ個(gè)割斷點(diǎn)或λ條割斷邊得到的圖的不同類型，即未考慮刪掉點(diǎn)割或邊割對(duì)網(wǎng)絡(luò)的破壞程度

2、；第三，默認(rèn)圖的任何子集中所有元素可能潛在地同時(shí)失效．為克服以上缺陷，自然要將經(jīng)典邊連通度加以推廣．自1983年F．Harary[1]提出條件邊連通度的概念以來(lái)，經(jīng)過(guò)二十多年的發(fā)展，條件邊連通度所涉及的內(nèi)容日益豐富和具體，包括超級(jí)邊連通度、過(guò)邊連通度、限制邊連通度等．
　　對(duì)于大規(guī)模網(wǎng)絡(luò)的可靠性和容錯(cuò)性的分析通常引入各種圖論模型，利用圖的點(diǎn)和邊來(lái)代替網(wǎng)絡(luò)的節(jié)點(diǎn)和連線，以此構(gòu)成相互連通的網(wǎng)絡(luò)的基礎(chǔ)拓?fù)洌槍?duì)不同的模型，都有諸多相關(guān)理

3、論問(wèn)題需要研究。其中一個(gè)重要模型是這樣的圖[2]G=(V，E)：假設(shè)其節(jié)點(diǎn)不會(huì)失效，每一條邊是獨(dú)立失效的，失效概率為p∈(0，1)．若G的邊數(shù)是ε，用Ci表示邊數(shù)為i的邊割的數(shù)目，則G不連通的概率為：其中λ(G)是G的邊連通度．易知網(wǎng)絡(luò)保持連通的概率為1-P(G，p)．顯然，P(G，p)的值越小，網(wǎng)絡(luò)的可靠性就越好．因此，若要確定網(wǎng)絡(luò)的可靠性，則需要確定所有的系數(shù)Gi．但是J．S．Provan和M．O．Ball[3]指出：對(duì)于一般圖G，