有向环网D(n;s_1,s_2,s_3)的直径

The Diameters of Directed Loop Networks D(n;s_1,s_2,s_3)

环网的直径是网中任意两点间距离的极大值。对于给定的n个顶点,设计出具有最短直径的优化环网,必须首先解决计算环网直径的问题。本文利用数论的方法得到计算有向环网D(n;s_1,s_2,s_3)的直径的公式,解决了出度为3的有向环网的直径计算问题。对研究具有任意出度的有向环网的直径计算问题有一定参考作用。

The diameter of a loop network is the maximal distance between any two vertices in the network. In order to design a optimal loop network with the shortest diameter for given n vertices,it is necessary to solve first the computational problem about the diameter of the loop network. Using number-theory method,a formula for computing the diameters of directed loop networks D(n;s1,s2,s3) is given in this paper. The problem for computing diameters of directed loop networks with outdegree of 3 has been solved. It is useful for further study of the problem with arbitrary outdegree.