張涌逸

摘要：本文我們提出了局部m維子立方體不連通的廣義n-維超立方體的概念，討論了局部m維子立方體不連通的廣義n-維超立方體的連通性，給出了基于局部m維子立方體不連通的廣義n-維超立方體的路由算法，分析了時(shí)間復(fù)雜度。

關(guān)鍵詞：廣義n-維超立方體 局部m維子立方體不連通的廣義n-維超立方體 容錯(cuò)路由 算法

中圖分類號(hào)：TP302.8 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1007-9416（2014）08-0037-01

1 引言

對(duì)并行處理器的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，人們已經(jīng)提出了各種各樣的模型，有些也已經(jīng)用到了實(shí)際的應(yīng)用中，在這些模型中超立方體是常見的模型之一，由于它有良好的性能，人們對(duì)它討論很多，它也有各種各樣的變形，廣義超立方體就是它的一種變形。隨著電子技術(shù)的發(fā)展，并行處理器數(shù)目越來越多，處理器出錯(cuò)誤的可能性也越來越大。如何在節(jié)點(diǎn)出現(xiàn)錯(cuò)誤（及結(jié)點(diǎn)不能參與傳輸數(shù)據(jù)）的情況下，仍然能把數(shù)據(jù)從源節(jié)點(diǎn)傳輸?shù)侥康慕Y(jié)點(diǎn)，也及容錯(cuò)成為人們越來越關(guān)注的問題。在文獻(xiàn)[1]中討論了具有局部連通性的廣義超立方體中的容錯(cuò)路由問題，容錯(cuò)結(jié)點(diǎn)個(gè)數(shù)小于結(jié)點(diǎn)個(gè)數(shù)的一半。本文進(jìn)一步討論了廣義超立方體中的容錯(cuò)路由，容錯(cuò)結(jié)點(diǎn)個(gè)數(shù)可超過一半以上，同時(shí)不需要所有的廣義n-維超立方體的m子立方體正確結(jié)點(diǎn)都須具有連通性，只需有一個(gè)m子立方體連通即可。

2 局部m維子立方體不連通的廣義n-維超立方體中的容錯(cuò)路由

廣義n-維超立方體：它的結(jié)點(diǎn)集V={x1x2…xn：0xiti-1，ti為整數(shù)，i=1，2，…，n}，兩個(gè)結(jié)點(diǎn)有邊相連當(dāng)且僅當(dāng)對(duì)應(yīng)的位有一位不同。為討論方便，取t1=t2=…=tn=k>1。

廣義n-維超立方體的m子立方體：結(jié)點(diǎn)集S={x1x2…xn-mkn-m+1

kn-m+2…kn：0kik，i= n-m+1，n-m+2，…，n}（xi為0到k之間確定的整數(shù)，i=0，1，…，n-m），兩個(gè)結(jié)點(diǎn)有邊相連當(dāng)且僅當(dāng)對(duì)應(yīng)的位有一位不同。簡記為x1x2…xn-m+1*，稱x1x2…xn-m為廣義超立方體的m子立方體的標(biāo)記。

局部m維子立方體不連通的廣義n-維超立方體：在廣義n-維超立方體中的每個(gè)m子立方體中的正確結(jié)點(diǎn)所在的連通分支中有一個(gè)正確結(jié)點(diǎn)和鄰接m子立方體中的正確結(jié)點(diǎn)相鄰接，且至少有一個(gè)m子立方體中的正確結(jié)點(diǎn)構(gòu)成連通圖。

從局部m維子立方體不連通的廣義n-維超立方體定義可以看出，不需要所有的m子立方體的正確結(jié)點(diǎn)構(gòu)成連通圖。也不需要m子立方體錯(cuò)誤結(jié)點(diǎn)數(shù)少于正確結(jié)點(diǎn)數(shù)，這樣錯(cuò)誤結(jié)點(diǎn)個(gè)數(shù)可突破結(jié)點(diǎn)個(gè)數(shù)可突破一半的限制。

定理：局部m維子立方體不連通的廣義n-維超立方體是連通圖。

