完全多部图全终端可靠度的一种计算方法  

A recursive method to calculate the all⁃terminal reliability of complete multigraphs

作　　者：王朝阳 赵海兴[1,2,3] 张科 谢笋[2,3] WANG Zhao⁃yang;ZHAO Hai⁃xing;ZHANG Ke;XIE Sun(School of Mathematics and Statistics,Qinghai Normal University,Xining 810016,China;School of Computer,Qinghai Normal University,Xining 810016,China;Tibetan Information Processing and Machine Translation Key Laboratory of Qinghai Province,Xining 810008,China;School of Information Engineering,Huzhou University,Huzhou 313000,China)

机构地区：[1]青海师范大学数学与统计学院,青海西宁810016 [2]青海师范大学计算机学院,青海西宁810016 [3]藏文信息处理教育部重点实验室,青海西宁810008 [4]湖州师范学院信息工程学院,浙江湖州313000

出　　处：《电子设计工程》2020年第14期1-5,共5页Electronic Design Engineering

基　　金：国家自然科学基金支持项目(11661069,61663041,61763041);长江学者和创新研究团队项目(IRT_15R40);青海省自然基金项目资助(2017-ZJ-949Q);青海省藏文信息处理与机器翻译重点实验室资助(2013-Z-Y17)。

摘　　要：基于设计更可靠的网络结构目的,引入了网络的全终端可靠度的概念,即:一个网络在点可靠、边以相同概率随机并独立失效状态下,整个网络保持正常通讯的概率。用可靠度多项式计算网络全终端可靠度是网络结构稳定的有效测度,并且精确计算普通图的全终端可靠度是NP-hard的问题。本文研究完全多部图的可靠度,通过采用一种递推的计算方法,得到了计算其可靠度的递推公式,对该图类中规模较小的情形加以验证,并给出了相应的图的可靠度的表达式。Based on the purpose of designing more reliable network structure,the concept of all terminal reliability of a network is introduced,namely,The probability that a network maintains normal communication under the condition that the vertices are reliable and the edges are random with the same probability and fail independently.It is an effective measure of network structure stability to calculate the all terminal reliability of a network with the reliability polynomial,and it is a NP⁃hard problem to calculate the all terminal reliability of a general graph accurately.In this paper,the reliability of complete multipart graphs is proposed,and a recursive formula for calculating its reliability is obtained by using a recursive calculation method.For the smaller scale cases in the graph class,the corresponding graph reliability expression is then given.

关 键 词：完全多部图 全终端可靠度 递推公式 网络结构设计 

分 类 号：TN711.6[电子电信—电路与系统]