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

Method to calculate the diameter of undirected double-loop networks G(N;±1,±s)

作　　者：方木云[1] 赵保华[1] 

机构地区：[1]中国科学技术大学计算机系

出　　处：《通信学报》2007年第2期124-129,共6页Journal on Communications

基　　金：国家自然科学基金资助项目(60473142)~~

摘　　要：提出新的无向双环网络G(N;±1,±s)的直径求解法——分步法,并得到一种新的直观图——螺旋环,研究了螺旋环的性质,给出无向双环网络的直径d(N;±1,±s)的显式公式,给出N,s都固定的直径算法。给出N固定,2≤s≤N?1这样一族无向双环网络的直径算法。利用VB6.0和SQL Server 2000来仿真2≤s≤N?1,找出了该族无向双环网络直径的分布特点:具有最大值、最小值和中间对称性;对任意N,有不少s使得G(N;±1,±s)紧优或几乎紧优。验证了Boesch和Wang等提出的无向双环网络G(N;±1,±S)的直径下界,给出了一个新的直径上界公式。A new method, step-search-diameter, to calculate the diameter of undirected double-loop networks G（N;±1,±s） was presented. A new diagram, spiral ring whose attributes were studied, was obtained by this method. A simple formula to express the d（N;±1,±s） of undirected double-loop networks was presented. The algorithm to calculate the diameter of undirected double-loop networks whose N,s were fixed and the algorithm to calculate the diameter of undirected double-loop networks whose N was fixed but s varied from 2 to N-1 were both given. VB6.0 and SQL Server 2000 were used to simulate the latter algorithm The diameters of such familY of undirected double-loop networks had such characters： maximum values, minimum values, symmetry. For any given N, many s made GG（N;±1,±s） tight optimal or nearly tight optimal. The limited bound of diameter of undirected double-loop networks G（N;±1,±s） presented by Boesch and Wang is certified. A new formula to calculate the upper bound of the diameter of undirected double-loop networks is presented.

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

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