證明：對(duì)于廣義n-維超立方體任意兩個(gè)結(jié)點(diǎn)S=s1s2…sn、T=t1t2…tn，以及一個(gè)正確結(jié)點(diǎn)連通的m子立方體W=w1w2…wn-m*。首先我們說明S和W中某個(gè)正確結(jié)點(diǎn)相連。由S=s1s2…sn，知S所在的m子立方體為s1s2…sn-m*，從前到后比較s1s2…sn-m和w1w2…wn-m對(duì)應(yīng)得位，設(shè)s1s2…sn-m+1中w1w2…wn-m對(duì)應(yīng)得第一個(gè)不同的位為，找S在w1w2……sn-m+1*中連通分支和w1w2……sn-m+1*中的一對(duì)正確的鄰接點(diǎn)T1、T2，知S到T2連通。再從T2起，重復(fù)上述過程，直到W中有正確結(jié)點(diǎn)和S相鄰。同理有W中也有正確結(jié)點(diǎn)和T相鄰。又W中的正確結(jié)點(diǎn)構(gòu)成連通圖，知S和T連通。命題得證。

上面的證明過程也就是局部m維子立方體不連通的廣義n-維超立方體容錯(cuò)路由的算法思想。下面我們根據(jù)這個(gè)想法給出算法。

算法：局部m維子立方體不連通的廣義n-維超立方體路由算法：

輸入：在局部m維子立方體不連通的廣義n-維超立方體輸入一對(duì)正確結(jié)點(diǎn)S、T。

輸出：輸出一條從S到T的路徑。

輸入S=s1s2…sn、T=t1t2…tn（si和t1為0到k之間確定的整數(shù)）

尋找一個(gè)正確結(jié)點(diǎn)連通的m子立方體W=w1w2…wn-m*；

路徑加入：P1=S；

（1）for（ i：=1；in-m；i++）

if（siwi）{1）搜索S在w1w2……sn-m*中連通分支和w1w2……sn-m*中的一對(duì)正確的鄰接點(diǎn)T1、T2；2）路徑加入：P1=在w1w2……sn-m*搜索到的S到T1的路徑及結(jié)點(diǎn)T2；}

（2）路徑加入：P2=T；

（3）for（ i：=1；in-m；i++）

if（tiwi）{1）搜索T在w1w2……tn-m*中連通分支和w1w2……tn-m*中的一對(duì)正確的鄰接點(diǎn)S1、S2；2）路徑加入：P2=在w1w2……tn-m*搜索到的S到S1的路徑及結(jié)點(diǎn)S2；}

（4）取出（1）、（3）中最后一個(gè)結(jié)點(diǎn)U、V，在W中尋找U到V，并添加到P1；

（5）把P2的路徑取反然后添加到P1；

算法在（2）中尋找一個(gè)正確結(jié)點(diǎn)連通的m子立方體需要時(shí)間0（k（n-m）km）。算法（1）需要時(shí)間0（2（n-m）km）。故整個(gè)算法時(shí)間復(fù)雜度為0（3kn）。

3 結(jié)語

我們在局部廣義k-維子立方體連通性基礎(chǔ)上進(jìn)一步提出了局部m維子立方體不連通的廣義n-維超立方體的概念。之后我們證明了此類廣義n-維超立方體是連通的，并提出了路由算法。通過分析得到的時(shí)間復(fù)雜度是0（3kn）。此時(shí)間復(fù)雜度要比廣度搜索時(shí)間復(fù)雜度大，但算法是基于局部信息且不需要所有的廣義n-維超立方體的m子立方體正確結(jié)點(diǎn)連通，同時(shí)還擴(kuò)大了容錯(cuò)性。

參考文獻(xiàn)

[1]劉紅美.廣義超立方體網(wǎng)絡(luò)容錯(cuò)路由算法[J].武漢理工大學(xué)學(xué)報(bào)：交通科學(xué)與工程版，2006，30（4）：682-685.

[2]王國軍，陳建二，陳松喬.具有大量錯(cuò)誤結(jié)點(diǎn)的超立方體網(wǎng)絡(luò)的高效路由算法的設(shè)計(jì)與討論[J].計(jì)算機(jī)學(xué)報(bào)，2001，24（9）：909-916.

