k元n方體的條件強(qiáng)匹配排除

馮 凱

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

k元n方體的條件強(qiáng)匹配排除

馮 凱*

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

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

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

0 引言

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

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

1 主要結(jié)果

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

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

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

1)Fuzv包含(NG(u)∩NG(v)) {z}中的每個(gè)點(diǎn)；

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

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

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

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

證畢。

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

證畢。

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

證畢。

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

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

證畢。

證畢。

證畢。

證畢。

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

2 結(jié)語(yǔ)

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)絡(luò)的k圈排除問(wèn)題的遞歸算法[J].計(jì)算機(jī)應(yīng)用,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。

國(guó)家自然科學(xué)基金資助項(xiàng)目(61502286)。

馮凱 (1987—)，男，山西臨汾人，講師，博士，CCF會(huì)員，主要研究方向：互連網(wǎng)絡(luò)的容錯(cuò)性、圖論及其應(yī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.