幾類互連網(wǎng)絡(luò)的容錯哈密頓性.pdf

1、將互連網(wǎng)絡(luò)中的每個處理器抽象成一個點,把處理器之間的信道抽象成兩點之間的連線,那么一個互連網(wǎng)絡(luò)就可以抽象成一個圖,稱之為互聯(lián)網(wǎng)絡(luò)拓撲結(jié)構(gòu),網(wǎng)絡(luò)的拓撲結(jié)構(gòu)決定著該網(wǎng)絡(luò)的性能.由于互聯(lián)網(wǎng)絡(luò)的拓撲結(jié)構(gòu)就是圖,所以圖論是設(shè)計和分析互連網(wǎng)絡(luò)的最基本且強有力的數(shù)學(xué)工具。
　　 可嵌入性是衡量網(wǎng)絡(luò)優(yōu)劣的一個重要性能，由于用含有圈拓撲結(jié)構(gòu)的圖設(shè)計出來的網(wǎng)絡(luò)通訊成本低,而且泛圈性和泛連通性也可以看成是圖的哈密頓性研究的擴展,因此圈嵌入是一個重要問

2、題。由于網(wǎng)絡(luò)的節(jié)點和鏈接都可能發(fā)生故障,所以需要研究網(wǎng)絡(luò)的容錯性,這是評估網(wǎng)絡(luò)性能時所考慮的主要因素之一。
　　 交替群圖作為計算機系統(tǒng)的一種互聯(lián)網(wǎng)絡(luò)拓撲結(jié)構(gòu),具有許多比超立方體和星圖更好的性質(zhì),也符合網(wǎng)絡(luò)設(shè)計高性能、低成本的原則要求。本文研究了交替群圖等幾類著名互聯(lián)網(wǎng)絡(luò)的容錯圈嵌入、最大邊連通、網(wǎng)絡(luò)設(shè)計等問題,主要研究工作如下:
　　 (1)研究了交替群圖的容錯哈密頓性和容錯哈密頓連通性.對于一個n-維交替群圖AGn,

3、證明了當n≥4時,AGn是(2n-6)-容錯哈密頓和(2n-6)-容錯泛圈的,并且是(2n-7)-容錯哈密頓連通的.本文所給的結(jié)果關(guān)于交替群圖的正則度是最優(yōu)的,也是對以前J.-M.Chang等人所給結(jié)果的改進。
　　 (2)定義了匹配組合網(wǎng)絡(luò)G=G(V1∪V2,E1∪E2∪M),其中M是V1和V2之間的一個完全匹配。研究了G的限制連通度,G的直徑的上下界與G1的直徑、G2的直徑和完全匹配M的關(guān)系,通過G1和G2的階確定了幾類特殊

4、匹配組合網(wǎng)絡(luò)G直徑的上下界,最后討論了G1和G2的泛圈性和泛連通性與G的泛圈性和泛連通性之間的關(guān)系。
　　 (3)用凸函數(shù)的性質(zhì)和數(shù)論知識研究了連通圖的倒數(shù)度的上界,給出了一個連通圖是最大邊連通的條件,為研究超連通或超邊連通圖提供了新的方法。通過例子說明所給結(jié)果用于判斷一個連通圖是否是最大邊連通圖是有效的。
　　 (4)線圖方法、笛卡兒乘積方法和代數(shù)方法是互聯(lián)網(wǎng)絡(luò)設(shè)計常用的三種方法。本文用代數(shù)方法對任何含有最小元素的偏序