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

摘要

许多现实问题可以抽象成无向简单连通图的生成问题.为了从节点的度数序列得到所有可能的无向简单连通图,针对度数序列设计了适合用计算机实现的去点回溯算法,证明了算法的正确性,通过每一步去点回溯后的变化矩阵,得到生成无向简单连通图所需的邻接矩阵,并最终用计算机实现了该算法,解决了节点度数已知时无向简单连通图的生成问题.%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.