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

馮 凱

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

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

馮 凱*

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

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

并行計算機系統；互連網絡；k元n方體；完美匹配；條件故障

0 引言

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

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

1 主要結果

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

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

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

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

2)若(u,v)∈E(G)，Fuzv包含邊(u,v)；

3)對任意的w∈NG(u)NG(v)，Fuzv或者包含w或者包含(u,w)；

4)對任意的w∈NG(v)NG(u)，Fuzv或者包含w或者包含(v,w)。

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

證畢。

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

證畢。

引理3 設k≥3為整數，n≥1為整數，則有：

證畢。

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

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

證畢。

證畢。

證畢。

證畢。

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

2 結語

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立方網絡的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會員，主要研究方向：互連網絡的容錯性、圖論及其應用。

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.