馮 凱

(山西大學 計算機與信息技術(shù)學院，太原 030006)(*通信作者電子郵箱fengkai@sxu.edu.cn)

k元n方體的條件強匹配排除

馮 凱*

(山西大學 計算機與信息技術(shù)學院，太原 030006)(*通信作者電子郵箱fengkai@sxu.edu.cn)

為了度量發(fā)生故障時k元n方體對其可匹配性的保持能力，通過剖析條件故障下使得k元n方體中不存在完美匹配或幾乎完美匹配所需故障集的構(gòu)造，研究了條件故障下使得k元n方體不可匹配所需的最小故障數(shù)。當k≥4為偶數(shù)且n≥2時，得出了k元n方體這一容錯性參數(shù)的精確值并對其所有相應的最小故障集進行了刻畫；當k≥3為奇數(shù)且n≥2時，給出了該k元n方體容錯性參數(shù)的一個可達下界和一個可達上界。結(jié)果表明，選取k為奇數(shù)的k元n方體作為底層互連網(wǎng)絡拓撲設計的并行計算機系統(tǒng)在條件故障下對其可匹配性有良好的保持能力；進一步地，該系統(tǒng)在故障數(shù)不超過2n時仍是可匹配的，要使該系統(tǒng)不可匹配至多需要4n-3個故障元。

并行計算機系統(tǒng)；互連網(wǎng)絡；k元n方體；完美匹配；條件故障

0 引言

設M是圖G中的邊子集且M中任意兩條邊無公共端點，則稱M為G的一個匹配。若|G|為偶數(shù)，G中匹配M滿足|M|=|G|/2，則稱M為G的一個完美匹配。若|G|為奇數(shù)，G中匹配M滿足|M|=(|G|-1)/2，則稱M為G的一個幾乎完美匹配。若圖G中存在完美匹配或幾乎完美匹配，則稱G是可匹配的；否則稱G是不可匹配的。對于圖G中任意一點v，G中所有與v相鄰的點構(gòu)成的集合稱為v的鄰域，記為NG(v)；G中與點v相關(guān)聯(lián)的邊的數(shù)目稱為v的度，記為dG(v)。若V(G)可以劃分成兩個非空子集X和Y，使得每條邊都有一個端點在X中，另一個端點在Y中，則稱G為一個二部圖，(X,Y)為G的一個二分類。對于文中其他未加定義而被使用的圖論術(shù)語和記號參見文獻[1]。

并行計算機系統(tǒng)通常以某個無向簡單圖G=(V(G),E(G))作為其基本的互連網(wǎng)絡，其中V(G)中每個頂點對應一個處理器，E(G)中每條邊對應一對處理器之間的一條直接通信線路。對于某些特定的系統(tǒng)，要求其互連網(wǎng)絡中每個處理器在任意時間都需要被指定一個與其配對的處理器，這些處理器對之間通過相互通信協(xié)同工作，整個系統(tǒng)才能正常運行。為了優(yōu)化資源配置、降低通信延遲，人們希望這樣的處理器對之間是通過直接的物理連線連接的。在此背景下，Brigham等[2]提出了互連網(wǎng)絡的匹配排除問題，即一個互連網(wǎng)絡中至少需要多少條邊發(fā)生故障才可以使該網(wǎng)絡是不可匹配的。在實際構(gòu)建的系統(tǒng)中元器件和通信信道發(fā)生故障是隨機的、不可預知的，互連網(wǎng)絡中某些點和邊可能同時發(fā)生故障?；谶@一考慮，Park等[3]對匹配排除問題進行了推廣，提出了互連網(wǎng)絡的強匹配排除問題。設G=(V(G),E(G))是一個無向簡單圖，F(xiàn)?V(G)∪E(G)為G中的故障集。若GF是不可匹配的，則稱F為G的一個強匹配排除集。G的含元素最少的強匹配排除集中元素的個數(shù)稱為G的強匹配排除數(shù)，記為smp(G)。若G中強匹配排除集F滿足|F|=smp(G)，則稱F為G的一個最小強匹配排除集。近來，互連網(wǎng)絡的強匹配排除問題得到了大量的關(guān)注[4-5]。對于帶有故障診斷算法的系統(tǒng)，系統(tǒng)發(fā)生故障導致出現(xiàn)孤立點的可能性很小。Park等[6]于2013年對條件故障下(即假定系統(tǒng)不會由于發(fā)生故障而產(chǎn)生孤立點)互連網(wǎng)絡的強匹配排除問題進行了研究。稱圖G中相應的強匹配排除集為G的條件強匹配排除集，相應的強匹配排除數(shù)記為smp1(G)。

1 主要結(jié)果

由定義可知，圖中一個條件強匹配排除集是一個特殊的強匹配排除集。下面的性質(zhì)顯然成立。

性質(zhì)1 若圖G中有強匹配排除集和條件強匹配排除集，則smp(G)≤smp1(G)。

性質(zhì)2[6]對于圖G中的一條路(u,z,v)，構(gòu)造故障集Fuzv如下：

1)Fuzv包含(NG(u)∩NG(v)) {z}中的每個點；

