交換超立方體網(wǎng)絡(luò)中路的可嵌入性分析.pdf

1、人們通常用連通的簡(jiǎn)單圖G=(V.E)來(lái)表示互連網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，其中圖G的頂點(diǎn)代表網(wǎng)絡(luò)中的組件，連線代表組件之間的通信聯(lián)系，而圖的嵌入問(wèn)題是研究互連網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的中心問(wèn)題之一，它的重要性在于我們可以將關(guān)于客圖的已有算法應(yīng)用于主圖.路的結(jié)構(gòu)簡(jiǎn)單，所以其上通信算法成本低，因此研究路的嵌入問(wèn)題是非常重要的.
　　 超立方體Qn是常見(jiàn)的互連網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)之一.交換超立方體(EH(s，t))作為超立方體的一個(gè)重要變型是由Loh等提出的，該圖是

2、從超立方體中有條理的刪除一些邊得到的.交換超立方體保留了大多數(shù)超級(jí)立方體的優(yōu)良的性質(zhì)，并且減少了網(wǎng)絡(luò)的復(fù)雜度.交換超立方體EH(s，t)與超立方體Qs+t+1的點(diǎn)數(shù)相同，而EH(s，t)的邊數(shù)幾乎只有Qs+t+1的一半.因此，交換超立方體EH(s，t)的性質(zhì)具有研究?jī)r(jià)值.
　　 本文討論交換超立方體，主要研究EH(s，t)的哈密頓可蕾絲性和強(qiáng)哈密頓可蕾絲性，以及其寬直徑和容錯(cuò)直徑.運(yùn)用構(gòu)造法和數(shù)學(xué)歸納法證明了:
　　 (

3、1)當(dāng)s，t≥2時(shí)，EH(s，t)是哈密頓可蕾絲的，也是強(qiáng)哈密頓可蕾絲的;
　　 (2) EH(s，t)的寬直徑dω(EH(s，t))和容錯(cuò)直徑Dω(EH(s，t))有如下關(guān)系:
　　 dω(EH(1，t))=Dω(EH(1，t))={t+3ω=1;t+5ω=2.其中t＞1,
　　 dω(EH(2，t))=Dω(EH(2，t))={t+4ω=1;t+5ω=2;t+6ω=3.其中t≥2，
　　 dω(EH(