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

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

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

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

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