2)若(u,v)∈E(G)，F(xiàn)uzv包含邊(u,v)；

3)對任意的w∈NG(u)NG(v)，F(xiàn)uzv或者包含w或者包含(u,w)；

4)對任意的w∈NG(v)NG(u)，F(xiàn)uzv或者包含w或者包含(v,w)。

若GFuzv不含孤立點且|GFuzv|為偶數(shù)，則Fuzv為G的一個條件強匹配排除集。

證畢。

引理2[6]設G為m正則連通二部圖，其中m≥3，則smp1(G)=2且G中任一個最小條件強匹配排除集均由同一部集中的兩個點構(gòu)成。

證畢。

引理3 設k≥3為整數(shù)，n≥1為整數(shù)，則有：

證畢。

1) 存在d∈{1,2,…,n}使得ud=vd。

2) 對任意d∈{1,2,…,n}有ud≠vd。

證畢。

證畢。

證畢。

證畢。

由定理4，顯然有下面的結(jié)論成立。

2 結(jié)語

References)

[1] BONDY J A, MURTY U S R. Graph Theory [M]. New York: Springer, 2008:1-450.

[2] BRIGHAM R C, HARARY F, VIOLIN E C, et al. Perfect-matching preclusion [J]. Congressus Numerantium, 2005, 174: 185-192.

[3] PARK J H, IHM I. Strong matching preclusion [J]. Theoretical Computer Science, 2011, 412(45): 6409-6419.

[4] FENG K, WANG S. Strong matching preclusion for two-dimensional torus networks [J]. International Journal of Computer Mathematics, 2015, 92(3): 473-485.

[5] CHENG E, KELM J, RENZI J. Strong matching preclusion of (n,k)-star graphs [J]. Theoretical Computer Science, 2016, 615: 91-101.

[6] PARK J H, IHM I. Strong matching preclusion under the conditional fault model [J]. Discrete Applied Mathematics, 2013, 161(7/8): 1093-1105.

[7] WANG S, WANG R, LIN S, et al. Matching preclusion fork-aryn-cubes [J]. Discrete Applied Mathematics, 2010, 158(18): 2066-2070.

[8] WANG S, FENG K, ZHANG G. Strong matching preclusion fork-aryn-cubes [J]. Discrete Applied Mathematics, 2013, 161(18): 3054-3062.

[9] 楊玉星,王世英.k元n立方網(wǎng)絡的k圈排除問題的遞歸算法[J].計算機應用,2013,33(9):2401-2403.(YANG Y X, WANG S Y. Recursive algorithm fork-cycle preclusion problem ink-aryn-cubes [J]. Journal of Computer Applications, 2013, 33(9): 2401-2403.)[10] YANG Y, LI J, WANG S. Embedding various cycles with prescribed paths intok-aryn-cubes [J]. Discrete Applied Mathematics, 2017, 220: 161-169.

[11] PETERSON C, SUTTON J, WILEY P. iWarp: a 100-MOPS, LIW microprocessor for multicomputers [J]. IEEE Micro, 1991, 11(3): 26-29.

[12] ANDERSON E, BROOKS J, GRASSL C, et al. Performance of the CRAY T3E multiprocessor [C]// Proceedings of the 1997 ACM/IEEE Conference on Supercomputing. New York: ACM, 1997: 1-17.

[13] 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/3): 265-276.

Conditionalstrongmatchingpreclusionfork-aryn-cubes

FENG Kai*

(SchoolofComputer&InformationTechnology,ShanxiUniversity,TaiyuanShanxi030006,China)

To measure the ability ofk-aryn-cube to remain the property of having a perfect matching or an almost perfect matching in the presence of failures, by analysis of constructions of the fault sets that make thek-aryn-cube having neither a perfect matching nor an almost perfect matching under the conditional fault model, the minimum number of failures that make thek-aryn-cube unmatchable under the conditional fault model was studied. Whenk≥4 is even andn≥ 2, the exact value of the fault-tolerant parameter fork-aryn-cube was obtained and all the corresponding minimum fault sets were characterized. Whenk≥3 is an odd number and n≥2, a sharp lower bound and a sharp upper bound on the fault tolerance parameter fork-aryn-cube were given. The results indicate that the parallel computer system, which takes thek-aryn-cube with oddkas underlying interconnection topology, has good ability to remain the property of having a perfect matching or an almost perfect matching under the conditional fault model. Moreover, this system is still matchable if the number of failures does not exceed 2nand at most 4n-3 failures could make this system unmatchable.

parallel computer system; interconnection network;k-aryn-cube; perfect matching; conditional failure

2017- 03- 10;

2017- 04- 27。

國家自然科學基金資助項目(61502286)。

馮凱 (1987—)，男，山西臨汾人，講師，博士，CCF會員，主要研究方向：互連網(wǎng)絡的容錯性、圖論及其應用。

1001- 9081(2017)09- 2454- 03

10.11772/j.issn.1001- 9081.2017.09.2454

TP393.02

A

This work is partially supported by the National Natural Science Foundation of China (61502286).

FENGKai, born in 1987, Ph. D., lecturer. His research interests include fault-tolerance of interconnection networks, graph theory and its applications.