论文标题
通过计算微不足道的切割来找到最可靠的图形
Finding uniformly most reliable graphs by counting trivial cuts
论文作者
论文摘要
有很多文献集中在网络可靠性评估上。在过去的几十年中，还解决了可靠性优化。弗兰克·博施（Frank Boesch）在1986年介绍了统一最可靠的图（UMRG）的概念。后来，Boesch \ emph {et al。}提出了第一个UMRGS，并指出了两分的完整图$ k_ {3,3} $的某些特殊细分，以及双 - 完整的图形$ k_ {4,4,4} $是UMRGS。王证明了第一个猜想是正确的。 Wendy Myrvold通过计算测试确认$ K_ {4,4} $也是UMRG。但是，到目前为止，文献中还没有数学证明。微不足道的切割是一个边缘集，其中包括固定节点的所有入射边缘。在本文中，我们描述了一种基于微不足道削减数量的界限来确定UMRGS的方法。作为概念验证，证明$ k_ {3,3} $和$ k_ {4,4} $都是UMRGS。
There is a vast literature focused on network reliability evaluation. In the last decades, reliability optimization has been also addressed. Frank Boesch in 1986 introduced the concept of uniformly most reliable graph (UMRG). Later, Boesch \emph{et al.} presented the first UMRGs and conjectured that some special subdivisions of the bipartite complete graph $K_{3,3}$, as well as the bipartite complete graph $K_{4,4}$, are UMRGs. Wang proved that the first conjecture is true. Wendy Myrvold confirmed that $K_{4,4}$ is also UMRG, by means of computational tests. However, thus far, there is no mathematical proof in the literature. A trivial cut is an edge-set that includes all the incident edges of a fixed node. In this article we describe a methodology to determine UMRGs based on bounding the number of trivial cuts. As a proof-of-concept it is proved that both $K_{3,3}$ and $K_{4,4}$ are UMRGs.
