張淑蓉，王世英，董操

山西大學(xué)數(shù)學(xué)科學(xué)學(xué)院，太原 030006

邊故障k元n立方體的超級(jí)哈密頓交織性

張淑蓉，王世英，董操

山西大學(xué)數(shù)學(xué)科學(xué)學(xué)院，太原 030006

k元n立方體（記為）是優(yōu)于超立方體的可進(jìn)行高效信息傳輸?shù)幕ミB網(wǎng)絡(luò)之一。是一個(gè)二部圖當(dāng)且僅當(dāng)k為偶數(shù)。令G[V0，V1]是一個(gè)二部圖，若（1）任意一對(duì)分別在不同部的頂點(diǎn)之間存在一條哈密頓路，且（2）對(duì)于任意一點(diǎn)v∈Vi，其中i∈{0，1}，V1-i中任意一對(duì)頂點(diǎn)可以被G[V0，V1]-v中的一條哈密頓路相連，則圖G[V0，V1]被稱為是超級(jí)哈密頓交織的。因?yàn)榫W(wǎng)絡(luò)中的元件發(fā)生故障是不可避免的，所以研究網(wǎng)絡(luò)的容錯(cuò)性就尤為重要。針對(duì)含有邊故障的，其中k≥4是偶數(shù)且n≥2，證明了當(dāng)其故障邊數(shù)至多為2n-3時(shí)，該故障是超級(jí)哈密頓交織圖，且故障邊數(shù)目的上界2n-3是最優(yōu)的。

互連網(wǎng)絡(luò)；超級(jí)哈密頓交織性；k元n立方體

1 引言和基本概念

隨著計(jì)算機(jī)應(yīng)用的不斷深入，迫切需要速度更快，性能更高的計(jì)算機(jī)系統(tǒng)，進(jìn)而開辟了并行和分布式系統(tǒng)的研究領(lǐng)域。系統(tǒng)中元件之間的連接模式稱為該系統(tǒng)的互連網(wǎng)絡(luò)，或者簡(jiǎn)稱為網(wǎng)絡(luò)。毫無(wú)疑問，并行和分布式系統(tǒng)功能的實(shí)現(xiàn)在很大程度上依賴于該系統(tǒng)的互連網(wǎng)絡(luò)結(jié)構(gòu)。k元n立方體是最重要的互連網(wǎng)絡(luò)之一[1-4]。它具有許多優(yōu)良性質(zhì)，如易運(yùn)行，低延遲和高帶寬。正是這些優(yōu)良的性質(zhì)，k元n立方體受到了廣泛關(guān)注，并且大量的并行和分布式系統(tǒng)都是基于k元n立方體來形成其連接模式，如iWarp[5]，J-machine[6]和IBM Blue Gene/L[7]。

互連網(wǎng)絡(luò)可以看成一個(gè)圖G=(V(G)，E(G))，其中V(G)和E(G)分別表示G的頂點(diǎn)集和邊集。圖的頂點(diǎn)表示系統(tǒng)中的元件，圖的邊表示元件之間的物理連線。在G中，頂點(diǎn)u的所有鄰點(diǎn)組成的集合稱為u的鄰域，記作NG(u)。若G的頂點(diǎn)可以被劃分為兩個(gè)集合V0和V1，使得每條邊的端點(diǎn)一個(gè)在V0中，另一個(gè)在V1中，則稱圖是二部圖，這樣的一個(gè)分劃(V0，V1)被稱為是圖G的一個(gè)二分劃，V0和V1被稱為是圖的兩個(gè)部。若二部圖中任意一對(duì)分別在不同部的頂點(diǎn)之間存在一條哈密頓路，則稱該圖是哈密頓交織圖[8]。

設(shè)G是具有二分劃(V0，V1)的哈密頓交織圖。若Vi中任意一對(duì)頂點(diǎn)可以被G中的一條長(zhǎng)度為|V(G)|-2的路相連，則圖G被稱為是強(qiáng)哈密頓交織圖[9]。對(duì)于任意一點(diǎn)v∈Vi，其中i∈{0，1}，V1-i中任意一對(duì)頂點(diǎn)可以被G-v中的一條哈密頓路相連，則圖G被稱為是超級(jí)哈密頓交織圖[10]。

由以上定義可以看出，若G是超級(jí)哈密頓交織圖，則G一定是強(qiáng)哈密頓交織圖。

在實(shí)際應(yīng)用中，網(wǎng)絡(luò)中的元件或連線也可能發(fā)生故障從而影響到網(wǎng)絡(luò)的正常運(yùn)行，所以研究故障網(wǎng)絡(luò)的（強(qiáng)或超級(jí)）哈密頓交織性具有重要的意義[11-13]。

