容錯網絡中若干問題研究.pdf

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

2、靠性越高.目前，互連網絡最廣泛采用的拓撲結構是n維超立方體Qn，它的點連通度和邊連通度都是n.
　　 為了更準確地度量網絡的容錯性，人們根據網絡應用的實際推廣圖的連通度概念到超連通度.圖G的超點連通度κs(G)(或者超邊連通度λs(G))是最小點數(或者邊數)，這個數目的點集(或者邊集)從G中移走會導致剩下的圖不連通并且不含孤立點.
　　 Esfahanian(1989)已經證明：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)的整數e，Qn中存在一條不含故障邊且長為e的uv路.這個結果改進了許多有關超立方體網絡邊容錯泛圈性和泛連通性的已知結果，也為超立方體網絡的高容錯性提供更有力的理論證據.
　　 本文的另一部分是研究超立方體的變形網絡VQn和超立方體的推廣-置換圖(G0，G1；M)的超點連通度和超邊連通度.證明了VQn的點連通度和邊連通度都是n，超點連通度和超邊連通度都是2n-2.對于兩個k正則k連通圖G0和G1的置換圖G=G