摘要：本文我們提出了局部m維子立方體不連通的廣義n-維超立方體的概念，討論了局部m維子立方體不連通的廣義n-維超立方體的連通性，給出了基于局部m維子立方體不連通的廣義n-維超立方體的路由算法，分析了時(shí)間復(fù)雜度。

關(guān)鍵詞：廣義n-維超立方體 局部m維子立方體不連通的廣義n-維超立方體 容錯(cuò)路由 算法

中圖分類號(hào)：TP302.8 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1007-9416（2014）08-0037-01

1 引言

對(duì)并行處理器的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，人們已經(jīng)提出了各種各樣的模型，有些也已經(jīng)用到了實(shí)際的應(yīng)用中，在這些模型中超立方體是常見的模型之一，由于它有良好的性能，人們對(duì)它討論很多，它也有各種各樣的變形，廣義超立方體就是它的一種變形。隨著電子技術(shù)的發(fā)展，并行處理器數(shù)目越來越多，處理器出錯(cuò)誤的可能性也越來越大。如何在節(jié)點(diǎn)出現(xiàn)錯(cuò)誤（及結(jié)點(diǎn)不能參與傳輸數(shù)據(jù)）的情況下，仍然能把數(shù)據(jù)從源節(jié)點(diǎn)傳輸?shù)侥康慕Y(jié)點(diǎn)，也及容錯(cuò)成為人們越來越關(guān)注的問題。在文獻(xiàn)[1]中討論了具有局部連通性的廣義超立方體中的容錯(cuò)路由問題，容錯(cuò)結(jié)點(diǎn)個(gè)數(shù)小于結(jié)點(diǎn)個(gè)數(shù)的一半。本文進(jìn)一步討論了廣義超立方體中的容錯(cuò)路由，容錯(cuò)結(jié)點(diǎn)個(gè)數(shù)可超過一半以上，同時(shí)不需要所有的廣義n-維超立方體的m子立方體正確結(jié)點(diǎn)都須具有連通性，只需有一個(gè)m子立方體連通即可。

2 局部m維子立方體不連通的廣義n-維超立方體中的容錯(cuò)路由

廣義n-維超立方體：它的結(jié)點(diǎn)集V={x1x2…xn：0xiti-1，ti為整數(shù)，i=1，2，…，n}，兩個(gè)結(jié)點(diǎn)有邊相連當(dāng)且僅當(dāng)對(duì)應(yīng)的位有一位不同。為討論方便，取t1=t2=…=tn=k>1。

廣義n-維超立方體的m子立方體：結(jié)點(diǎn)集S={x1x2…xn-mkn-m+1

kn-m+2…kn：0kik，i= n-m+1，n-m+2，…，n}（xi為0到k之間確定的整數(shù)，i=0，1，…，n-m），兩個(gè)結(jié)點(diǎn)有邊相連當(dāng)且僅當(dāng)對(duì)應(yīng)的位有一位不同。簡記為x1x2…xn-m+1*，稱x1x2…xn-m為廣義超立方體的m子立方體的標(biāo)記。

局部m維子立方體不連通的廣義n-維超立方體：在廣義n-維超立方體中的每個(gè)m子立方體中的正確結(jié)點(diǎn)所在的連通分支中有一個(gè)正確結(jié)點(diǎn)和鄰接m子立方體中的正確結(jié)點(diǎn)相鄰接，且至少有一個(gè)m子立方體中的正確結(jié)點(diǎn)構(gòu)成連通圖。

從局部m維子立方體不連通的廣義n-維超立方體定義可以看出，不需要所有的m子立方體的正確結(jié)點(diǎn)構(gòu)成連通圖。也不需要m子立方體錯(cuò)誤結(jié)點(diǎn)數(shù)少于正確結(jié)點(diǎn)數(shù)，這樣錯(cuò)誤結(jié)點(diǎn)個(gè)數(shù)可突破結(jié)點(diǎn)個(gè)數(shù)可突破一半的限制。

定理：局部m維子立方體不連通的廣義n-維超立方體是連通圖。

