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

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

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

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