排列图的限制边连通度
2021-04-02邹婷婷曾雪倩李向军
湖北民族大学学报(自然科学版) 2021年1期
邹婷婷,曾雪倩,李向军
(长江大学 信息与数学学院,湖北 荆州 434023)
在大规模多元信息处理系统中,元件故障不可避免,当故障发生时网络对某些条件性质的保持能力就是它的容错性能.在设计大规模网络时,高性能、低成本是最终目标.在选择互连网络的拓扑结构时,处理器之间的有效通信是衡量系统性能的一个重要标准,当处理器数目逐渐增多时,其发生故障的可能性也随之增加,不同处理器之间信息传递过程中的容错性便成为一个非常关键的问题,为此有必要考虑网络的容错性和可靠性.点连通度(记作κ(G))是使得G-T不连通的最小顶点子集T的基数;边连通度(记作λ(G))的定义类似,它是使得G-F不连通的最小边子集F的基数.但连通度假设任意顶点和任意边可以同时发生故障,在实际应用中并不能很好地反映网络的弹性,Harary针对这一弱点,引入了条件连通度的概念,对剩余的网络提出了一些附加要求[1].此后,Latifi等[2]在一定意义上推广了这一概念,通过限制每个顶点至少有h个无故障邻点,提出了h-限制连通度.在实际应用中,这些广义度量可以更准确地估计互连网络的容错性.
用无向图G=(V;E)表示互连网络的拓扑结构,图G的顶点V(G)代表系统中的元件,图G的边E(G)代表元件之间的物理连线[3].对于u∈V,u的度是与u关联的边数,记作d(u),δ(G)表示图G的最小度.假设G为连通图,T是V(G)的子集,若G-T不连通且最小度至少为h,即δ(G-T)≥h,称T是图G的h-点割,h-限制点连通度(记作κh(G))是最小h-点割的基数.对于……
登录APP查看全文
