无向双环网络G(N;±r,±s)直径求解方法  

A new method to calculate the diameter of undirected double-loop network

作　　者：方木云[1] 赵保华[2] 屈玉贵[2] 戴小平[1] 

机构地区：[1]安徽工业大学计算机学院,安徽马鞍山243002 [2]中国科技大学计算机系,安徽合肥230027

出　　处：《华中科技大学学报（自然科学版）》2006年第9期14-17,共4页Journal of Huazhong University of Science and Technology(Natural Science Edition)

基　　金：国家自然科学基金资助项目(60473142);安徽省教育厅资助项目(2005KJ076)

摘　　要：提出新的无向双环网络G(N;±r,±s)的直径求解法———分步法;并得到一种新的直观图———螺旋环,研究了螺旋环的性质;给出了无向双环网络的直径d(N;±r,±s)的显式公式;给出了N,s都固定的直径算法;在N固定,且2≤r<s≤N-1时,给出了一族无向双环网络的直径算法.利用VB6.0和SQL Server2000来仿真后者;对任意N,有不少r,s使得G(N;±r,±s)紧优或几乎紧优.验证了Boesch和Wang等提出的无向双环网络G(N;±r,±s)的直径下界;给出了一个新的直径上界公式.A new method, step-search-diameter, is presented to calculate the diameter of undirected double-loop networks G（N;±r, ±s）. A new intuitional diagram, spiral ring, is obtained by this method and its attributes were studied. A simple formula for expressing d（N;±r, ±s） of this network is presented. The algorithm to calculate the network with fixed N and s and the one to calculate the diameter of the networks with fixed N and r,s（r〈s） varying to N-1 from 2 are both given. The latter algorithm was simulated by VB6.0 and SQL Server2000. The results show that for any given N, many s make G（N;±r, ±s） tight optimal or nearly tight optimal. The limited bound of the diameter of the network G（N;±r,±s） presented by Boesch and Wang was certified. A new for mula for calculating the upper bound of the diameter of the networks is also given.

关 键 词：无向双环网络 分步法 螺旋环 紧优 族 

分 类 号：O157.9[理学—数学] TP302[理学—基础数学]