超立方體Qn中路和樹的研究.pdf

1、互連網(wǎng)絡(luò)(Interconnection Network)融合了計算機(jī)科學(xué)、信息化技術(shù)、通信工程、數(shù)學(xué)等多學(xué)科多領(lǐng)域的知識,是高性能并行計算機(jī)的主要研究課題之一?；ミB網(wǎng)絡(luò)的結(jié)構(gòu)多種多樣,超立方體(Hypercube)就是該領(lǐng)域里較早提出的優(yōu)秀網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)之一。它高度的對稱性、正則性、短直徑性、強(qiáng)容錯性、可靠性、可嵌入性、可擴(kuò)展性以及網(wǎng)絡(luò)良好的通信能力等優(yōu)點(diǎn),深受學(xué)者們和業(yè)內(nèi)人士的喜歡,引起了國內(nèi)外專家學(xué)者們的長期關(guān)注,成為近些年來國際研

2、究的熱點(diǎn)之一。
　　本文針對n維超立方體Qn的拓?fù)浣Y(jié)構(gòu),基于其節(jié)點(diǎn)編碼的特點(diǎn),得到了求超立方體Qn中指定條件下的最短路算法,并且利用避圈法,依據(jù)廣度優(yōu)先策略,給出了在超立方體Qn中找一棵生成樹的算法,最后在理論分析的基礎(chǔ)上,得到關(guān)于超立方體Qn中邊不交生成樹棵數(shù)上界和下界的兩個定理。具體的研究結(jié)果如下:
　　1.給出了求超立方體Qn中從始點(diǎn)s到達(dá)終點(diǎn)t的一條最短路徑算法;
　　2.給出了求超立方體Qn中從始點(diǎn)s到達(dá)終點(diǎn)

3、t且邊不交的最優(yōu)路徑算法;
　　3.給出了求超立方體Qn中從始點(diǎn)s到達(dá)終點(diǎn)t且經(jīng)過指定節(jié)點(diǎn) vkv1, v2,……,(k　　4.給出了超立方體Qn中尋找一棵最小生成樹的算法;
　　5.給出了超立方體Qn中邊不交的生成樹棵樹的上界和下界:(1) Qn中邊不交的生成樹最多有棵,即(2)當(dāng)4時, nQ中至少存在2棵邊不交的生成樹,即
　　在每個重要算法給出之前,文中都交代了其算法思想,并且給出了