基于树的无向双环网络G(N;±r,±s)寻径策略  

The algorithm to calculate the diameter of undirected double loop networks G(N;±r,±s) based on tree

作　　者：李颖[1] 陈业斌[2] 

机构地区：[1]马鞍山师范高等专科学校,安徽马鞍山243041 [2]安徽工业大学计算机学院,安徽马鞍山243002

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

基　　金：安徽省教育厅重大项目(ZD2008005-1);安徽省教育厅自然科学基金资助项目(KJ2007B078)

摘　　要：提出了新的无向双环网络G(N;±r,±s)的直径求解方法,将其图论模型中的节点进行了重新排列,得到了一种基于树的路由模型,研究了该树型结构中与路由相关的一些性质;给出了计算无向双环网络G(N;±r,±s)直径d(N;±r,±s)的显式公式;证明了无向双环网络G(N;±r,±s)的直径等于树高;验证了Boe-sch和Wang等提出的无向双环网络G(N;±r,±s)直径的下界.A new method was presented to calculate the diameter of undirected double-loop networks G（N;±r,±s）. A new routing modal, tree-structure, was presented by arranging all nodes of undi- rected double-loop networks G（N;±r,±s） over again. Some characters of the tree-modal about routing was studied. A simple formula for expressing d（N;±r,±s） was presented to calculate the diameter of undirected double-loop networks G（N;±r,±s）. It was proved that the diameter of undirected double-loop networks G（N;±r,±s） equals to the height of tree-modal. The limited bound of diameter for undirected double-loop networks G（N;±r,±s） presented by Boesch and Wang was certified.

关 键 词：无向双环网络 最短路径 树型结构 直径 层 路由 

分 类 号：TP302[自动化与计算机技术—计算机系统结构] O157.9[自动化与计算机技术—计算机科学与技术]