超立方体网络的3路结构连通度及子结构连通度

详细信息    查看全文 | 推荐本文 |

英文篇名：Three-length-path structure connectivity and substructure connectivity of hypercube networks 作者：杨玉星 ; 李晓慧 英文作者：YANG Yuxing;LI Xiaohui;College of Mathematics and Information Science, Henan Normal University;Henan Engineering Laboratory for Big Data Statistical Analysis and Optimal Control ( Henan Normal University); 关键词：多处理机系统 ; 超立方体网络 ; 容错 ; 可靠性 ; 结构连通度 英文关键词：multi-processor system;;hypercube network;;fault tolerance;;reliability;;structure connectivity 中文刊名：JSJY 英文刊名：Journal of Computer Applications 机构：河南师范大学数学与信息科学学院;大数据统计分析与优化控制河南省工程实验室(河南师范大学); 出版日期：2018-10-01 17:16 出版单位：计算机应用 年：2019 期：v.39;No.342 基金：国家自然科学基金-河南联合基金资助项目(U1304601)~~ 语种：中文; 页：JSJY201902035 页数：4 CN：02 ISSN：51-1307/TP 分类号：205-208

摘要

针对以超立方体网络为蓝本的多处理机系统的可靠性和容错能力的精准度量问题,结合多处理机系统遭受计算机病毒攻击时常常发生结构性故障的特点,研究了n维超立方体网络的结构连通性和子结构连通性评价问题。首先,使用构造n维超立方体网络的3路结构割的方法得到其3路结构连通度的一个上界;然后,使用构造n维超立方体网络的3路子结构集的等价变换或约简变换的方法,得到其3路结构子连通度的一个下界;最后,利用任意网络的3路结构连通度不小于3路子结构连通度的性质,证实了超立方体网络的3路结构连通度和子结构连通度均为该超立方体网络维数的一半。这一结果表明,在3路结构故障模型下,破坏敌方以超立方体网络为底层拓扑的多处理系统至少需要攻击该系统中维数一半的3路结构或子结构。
        In order to evaluate the reliability and fault-tolerant ability of multi-processor system which takes hypercubes as underlying networks,combining the fact that structural faults often occur when the system is invaded by computer viruses,three-length-path structure connectivity and substructure connectivity of the n-cube network were investigated.Firstly,by using the three-length-path structure-cut of the n-cube network,an upper bound of three-length-path structure connectivity of the network was obtained.Secondly,by using an equivalent transformation or a reductive transformation of the three-lengthpath substructure-set of the n-cube network,a lower bound of three-length-path substructure connectivity of the network was obtained.Finally,combining with the property that three-length-path structure connectivity of a network is not less than its three-length-path substructure connectivity,it was proved that both three-length-path structure connectivity and substructure connectivity of a n-cube network were half of n.The results show that to destroy the enemy's multi-processor system which take the n-cubes as underlying networks under three-length-path structure fault model,at least half of n three-length-path structures or substructures of the system should be attacked.

引文

[1]XU J M,ZHU Q,HOU X M,ZHU T.On restricted connectivity and extra connectivity of hypercubes and folded hypercubes[J].Journal of Shanghai Jiaotong University(Science),2005,E-10(2):203-207.
    [2]YANG W,MENG J.Extraconnectivity of hypercubes[J].Applied Mathematics Letters,2009,22(6):887-891.
    [3]MORRISION N,NOEL J A.Extremal bounds for bootstrap percolation in the hypercube[J].Journal of Combinatorial Theorey,Series A,2018,156:61-84.
    [4]WANG F,ZHANG H.Hamiltonian laceability in hypercubes with faulty edges[J].Discrete Applied Mathematics,2018,236:438-445.
    [5]邱亚娜,杨玉星.增广泡型网络的边连通性和限制边连通性[J].计算机应用,2016,36(11):3006-3009.(QIU Y N,YANG Y X.Link connectivity and restricted link connectivity of augmented bubble-sort networks[J].Journal of Computer Applications,2016,36(11):3006-3009.)
    [6]李际超,吴俊,谭跃进,等.基于有向自然连通度的作战网络抗毁性研究[J].复杂系统与复杂性科学,2015,12(4):25-31.(LI J C,WU J,TAN Y J,et al.Robustness of combat networks based on directed natural connectivity[J].Complex Systems and Complexity Science,2015,12(4):25-31.)
    [7]YANG Y,WANG S.Conditional connectivity of star graph networks under embedding restriction[J].Information Sciences,2012,199:187-192.
    [8]YANG Y,WANG S,LI J.Conditional connectivity of recursive interconnection networks respect to embedding restriction[J].Information Sciences,2014,279:273-279.
    [9]LI X-J,DONG Q-Q,YAN Z,et al.Embedded connectivity of recursive networks[J].Theoretical Computer Science,2016,653:79-86.
    [10]ZHAO S,YANG W,ZHANG S.Component connectivity of hypercubes[J].Theoretical Computer Science,2016,640:115-118.
    [11]LIN C-K,ZHANG L,FAN J,et al.Structure connectivity and substructure connectivity of hypercubes[J].Theoretical Computer Science,2016,634:97-107.
    [12]LYU Y,FAN J,HSU D F,et al.Structure connectivity and substructure connectivity of k-ary n-cube networks[J].Information Sciences,2018,433/434:115-124.
    [13]MANE S A.Structure connectivity of hypercubes[J].AKCE International Journal of Graphs and Combinatorics,2018,15(1):49-52.
    [14]SABIR E,MENG J.Structure fault tolerance of hypercubes and folded hypercubes[J].Theoretical Computer Science,2018,711:44-55.
    [15]BONDY J A,MURTY U S R.Graph Theory[M].New York:Springer,2008:633-641.