双环网络G(N;1,s)等价生成树  

Equivalent span-tree of double-loop network G(N;1,s)

作　　者：秦飞[1] 郑毅[2] 刘明[1] 方木云[1] 

机构地区：[1]安徽工业大学计算机学院,安徽马鞍山243002 [2]中冶华天工程技术有限公司,安徽马鞍山243002

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

基　　金：国家自然科学基金资助项目(60473142);安徽省计算机与通信软件重点实验室资助项目;安徽省教育厅重大项目(ZD2008005-1)

摘　　要：提出研究双环网络G(N;1,s)的抽象模型——等价生成树,并对其性质进行了研究,给出了双环网络G(N;1,s)等价生成树的构造方法.提出基于等价生成树G(N;1,s)的直径d(N;1,s)的求解算法,并给出了其显式公式,利用C语言编程对等价生成树的结构模型进行了仿真.结果表明:算法不仅可在有限时间内求出G(N;1,s)的所有直径,而且可方便地得到源结点到所有其他结点的最短路径.算法的复杂度为O(N).A new abstract model-equivalent span-tree was proposed to study double-loop network G（N; 1, s）. A method creating equivalent span-tree of double-loop network G（N; 1, s） was given. A simple formula for expressing d（N; 1, s） of this network based on equivalent span-tree was presented. With C severing as program, the equivalent span tree models were given. The results indicates that the algorithm not only can get all diameters of double-loop networks G（N; 1, s） in limited time but also can obtain the shortest path which from the source node to others nodes. The complexity of algorithm is O（N）.

关 键 词：双环网络 等价生成树 紧优 拓扑结构 复杂度 

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