證明：對(duì)于廣義n-維超立方體任意兩個(gè)結(jié)點(diǎn)S=s1s2…sn、T=t1t2…tn，以及一個(gè)正確結(jié)點(diǎn)連通的m子立方體W=w1w2…wn-m*。首先我們說明S和W中某個(gè)正確結(jié)點(diǎn)相連。由S=s1s2…sn，知S所在的m子立方體為s1s2…sn-m*，從前到后比較s1s2…sn-m和w1w2…wn-m對(duì)應(yīng)得位，設(shè)s1s2…sn-m+1中w1w2…wn-m對(duì)應(yīng)得第一個(gè)不同的位為，找S在w1w2……sn-m+1*中連通分支和w1w2……sn-m+1*中的一對(duì)正確的鄰接點(diǎn)T1、T2，知S到T2連通。再從T2起，重復(fù)上述過程，直到W中有正確結(jié)點(diǎn)和S相鄰。同理有W中也有正確結(jié)點(diǎn)和T相鄰。又W中的正確結(jié)點(diǎn)構(gòu)成連通圖，知S和T連通。命題得證。

上面的證明過程也就是局部m維子立方體不連通的廣義n-維超立方體容錯(cuò)路由的算法思想。下面我們根據(jù)這個(gè)想法給出算法。

算法：局部m維子立方體不連通的廣義n-維超立方體路由算法：

輸入：在局部m維子立方體不連通的廣義n-維超立方體輸入一對(duì)正確結(jié)點(diǎn)S、T。

輸出：輸出一條從S到T的路徑。

輸入S=s1s2…sn、T=t1t2…tn（si和t1為0到k之間確定的整數(shù)）

尋找一個(gè)正確結(jié)點(diǎn)連通的m子立方體W=w1w2…wn-m*；

路徑加入：P1=S；

（1）for（ i：=1；in-m；i++）

if（siwi）{1）搜索S在w1w2……sn-m*中連通分支和w1w2……sn-m*中的一對(duì)正確的鄰接點(diǎn)T1、T2；2）路徑加入：P1=在w1w2……sn-m*搜索到的S到T1的路徑及結(jié)點(diǎn)T2；}

（2）路徑加入：P2=T；

（3）for（ i：=1；in-m；i++）

if（tiwi）{1）搜索T在w1w2……tn-m*中連通分支和w1w2……tn-m*中的一對(duì)正確的鄰接點(diǎn)S1、S2；2）路徑加入：P2=在w1w2……tn-m*搜索到的S到S1的路徑及結(jié)點(diǎn)S2；}

（4）取出（1）、（3）中最后一個(gè)結(jié)點(diǎn)U、V，在W中尋找U到V，并添加到P1；

（5）把P2的路徑取反然后添加到P1；

算法在（2）中尋找一個(gè)正確結(jié)點(diǎn)連通的m子立方體需要時(shí)間0（k（n-m）km）。算法（1）需要時(shí)間0（2（n-m）km）。故整個(gè)算法時(shí)間復(fù)雜度為0（3kn）。

3 結(jié)語

我們在局部廣義k-維子立方體連通性基礎(chǔ)上進(jìn)一步提出了局部m維子立方體不連通的廣義n-維超立方體的概念。之后我們證明了此類廣義n-維超立方體是連通的，并提出了路由算法。通過分析得到的時(shí)間復(fù)雜度是0（3kn）。此時(shí)間復(fù)雜度要比廣度搜索時(shí)間復(fù)雜度大，但算法是基于局部信息且不需要所有的廣義n-維超立方體的m子立方體正確結(jié)點(diǎn)連通，同時(shí)還擴(kuò)大了容錯(cuò)性。

參考文獻(xiàn)

[1]劉紅美.廣義超立方體網(wǎng)絡(luò)容錯(cuò)路由算法[J].武漢理工大學(xué)學(xué)報(bào)：交通科學(xué)與工程版，2006，30（4）：682-685.

[2]王國軍，陳建二，陳松喬.具有大量錯(cuò)誤結(jié)點(diǎn)的超立方體網(wǎng)絡(luò)的高效路由算法的設(shè)計(jì)與討論[J].計(jì)算機(jī)學(xué)報(bào)，2001，24（9）：909-916.

