基于L形瓦的无向双环网络直径求解算法  

Calculation method of bidirectional double-loop networks diameter based on L-shape tile

作　　者：刘辉[1] 方木云[1] 郑啸[1] 李颖[2] 

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

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

基　　金：国家自然科学基金资助项目(61003311);安徽省教育厅重大项目(ZD2008005-1);安徽省教育厅重点项目(KJ2012A262);安徽工业大学科研项目(QZ201114)

摘　　要：针对构造无向双环网络最短路径图(MDD)常用的节点遍历方式较为复杂、割裂了有向双环网络和无向双环网络之间的内在联系的问题,将有向双环网络拓扑结构映射到平面直角坐标系,在得到的L形瓦基础上,对其上的节点坐标通过简单坐标变换,得到无向双环网络MDD上对应节点坐标,进而计算无向双环网络的直径.相对于目前构造无向双环网络MDD或其等价拓扑结构普遍采用节点遍历方式而言,该算法仅增加了几次比较,就改善并提高了无向双环网络直径的求解效率.Node traversing method is widely used in constructing minimum distance diagram （MDD） of double-loop networks, which seperates the relationship between the bidirectional double-loop net works and the unidirectional double-loop networks. Firstly topology of unidirectional double loop net- works was reflected in Cartesian coordinates to get minimum distance diagram which was L-shape tile. Then, a method to calculate the diameter of bidirectional double-loop networks was presented based on L-shape tile to change the locations of nodes from the unidirectional region into bidirectional region in Cartesian coordinates. By using this method, the fast algorithm was presented to construct the MDD of bidirectional double-loop networks and calculalc the diameter of bidirectional double-loop net- works. Compared with node traversing method, this method is based on the L-shape tile and only adds a few steps to calculate, improving research of diameter of the bidirectional double-loop networks efficiently.

关 键 词：有向双环网络 无向双环网络 坐标映射 L-形瓦 直径 最短路径图 

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