Huang在2009年[9]已經(jīng)證明了當(dāng)k為偶數(shù)時(shí)，不含故障邊的k元n立方體是強(qiáng)哈密頓交織圖。而本文是在文獻(xiàn)[9]的基礎(chǔ)上所做的進(jìn)一步研究，并且證明了：至多含有2n-3條故障邊的k元n立方體（k為偶數(shù)）是超級(jí)哈密頓交織圖，可見該結(jié)果推廣并涵蓋了文獻(xiàn)[9]的主要結(jié)論。

定義1（m-邊容錯(cuò)（超級(jí)）哈密頓交織圖）設(shè)G是二部圖，F(xiàn)(|F|≤m)是G的故障邊集合。若G為（超級(jí)）哈密頓交織圖且G-F仍為（超級(jí)）哈密頓交織圖，則稱G是m-邊容錯(cuò)（超級(jí)）哈密頓交織圖。

定義2（k元n立方體）k元n立方體，記為(k≥1， n≥1)，是一個(gè)具有kn個(gè)頂點(diǎn)的圖，每個(gè)頂點(diǎn)可以標(biāo)記為u=un-1un-2…u0，其中ui∈{0，1，…，k-1}，0≤i≤n-1。兩個(gè)頂點(diǎn)u=un-1un-2…u0和v=vn-1vn-2…v0相鄰當(dāng)且僅當(dāng)存在一個(gè)整數(shù)j∈{0，1，…，n-1}，使得uj=vj±1 (mod k)且對(duì)每個(gè)i∈{0，1，…，n-1}{j}都有ui=vi。這樣的邊uv被稱為是一條j維邊。為書寫方便，在本文中遇到類似情況時(shí)省略“(mod k)”。

取定一個(gè)正整數(shù)j∈{0，1，…，n-1}。刪除所有的j維邊便可以沿第j維將(k≥2)劃分為k個(gè)不相交的子立方，依次記為：0]，[1]，…，[k-1]（在不引起歧義的情況下，簡(jiǎn)記為Q[0]，Q[1]，…，Q[k-1]，如圖1）。顯然對(duì)每一個(gè)0≤i≤k-1，Q[i]均與同構(gòu)。在該中任取一點(diǎn)u=uu…uuu…u，不失一般n-1n-2j+1jj-10性，假設(shè)u∈V(Q[i])，其中0≤i≤k-1。記Q[i′]中的頂點(diǎn)v=un-1un-2…uj+1vjuj-1…u0為ni′(u)，其中vj≠uj?？梢钥闯鰊i′(u)和u相鄰當(dāng)且僅當(dāng)i′=i±1。

圖1 將劃分為Q[0]，Q[1]，…，Q[k-1]

圖3 的子圖Row[0:3]

圖2 的子圖Row[0:2]

2 主要結(jié)論

首先給出對(duì)主要結(jié)論證明有用的一些引理。

引理2.1[14]在Row[0:p]中任取3個(gè)不同的頂點(diǎn)s，t和x，其中1≤p≤k-1。若δ(x，s)=1且δ(s，t)=0，則Row[0:p]-x中存在一條哈密頓st-路。

引理2.2[15]設(shè)n≥2是整數(shù)，k≥4是偶數(shù)。在中任取兩個(gè)相鄰頂點(diǎn)s*和t*，則-{u*，v*}是哈密頓交織圖。

引理2.3[16]若n≥2是整數(shù)，k≥4是偶數(shù)，則是(2n-2)-邊容錯(cuò)哈密頓交織圖。

圖4 情形1.1.1中哈密頓路的構(gòu)造方法演示

圖5 情形1.2.1中哈密頓路的構(gòu)造方法演示

圖6 情形2中哈密頓路的構(gòu)造方法演示

3 結(jié)束語(yǔ)

本文主要對(duì)含有故障邊的k元n立方體（k≥4為偶數(shù)）的超級(jí)哈密頓交織性進(jìn)行了研究。證明了若該k元n立方體中的故障邊集F滿足|F|≤2n-3，則-F是超級(jí)哈密頓交織圖。這一結(jié)果表明，就超級(jí)哈密頓交織性來說，k元n立方體（k≥4為偶數(shù)）具有良好的故障容錯(cuò)能力，這一結(jié)果對(duì)于建立k元n立方體（k≥4為偶數(shù)）環(huán)境下的T比特路由器是不無(wú)裨益的。

[1]Bose B，Broeg B，Younggeun K，et al.Lee distance and topological properties of k-ary n-cubes[J].IEEE Transactions on Computers，1995，44（8）：1021-1030.