摘要：本文我們提出了局部m維子立方體不連通的廣義n-維超立方體的概念，討論了局部m維子立方體不連通的廣義n-維超立方體的連通性，給出了基于局部m維子立方體不連通的廣義n-維超立方體的路由算法，分析了時(shí)間復(fù)雜度。

關(guān)鍵詞：廣義n-維超立方體 局部m維子立方體不連通的廣義n-維超立方體 容錯(cuò)路由 算法

中圖分類號(hào)：TP302.8 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1007-9416（2014）08-0037-01

1 引言

對(duì)并行處理器的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，人們已經(jīng)提出了各種各樣的模型，有些也已經(jīng)用到了實(shí)際的應(yīng)用中，在這些模型中超立方體是常見的模型之一，由于它有良好的性能，人們對(duì)它討論很多，它也有各種各樣的變形，廣義超立方體就是它的一種變形。隨著電子技術(shù)的發(fā)展，并行處理器數(shù)目越來越多，處理器出錯(cuò)誤的可能性也越來越大。如何在節(jié)點(diǎn)出現(xiàn)錯(cuò)誤（及結(jié)點(diǎn)不能參與傳輸數(shù)據(jù)）的情況下，仍然能把數(shù)據(jù)從源節(jié)點(diǎn)傳輸?shù)侥康慕Y(jié)點(diǎn)，也及容錯(cuò)成為人們越來越關(guān)注的問題。在文獻(xiàn)[1]中討論了具有局部連通性的廣義超立方體中的容錯(cuò)路由問題，容錯(cuò)結(jié)點(diǎn)個(gè)數(shù)小于結(jié)點(diǎn)個(gè)數(shù)的一半。本文進(jìn)一步討論了廣義超立方體中的容錯(cuò)路由，容錯(cuò)結(jié)點(diǎn)個(gè)數(shù)可超過一半以上，同時(shí)不需要所有的廣義n-維超立方體的m子立方體正確結(jié)點(diǎn)都須具有連通性，只需有一個(gè)m子立方體連通即可。

2 局部m維子立方體不連通的廣義n-維超立方體中的容錯(cuò)路由

廣義n-維超立方體：它的結(jié)點(diǎn)集V={x1x2…xn：0xiti-1，ti為整數(shù)，i=1，2，…，n}，兩個(gè)結(jié)點(diǎn)有邊相連當(dāng)且僅當(dāng)對(duì)應(yīng)的位有一位不同。為討論方便，取t1=t2=…=tn=k>1。

廣義n-維超立方體的m子立方體：結(jié)點(diǎn)集S={x1x2…xn-mkn-m+1

kn-m+2…kn：0kik，i= n-m+1，n-m+2，…，n}（xi為0到k之間確定的整數(shù)，i=0，1，…，n-m），兩個(gè)結(jié)點(diǎn)有邊相連當(dāng)且僅當(dāng)對(duì)應(yīng)的位有一位不同。簡記為x1x2…xn-m+1*，稱x1x2…xn-m為廣義超立方體的m子立方體的標(biāo)記。

局部m維子立方體不連通的廣義n-維超立方體：在廣義n-維超立方體中的每個(gè)m子立方體中的正確結(jié)點(diǎn)所在的連通分支中有一個(gè)正確結(jié)點(diǎn)和鄰接m子立方體中的正確結(jié)點(diǎn)相鄰接，且至少有一個(gè)m子立方體中的正確結(jié)點(diǎn)構(gòu)成連通圖。

從局部m維子立方體不連通的廣義n-維超立方體定義可以看出，不需要所有的m子立方體的正確結(jié)點(diǎn)構(gòu)成連通圖。也不需要m子立方體錯(cuò)誤結(jié)點(diǎn)數(shù)少于正確結(jié)點(diǎn)數(shù)，這樣錯(cuò)誤結(jié)點(diǎn)個(gè)數(shù)可突破結(jié)點(diǎn)個(gè)數(shù)可突破一半的限制。

定理：局部m維子立方體不連通的廣義n-維超立方體是連通圖。

