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

1、山東師范大學(xué)碩士學(xué)位論文圖的k限制邊連通度的若干性質(zhì)姓名：張淑芹申請(qǐng)學(xué)位級(jí)別：碩士專(zhuān)業(yè)：應(yīng)用數(shù)學(xué)指導(dǎo)教師：高敬振20080410山東師范大學(xué)碩士學(xué)位論文圖的足限制邊連通度的若干性質(zhì)張淑芹(山東師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院，濟(jì)南，山東，250014)中文摘要目前，互聯(lián)網(wǎng)絡(luò)已經(jīng)與人們的工作，日常生活等方面息息相關(guān)網(wǎng)絡(luò)的可靠性和容錯(cuò)陛是近年來(lái)國(guó)內(nèi)外研究的熱點(diǎn)問(wèn)題我們知道，邊連通度是反映圖的連通性質(zhì)的一個(gè)重要參數(shù)而要精確地刻畫(huà)圖的連通性質(zhì)，經(jīng)典邊連通度

2、存在著不足之處：首先，邊連通度相同的圖可靠度可能不同其次，不能區(qū)分刪掉K個(gè)割斷點(diǎn)或A條割斷邊得到的圖的不同類(lèi)型，即未考慮對(duì)網(wǎng)絡(luò)的傷害程度第三，默認(rèn)圖的任何子集中所有元素能潛在地同時(shí)失效為克服以上缺陷，自然要將經(jīng)典邊連通度的概念加以推廣自1983年日nrary[2j提出條件連通度的概念以來(lái)，經(jīng)過(guò)約二十年的發(fā)展，條件連通度所涉及的內(nèi)容日益豐富和具體，包括超級(jí)連通度、過(guò)邊連通度、限制邊連通度等設(shè)計(jì)和分析大規(guī)模網(wǎng)絡(luò)的可靠性和容錯(cuò)性時(shí)，通常包括某

3、些類(lèi)型的圖模型針對(duì)不同的模型，都有諸多相關(guān)理論問(wèn)題需要研究其中一個(gè)重要模型是這樣的網(wǎng)絡(luò)G：假設(shè)其節(jié)點(diǎn)不會(huì)失效，但節(jié)點(diǎn)間的連線(xiàn)可能相互獨(dú)立地以等概率，，失效則G不連通的概率為：￡P(guān)(Gp)=：Ckp“f1一p)。一“^=l其中P為G的邊數(shù)，G表示基數(shù)為而的邊割的數(shù)目，則圖G的可靠度為1一尸(Gjp)確定P(G：p)的大小問(wèn)題在可靠度的研究中受到了廣泛關(guān)注但P7’鍘。釘和Bof『f3]已經(jīng)證明，對(duì)一般圖G尸(G，p)的計(jì)算是A’尸一^nrc