[2]Dally W J.Performance analysis of k-ary n-cube interconnection networks[J].IEEE Transactions on Computers，1990，39（6）：775-785.

[3]Ghozati S A，Wasserman H C.The k-ary n-cube network：modeling，topological properties and routing strategies[J]. Computers and Electrical Engineering，1999，25（3）：155-168.

[4]Hsieh S Y，Chang Y H.Extraconnectivity of k-ary n-cube networks[J].Theoretical Computer Science，2012，443（20）：63-69.

[5]Peterson C，Sutton J，Wiley P.iWarp：a 100-MOPS，LIW microprocessor for multicomputers[J].IEEE Micro，1991，11（3）：26-29，81-87.

[6]Noakes M，Dally W J.System design of the J-machine[C]// 6th MIT Conference on Advanced Research in VLSI，1990：179-194.

[7]Adiga N R，Blumrich M A，Chen D，et al.Blue Gene/L torus interconnection network[J].IBM Journal of Research and Development，2005，49（2）：265-276.

[8]Wong S A.Hamiltonian cycles and paths in buttery graphs[J]. Networks，1995，26（3）：145-150.

[9]Huang C H.Strongly Hamiltonian laceability of the even k-ary n-cube[J].Computers and Electrical Engineering，2009，35（5）：659-663.

[10]Lewinter M，Widulski W.Hyper-Hamilton laceable and caterpillar-spannable product graphs[J].Computers and Mathematics with Applications，1997，34（11）：99-104.

[11]Li T K，Tan J J M，Hsu L H.Hyper hamiltonian laceability on edge fault star graph[J].Information Sciences，2004，165（1/2）：59-71.

[12]Tsai C H，Tan J J M，Liang T，et al.Fault-tolerant Hamiltonian laceability of hypercubes[J].Information Processing Letters，2002，83（6）：301-306.

[13]Araki T，Kikuchi Y.Hamiltonian laceability of bubblesort graphs with edge faults[J].Information Sciences，2007，177（13）：2679-2691.

[14]Kim H C，Park J H.Fault hamiltonicity of two-dimensional torus networks[C]//Workshop on Algorithms and Computation，Tokyo，Japan，2000：110-117.

[15]Wang Shiying，Zhang Shurong.Embedding hamiltonian paths in k-ary n-cubes with conditional edge faults[J]. Theoretical Computer Science，2011，412（46）：6570-6584.

[16]Stewart I A，Xiang Yonghong.Embedding long paths in k-ary n-cubes with faulty nodes and links[J].IEEE Transactions on Parallel and Distributed Systems，2008，19（8）：1071-1085.

ZHANG Shurong,WANG Shiying,DONG Cao

School of Mathematical Sciences,Shanxi University,Taiyuan 030006,China

Thek-aryn-cube,denoted by,as one of the most efficient interconnection networks for information

transportation,has been shown as an alternative to the hypercube.Ais bipartite if and only ifkis even.A bipartite graphG[V0，V1]is called hyper hamiltonian laceable if（1）it has a hamiltonian path between any pair of vertices in different parts,and（2）for any vertexv∈Vi,there is a hamiltonian path ofG[V0，V1]-vbetween any two vertices inV1-i,where i∈{0，1}.Since edge faults may occur after a network is activated,it is important to solve problems in faulty networks. This paper addresses the faultywith evenk≥4andn≥2,and proves that thewith at most2n-3faulty edges is hyper hamiltonian laceable.This result is optimal to the number of edge faults tolerated.

interconnection networks;hyper hamiltonian laceability;k-aryn-cubes

A

O157.5

10.3778/j.issn.1002-8331.1212-0216

ZHANG Shurong,WANG Shiying,DONG Cao.Hyper hamiltonian laceability of k-ary n-cubes with edge faults. Computer Engineering and Applications,2014,50（21）：39-43.

國(guó)家自然科學(xué)基金（No.61070229）；教育部高等學(xué)校博士點(diǎn)專項(xiàng)基金（No.20111401110005）。

張淑蓉（1984—），女，博士研究生，研究領(lǐng)域?yàn)閳D論及其應(yīng)用；王世英（1961—），男，博士，教授，研究領(lǐng)域?yàn)閳D論及其應(yīng)用；董操（1983—），男，碩士研究生，研究領(lǐng)域?yàn)閳D論及其應(yīng)用。E-mail：zhangsr@sxu.edu.cn

2012-12-18

2013-07-09

1002-8331（2014）21-0039-05

CNKI出版日期：2013-08-05，http://www.cnki.net/kcms/detail/11.2127.TP.20130805.0943.004.html