證明：對(duì)于廣義n-維超立方體任意兩個(gè)結(jié)點(diǎn)S=s1s2…sn、T=t1t2…tn，以及一個(gè)正確結(jié)點(diǎn)連通的m子立方體W=w1w2…wn-m*。首先我們說明S和W中某個(gè)正確結(jié)點(diǎn)相連。由S=s1s2…sn，知S所在的m子立方體為s1s2…sn-m*，從前到后比較s1s2…sn-m和w1w2…wn-m對(duì)應(yīng)得位，設(shè)s1s2…sn-m+1中w1w2…wn-m對(duì)應(yīng)得第一個(gè)不同的位為，找S在w1w2……sn-m+1*中連通分支和w1w2……sn-m+1*中的一對(duì)正確的鄰接點(diǎn)T1、T2，知S到T2連通。再從T2起，重復(fù)上述過程，直到W中有正確結(jié)點(diǎn)和S相鄰。同理有W中也有正確結(jié)點(diǎn)和T相鄰。又W中的正確結(jié)點(diǎn)構(gòu)成連通圖，知S和T連通。命題得證。

上面的證明過程也就是局部m維子立方體不連通的廣義n-維超立方體容錯(cuò)路由的算法思想。下面我們根據(jù)這個(gè)想法給出算法。

算法：局部m維子立方體不連通的廣義n-維超立方體路由算法：

輸入：在局部m維子立方體不連通的廣義n-維超立方體輸入一對(duì)正確結(jié)點(diǎn)S、T。

輸出：輸出一條從S到T的路徑。

輸入S=s1s2…sn、T=t1t2…tn（si和t1為0到k之間確定的整數(shù)）

尋找一個(gè)正確結(jié)點(diǎn)連通的m子立方體W=w1w2…wn-m*；

路徑加入：P1=S；

（1）for（ i：=1；in-m；i++）

if（siwi）{1）搜索S在w1w2……sn-m*中連通分支和w1w2……sn-m*中的一對(duì)正確的鄰接點(diǎn)T1、T2；2）路徑加入：P1=在w1w2……sn-m*搜索到的S到T1的路徑及結(jié)點(diǎn)T2；}

（2）路徑加入：P2=T；

（3）for（ i：=1；in-m；i++）

if（tiwi）{1）搜索T在w1w2……tn-m*中連通分支和w1w2……tn-m*中的一對(duì)正確的鄰接點(diǎn)S1、S2；2）路徑加入：P2=在w1w2……tn-m*搜索到的S到S1的路徑及結(jié)點(diǎn)S2；}

（4）取出（1）、（3）中最后一個(gè)結(jié)點(diǎn)U、V，在W中尋找U到V，并添加到P1；

（5）把P2的路徑取反然后添加到P1；

算法在（2）中尋找一個(gè)正確結(jié)點(diǎn)連通的m子立方體需要時(shí)間0（k（n-m）km）。算法（1）需要時(shí)間0（2（n-m）km）。故整個(gè)算法時(shí)間復(fù)雜度為0（3kn）。

3 結(jié)語

我們在局部廣義k-維子立方體連通性基礎(chǔ)上進(jìn)一步提出了局部m維子立方體不連通的廣義n-維超立方體的概念。之后我們證明了此類廣義n-維超立方體是連通的，并提出了路由算法。通過分析得到的時(shí)間復(fù)雜度是0（3kn）。此時(shí)間復(fù)雜度要比廣度搜索時(shí)間復(fù)雜度大，但算法是基于局部信息且不需要所有的廣義n-維超立方體的m子立方體正確結(jié)點(diǎn)連通，同時(shí)還擴(kuò)大了容錯(cuò)性。

參考文獻(xiàn)

[1]劉紅美.廣義超立方體網(wǎng)絡(luò)容錯(cuò)路由算法[J].武漢理工大學(xué)學(xué)報(bào)：交通科學(xué)與工程版，2006，30（4）：682-685.

[2]王國軍，陳建二，陳松喬.具有大量錯(cuò)誤結(jié)點(diǎn)的超立方體網(wǎng)絡(luò)的高效路由算法的設(shè)計(jì)與討論[J].計(jì)算機(jī)學(xué)報(bào)，2001，24（9）：909-916.