从节点度数生成无向简单连通图  

Building connected undirected simple graph from degree of vertex

作　　者：毛国勇[1,2] 张宁[3] 

机构地区：[1]常州工学院电子信息与电气工程学院,江苏常州213002 [2]常州市软件技术研究与应用重点实验室,江苏常州213002 [3]上海理工大学管理学院,上海200093

出　　处：《计算机工程与应用》2011年第29期40-41,106,共3页Computer Engineering and Applications

基　　金：国家自然科学基金(the National Natural Science Foundation of China under Grant No.70971089)

摘　　要：许多现实问题可以抽象成无向简单连通图的生成问题。为了从节点的度数序列得到所有可能的无向简单连通图,针对度数序列设计了适合用计算机实现的去点回溯算法,证明了算法的正确性,通过每一步去点回溯后的变化矩阵,得到生成无向简单连通图所需的邻接矩阵,并最终用计算机实现了该算法,解决了节点度数已知时无向简单连通图的生成问题。Many real problems can be abstracted into problems related to the generating of undirected simple connected graph.To get all possible undirected simple connected graphs from degree of each node, the point-cutting and backtracking algorithm suitable for computer implementation is brought forward based on series of degrees.The correctness of algorithm is proved.The adjacency matrix needed for generating undirected simple connected graph can be reached from the changing matrix derived from each step of point-cutting and backtracking algorithm.This algorithm is implemented using computer in the end.

关 键 词：去点 回溯 度数 无向简单连通图 

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