容錯網(wǎng)絡(luò)中若干問題研究.pdf

1、本文考慮互連網(wǎng)絡(luò)中的容錯性和容錯網(wǎng)絡(luò)的路嵌入問題.習(xí)知，互連網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)可以用圖G=(V,E)來作為數(shù)學(xué)模型，圖G中的點(diǎn)表示互連網(wǎng)絡(luò)中的元件，G中的邊表示元件之間的通信連線.那么，圖G的點(diǎn)連通度κ(G)和邊連通度λ(G)則是該互連網(wǎng)絡(luò)可靠性的重要度量參數(shù).它們表明對應(yīng)的互連網(wǎng)絡(luò)可以容許κ(G)-1個元件或者λ(G)-1條連線同時發(fā)生故障的情況下，剩余網(wǎng)絡(luò)的元件之間仍能保持通信.所以，圖的點(diǎn)連通度或者邊連通度越大，它所模擬的互連網(wǎng)絡(luò)的可

2、靠性越高.目前，互連網(wǎng)絡(luò)最廣泛采用的拓?fù)浣Y(jié)構(gòu)是n維超立方體Qn，它的點(diǎn)連通度和邊連通度都是n.
　　 為了更準(zhǔn)確地度量網(wǎng)絡(luò)的容錯性，人們根據(jù)網(wǎng)絡(luò)應(yīng)用的實(shí)際推廣圖的連通度概念到超連通度.圖G的超點(diǎn)連通度κs(G)(或者超邊連通度λs(G))是最小點(diǎn)數(shù)(或者邊數(shù))，這個數(shù)目的點(diǎn)集(或者邊集)從G中移走會導(dǎo)致剩下的圖不連通并且不含孤立點(diǎn).
　　 Esfahanian(1989)已經(jīng)證明：n維超立方體Qn的超點(diǎn)連通度和超邊連通度

3、都是2n-2.這意味著，即使Qn中有2n-3條邊同時發(fā)生故障，只要確保每個點(diǎn)關(guān)聯(lián)至少一條非故障邊，那么Qn中任何兩個非故障點(diǎn)之間仍然存在由非故障邊組成的路.徐俊明等人(2003)證明了：當(dāng)Qn(n≥4)至多有2n-3條故障邊，而且每個點(diǎn)關(guān)聯(lián)至少一條非故障邊時，對于Qn中任何兩點(diǎn)u和v，如果它們之間的距離d滿足2≤d≤n-2且n≥4，那么u和v之間存在長不超過d+4且不含故障邊的路.另一方面，Chan和Lee(1991)證明了：Qn(n≥

4、3)存在2n-4條故障邊，而且每個點(diǎn)關(guān)聯(lián)至少兩條非故障邊，但Qn中不存在不含故障邊的Hamilton圈.這個事實(shí)說明：如果Qn(n≥3)有2n-4條故障邊，而且每個點(diǎn)關(guān)聯(lián)至少兩條非故障邊，那么，對于一條非故障邊uv，Qn中有可能不存在不含故障邊且長為2n-1的uv路.
　　 本文證明了：如果Qn(n≥3)至多有2n-5條故障邊，而且每個點(diǎn)關(guān)聯(lián)至少兩條非故障邊，那么對Qn中任何不同兩點(diǎn)u和v，其距離為d和滿足d+4≤e≤2n-1和

5、e-d≡0(mod2)的整數(shù)e，Qn中存在一條不含故障邊且長為e的uv路.這個結(jié)果改進(jìn)了許多有關(guān)超立方體網(wǎng)絡(luò)邊容錯泛圈性和泛連通性的已知結(jié)果，也為超立方體網(wǎng)絡(luò)的高容錯性提供更有力的理論證據(jù).
　　 本文的另一部分是研究超立方體的變形網(wǎng)絡(luò)VQn和超立方體的推廣-置換圖(G0，G1；M)的超點(diǎn)連通度和超邊連通度.證明了VQn的點(diǎn)連通度和邊連通度都是n，超點(diǎn)連通度和超邊連通度都是2n-2.對于兩個k正則k連通圖G0和G1的置換圖G=G