超立方體和蜂窩矩形環(huán)托中的圈和路嵌入.pdf

1、圖的嵌入問題是衡量一個(gè)互連網(wǎng)絡(luò)的中心問題之一，它的重要性在于我們可以將關(guān)于客圖的已有算法應(yīng)用到主圖中．環(huán)和線性陣列由于通信成本低廉，因而是并行處理和分布計(jì)算中的兩個(gè)基本網(wǎng)絡(luò)結(jié)構(gòu)．一個(gè)網(wǎng)絡(luò)若含有哈密爾頓圈或哈密爾頓路，就能夠有效模擬許多為環(huán)和線性陣列設(shè)計(jì)的算法，因此有效的圈或路嵌入是設(shè)計(jì)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的基本要求．大型系統(tǒng)在使用過程中它的某些連線或結(jié)點(diǎn)難免發(fā)生故障，因此在并行計(jì)算中，一個(gè)互連網(wǎng)絡(luò)的容錯(cuò)能力是一個(gè)關(guān)鍵性的因素．研究存在故障的系統(tǒng)

2、具有重要的實(shí)際意義．
　　 超立方體和蜂窩矩形環(huán)托是兩種常見的互聯(lián)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)．N維超立方體(記為Qn)是含有2n個(gè)頂點(diǎn)的n正則二部圖，蜂窩矩形環(huán)托(honeycomb rectangulartorus，記為HReT(m，n))是由環(huán)托(torus，一種網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，即兩個(gè)圈的笛卡爾乘積)適當(dāng)刪除一些邊后得到的3正則圖．它們都具有許多優(yōu)良的拓?fù)湫再|(zhì)，已被應(yīng)用于并行處理和分布計(jì)算系統(tǒng)中．
　　 本文研究了以下兩個(gè)問題：

3、r>　　 (1)在有故障邊的超立方體中通過給定線性森林(即每個(gè)分支是路的子圖)的無故障圈的嵌入問題；
　　 (2)在有故障邊的蜂窩矩形環(huán)托HReT(m，n)中的無故障哈密爾頓圈嵌入和蜂窩矩形環(huán)托HReT(m，n)中哈密爾頓可跡性(Hamiltonian-laceability)問題，并得到了以下結(jié)果：
　　 1、在超立方體中通過給定3條邊的圈嵌入；
　　 2、在有故障邊的超立方體中通過給定線性森林的無故障圈嵌入