1、在當(dāng)今經(jīng)濟(jì)和科技蓬勃發(fā)展的信息時(shí)代，互聯(lián)網(wǎng)在人們的工作、日常生活等方面凸顯越來越重要的地位．研究網(wǎng)絡(luò)的可靠性和容錯(cuò)性成為近年來國內(nèi)外研究的熱點(diǎn)課題之一．眾所周知，圖的邊連通度是反映圖的連通性質(zhì)的一個(gè)重要參數(shù)．然而為了更精確地刻畫圖的連通性質(zhì)，需要將經(jīng)典邊連通度的概念繼續(xù)加以推廣．1983年F．Harary[1]提出條件邊連通度的概念，經(jīng)過二十年來的發(fā)展，各類條件邊連通度問題被相繼提出，發(fā)展和應(yīng)用．圖的限制邊連通度問題在大型網(wǎng)絡(luò)的設(shè)計(jì)和分

2、析中非常重要，在實(shí)際問題中也應(yīng)用廣泛，是圖論研究中非常活躍的研究課題．
　　在設(shè)計(jì)和分析大規(guī)模網(wǎng)絡(luò)的可靠性和容錯(cuò)性時(shí)，通?？紤]某些類型的度量準(zhǔn)則和圖模型．對于不同的度量準(zhǔn)則和模型，相應(yīng)地需要研究許多不同的相關(guān)理論問題．圖的不連通性可以作為圖網(wǎng)絡(luò)可靠性的度量準(zhǔn)則，此時(shí)其中一個(gè)重要模型是這樣的圖G=(V,E)：假設(shè)其節(jié)點(diǎn)不會失效，但節(jié)點(diǎn)間的連線，也就是邊相互獨(dú)立地以等概率p∈(0，1)失效．令e是G的邊數(shù)，Ch表示邊數(shù)為h的邊割的數(shù)目

3、，則G不連通的概率可以表示為：P(G，p)=e∑ h=1 Chph(1-p)e-h．
　　因此圖G的可靠度為1-P(G，p)．顯然P(G，p)越小，網(wǎng)絡(luò)的可靠性就越好．自然，為了確定P(G，p)的值就需要確定所有系數(shù)Ch．但是J．Provan和M．Ball[2]指出，對一般圖G，確定所有系數(shù)Ch，從而計(jì)算P(G，p)的值是NP-困難的．為此，A．H．Esfahanian和S．L．Hakimi[3]在研究大規(guī)模網(wǎng)絡(luò)的可靠性和容錯(cuò)性時(shí)