网络优化中一个组合问题的探讨

文4]提出了网络优化中若干有待解决的组合问题，本文围绕其中之一“减小直径问题”进行了探讨．设P（n，t）表示长为n的路径增加t条边后所得图直径的最小值，C（n，t）表示长为n的圈增加t条边后所得回直径的最小值．本文取得如下进展：1）给出P（n，2），P（n，3）及C（n，2）的精确值，并得出P（n，4）的一更精细的上界及一种更好的加边方式．上述结果均满足小极大度原则．2）在有极大度限制的条件下，分别对t为偶数和奇数给出了P（n，t）的上界．

Research on a Combination Problem in the Optimization of Network

Reference 4] proposed some combination problems in the optimization of network. One of the problems, Decreasing Diameter, is discussed here. By using the properties of an cycle and the symmetry, the exact value of P(n, 2), P(n, 3) and C(n, 2) are obtained. We also give a sharp upper bound for P(n, 4) and a better approach of adding-edge. All results obey the rule of small Max-degree. The upper bound of P(n, t) on the constraint of Max-degree are dealt with in the term of the even or odd of t, where P(n, t) denotes the least possible diameter for the graph obtained from an n-edge path by adding t edges, C(n, t) denotes the corresponding value for the cycle case.