关于G(n,n+3)网的树-优图公式(英文)

The Formula on the t-Optimal Graphs For G(n,n+3)

在网络可靠性研究中经常考虑的网络是有可靠结点，而且边具有独立、相等故障概率的无向图。作为网络可靠性分析的另一方面课题，Ｂｏｅｓｃｈ ＦＴ 等人首先提出了网络合成问题，其中一类网络合成问题是在给定结点ｎ ，边ｅ 以及边故障概率为Ｐ 的情况下，构造一个具有最大可靠性的网络。如果这样的网络存在，称其为一致最优网（ ＵＯＲ） 。在此过程中，ｔ － 优图的概念是十分重要的。利用ｔ － 优图，Ｂｏｅｓｃｈ 等人验证了对于ｅ＝ ｎ ，ｎ ＋ １ ，ｎ ＋ ２ ， 一致最优网的存在。在此考虑了ｅ＝ ｎ ＋ ３ 情况下ｔ－ 优图的存在及结构并且给出了ｔ－ 优图公式。

A well-known model for network reliability studies consists of an undirected graph with perfectly reliable nodes and equal and independent edge failure probabilities. As a subject of reliability analysis of networks, synthesis of reliable networks was first put forward by Boesch F T et al. A synthesis problem is to find a graph that maximizes the probability when the number of nodes n , the number of edges e , and edge failure rate p are given. When such a graph exists, it will be called a uniformly optimally reliable (UOR) graph. In the procedure, the t -optimal graph is a very important concept. Boesch et al. verified the existence of uniformly optimally reliable networks for e=n, n +1, n +2 by using the approach of t -optimal graph. In this paper, the existence and construction of the t -optimal graph are considered and the formula t -optimal graph is given for e=n +3.