圖的脆弱性參數(shù)研究.pdf

1、在設(shè)計(jì)計(jì)算機(jī)網(wǎng)絡(luò)和通訊網(wǎng)絡(luò)時(shí)，為了避免和最大限度減少因網(wǎng)絡(luò)通訊中斷而帶來的損失，設(shè)計(jì)者必須考慮網(wǎng)絡(luò)的穩(wěn)定性．因此，網(wǎng)絡(luò)設(shè)計(jì)的基本思想之一便是使其在受到外部攻擊時(shí)，不容易被破壞；更進(jìn)一步，如果真的受到破壞，它們也比較容易被修復(fù)重建．一個計(jì)算機(jī)網(wǎng)絡(luò)或者通訊網(wǎng)絡(luò)，可以用一個連通圖來表示，其中圖的頂點(diǎn)表示通訊站，邊表示兩個通訊站之間可以直接通訊的通訊線路．對于一個網(wǎng)絡(luò)，它的穩(wěn)定性常用它所對應(yīng)的圖的脆弱性參數(shù)描述． 早期在脆弱性參數(shù)方面的

2、研究，主要是圍繞連通度和邊連通度展開的．這兩個參數(shù)被廣泛用來描述圖的脆弱性，而且已被證明，它們的計(jì)算存在多項(xiàng)式時(shí)間算法．由于這兩個參數(shù)在描述圖的脆弱性方面具有局限性，近年來人們陸續(xù)引入了一些其它脆弱性參數(shù)，主要包括了堅(jiān)韌度和邊堅(jiān)韌度，離散數(shù)，完整度和邊完整度，粘連度和邊粘連度，毀裂度，鄰域連通度和邊鄰域連通度，鄰域完整度和邊鄰域完整度，鄰域離散數(shù)和邊鄰域離散數(shù)．與連通度和邊連通度不同，這些參數(shù)不僅考慮了破壞網(wǎng)絡(luò)的難易程度，還考慮了網(wǎng)絡(luò)遭

3、受破壞的程度． 本文主要研究了圖的(邊)鄰域離散數(shù)、毀裂度、完整度和弱完整度等幾個脆弱性參數(shù)，分五章討論了以下幾個問題： 第一章主要介紹了這些脆弱性參數(shù)的定義以及它們的研究背景、研究現(xiàn)狀和本文的一些研究成果． 第二章主要討論了一般圖及連通二部圖的鄰域離散數(shù)的上下界，并證明了二部圖鄰域離散數(shù)的計(jì)算是一個NP-完全問題． 第三章主要討論了一般圖的邊鄰域離散數(shù)的界并給出了計(jì)算公式，構(gòu)造了邊鄰域離散數(shù)意義下的最大