计算机工程与应用
計算機工程與應用
계산궤공정여응용
COMPUTER ENGINEERING AND APPLICATIONS
2005年
32期
83-86
,共4页
刘昕%樊建席%宗绪锋%徐翠霞
劉昕%樊建席%宗緒鋒%徐翠霞
류흔%번건석%종서봉%서취하
互连网络%HCH-立方体%超立方体%交叉立方体%Hamilton-路%Hamilton连通性
互連網絡%HCH-立方體%超立方體%交扠立方體%Hamilton-路%Hamilton連通性
호련망락%HCH-립방체%초립방체%교차립방체%Hamilton-로%Hamilton련통성
新型并行计算系统的研制依赖于对新型互连网络结构及其性质的研究.超立方体及其变型--交叉立方体具有优点,也具有缺点.文献[1]给出了在超立方体与交叉立方体的顶点之间的一种连接--超连接,从而得到了一种称为HCH-立方体的互连网络,文章证明了当n≥4,HCH-立方体任意两个顶点之间存在Hamilton路径,即HCH-立方体是Hamilton连通的,而超立方体不是Hamilton连通的.这表明HCH-立方体具备了交叉立方体在Hamilton连通性方面的性质.文章还给出了在n维HCH-立方体中构造任意两个顶点之间Hamilton路径的算法,该算法的时间复杂度为O(N),其中N=2n,为n维HCH-立方体的顶点个数.
新型併行計算繫統的研製依賴于對新型互連網絡結構及其性質的研究.超立方體及其變型--交扠立方體具有優點,也具有缺點.文獻[1]給齣瞭在超立方體與交扠立方體的頂點之間的一種連接--超連接,從而得到瞭一種稱為HCH-立方體的互連網絡,文章證明瞭噹n≥4,HCH-立方體任意兩箇頂點之間存在Hamilton路徑,即HCH-立方體是Hamilton連通的,而超立方體不是Hamilton連通的.這錶明HCH-立方體具備瞭交扠立方體在Hamilton連通性方麵的性質.文章還給齣瞭在n維HCH-立方體中構造任意兩箇頂點之間Hamilton路徑的算法,該算法的時間複雜度為O(N),其中N=2n,為n維HCH-立方體的頂點箇數.
신형병행계산계통적연제의뢰우대신형호련망락결구급기성질적연구.초립방체급기변형--교차립방체구유우점,야구유결점.문헌[1]급출료재초립방체여교차립방체적정점지간적일충련접--초련접,종이득도료일충칭위HCH-립방체적호련망락,문장증명료당n≥4,HCH-립방체임의량개정점지간존재Hamilton로경,즉HCH-립방체시Hamilton련통적,이초립방체불시Hamilton련통적.저표명HCH-립방체구비료교차립방체재Hamilton련통성방면적성질.문장환급출료재n유HCH-립방체중구조임의량개정점지간Hamilton로경적산법,해산법적시간복잡도위O(N),기중N=2n,위n유HCH-립방체적정점개수.
