组合星图的最优生成树  

An Optimal Spanning Tree in (n,k)-Star Graph Networks

作　　者：李静力[1] 向永红[2] 陈蔓莉[1] 周永恒[1] 

机构地区：[1]云南大学信息学院,云南昆明650091 [2]云南大学软件学院,云南昆明650091

出　　处：《微电子学与计算机》2006年第9期168-170,共3页Microelectronics & Computer

基　　金：云南省自然科学基金(NO.2004F00062);云南大学自然科学基金(NO.2003Q022A)

摘　　要：文章解决了组合星图生成树的构造问题。首先给出了组合星图的定义及其重要的拓扑性质,然后采用构造方法获得了组合星图的一棵高度为D(Sn,k)的生成树,并给出了相应的算法,其中D(Sn,k)为组合星图的直径。该生成树具有最优的高度,且是一棵贪婪树。A spanning tree of optimal height is obtained in （n, k）-star graph networks. An algorithm for constructing a greedy spanning tree of height D（Sn,k） is given, where D（Sn,k） is the diameter of the （n, k）-star grapho The algorithm is proved to be correct and the result is optimal.

关 键 词：组合星图 距离 生成树 

分 类 号：TP31[自动化与计算机技术—计算机软件与理论]