交換超立方體網絡中路的可嵌入性分析.pdf

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

2、從超立方體中有條理的刪除一些邊得到的.交換超立方體保留了大多數超級立方體的優(yōu)良的性質，并且減少了網絡的復雜度.交換超立方體EH(s，t)與超立方體Qs+t+1的點數相同，而EH(s，t)的邊數幾乎只有Qs+t+1的一半.因此，交換超立方體EH(s，t)的性質具有研究價值.
　　 本文討論交換超立方體，主要研究EH(s，t)的哈密頓可蕾絲性和強哈密頓可蕾絲性，以及其寬直徑和容錯直徑.運用構造法和數學歸納法證明了:
　　 (

3、1)當s，t≥2時，EH(s，t)是哈密頓可蕾絲的，也是強哈密頓可蕾絲的;
　　 (2) EH(s，t)的寬直徑dω(EH(s，t))和容錯直徑Dω(EH(s，t))有如下關系:
　　 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(