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

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

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

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

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

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