幾類(lèi)特殊圖的脆弱性參數(shù).pdf

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

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

3、難易程度，還考慮了網(wǎng)絡(luò)遭受破壞的程度。 但已被證明的是計(jì)算一般圖的這些參數(shù)是NP-困難問(wèn)題。因此研究特殊圖類(lèi)的這些參數(shù)就十分有意義。在本文中，我們主要討論了三類(lèi)圖：分割圖，刺圖和路和圈笛卡爾積的脆弱性參數(shù)。 本文第一章首先介紹了這些脆弱性參數(shù)，并總結(jié)了一些基本圖類(lèi)(路，圈，星狀圖，彗星圖，完全k-部圖等)關(guān)于這些參數(shù)的研究結(jié)果以及本文的研究成果。 第二章簡(jiǎn)要介紹了分割圖的性質(zhì)，討論了分割圖的脆弱性參數(shù)的計(jì)算問(wèn)題。