邊故障的超立方體和k-ary n-立方體中路及測地圈的嵌入問題.pdf

1、超立方體(Qn)和k-ary n-立方體(Qkn)是常見的網(wǎng)絡拓撲結構.它們具有很多優(yōu)良的性質，如遞歸結構，結構對稱，網(wǎng)絡尋路算法簡單等特點.環(huán)和線性陣列是并行分布計算最基本的兩個網(wǎng)絡結構.有許多基于它們設計出的高效低成本的算法.因而給出網(wǎng)絡各種長度的路和圈是人們感興趣的.各種互聯(lián)網(wǎng)絡最中心問題之一是尋找點不交的路.由于高效率通信網(wǎng),容錯路由等方面的應用，尋找網(wǎng)絡中點不交的路問題備受關注.大型系統(tǒng)在運行時難免會出現(xiàn)一些故障，因此研究超立

2、方體和k-ary n立方體點不交路和測地圈嵌入時考慮容錯性是具有重要的現(xiàn)實意義.在這篇論文中，我們的主要結果如下:
　　 (1)令F是Q3n(n≥2)的邊集，∣F∣≤2n-4，令x1,x2,y1,y2是Q3n中任意4個頂點，則在Q3n-F中存在兩條頂點不交的路P1和P2，使得，V(P1)∪V(P2)=V(Q3n)這里P1連接x1和y1,P2連接x2和y2.
　　 (2)當n≥3，令超立方體中的邊故障集∣F∣≤n-3，設x

3、1,x2,y1,y2是Qn中任意4個頂點，使得距離d(x1,y1)和距離d(x1,y2)都是奇數(shù)，則在Qn-F中存在兩條點不交路P1和P2，使得V(P1)∪V(P2)=V(Qn)，這里P1連接x1和y1，P2連接x2和y2，而且故障邊數(shù)的上界是緊的.
　　 (3)假設u=(u1,u2…un)和v=(v1,v2…vn)是Qkn(n≥2,k≥3)中任意2個頂點,令di=min{∣u1-v1∣,k-∣ui-vi∣},這里0≤di≤k2

4、(I=1,…n)，記d=d1+d2+…dn≥1,N=kn,對于每個偶數(shù)l適合2d+2≤l≤n，則Qkn中有過u和長為l的圈C,且C上u和v的距離為d.并且當且僅當有I和j滿足1≤I