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

计算机工程与应用 ›› 2011, Vol. 47 ›› Issue (29): 40-41.

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

毛国勇1，2，张宁3

1.常州工学院电子信息与电气工程学院，江苏常州 213002
2.常州市软件技术研究与应用重点实验室，江苏常州 213002
3.上海理工大学管理学院，上海 200093

收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2011-10-11 发布日期:2011-10-11

Building connected undirected simple graph from degree of vertex

MAO Guoyong1，2，ZHANG Ning3

1.School of Electronic Information and Electric Engineering，Changzhou Institute of Technology，Changzhou，Jiangsu 213002，China
2.Changzhou Key Lab for Research and Application of Software Technology，Changzhou，Jiangsu 213002，China
3.Business School，University of Shanghai for Science and Technology，Shanghai 200093，China

Received:1900-01-01 Revised:1900-01-01 Online:2011-10-11 Published:2011-10-11

摘要/Abstract

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

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

Abstract: 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.

Key words: point-cutting, backtracking, degree, undirected simple connected graph

毛国勇1，2，张宁3. 从节点度数生成无向简单连通图[J]. 计算机工程与应用, 2011, 47(29): 40-41.

MAO Guoyong1，2，ZHANG Ning3. Building connected undirected simple graph from degree of vertex[J]. Computer Engineering and Applications, 2011, 47(29): 40-41.

[1]	魏锋涛，史云鹏，石坤. 具有组合变异策略的回溯搜索优化算法[J]. 计算机工程与应用, 2020, 56(9): 41-47.
[2]	苟海雯，宁爱兵，胡沁，张惠珍. 带惩罚的无容量设施选址问题的降阶回溯算法[J]. 计算机工程与应用, 2020, 56(24): 43-49.
[3]	王丽1，王晓凯2. 多峰函数优化的改进群居蜘蛛优化算法[J]. 计算机工程与应用, 2017, 53(3): 1-6.
[4]	谭高，肖昌炎，文谦. 基于测地线投票的CT图像肺裂检测[J]. 计算机工程与应用, 2017, 53(24): 191-195.
[5]	王鹏，陈得宝，邹锋，李峥. 引导小生境回溯优化算法[J]. 计算机工程与应用, 2017, 53(21): 126-131.
[6]	徐新林，胡中波，何先平，苏清华. 自适应变异尺度系数和混合选择的回溯搜索算法[J]. 计算机工程与应用, 2017, 53(17): 6-13.
[7]	陈雷1，2，韩大伟3，郭艳菊3，李媛媛3，贾志成3. 基于回溯搜索优化的卷积混合语音盲分离[J]. 计算机工程与应用, 2017, 53(15): 137-143.
[8]	贺靖卿，岳春生，胡泽明. 考虑综合性约束的软件无线电应用部署算法[J]. 计算机工程与应用, 2017, 53(15): 239-243.
[9]	张智磊1，刘三阳2. 基于回溯搜索算法的决策粗糙集属性约简[J]. 计算机工程与应用, 2016, 52(10): 71-74.
[10]	刘艳芳，宁爱兵，王英磊. 图的Steiner最小树问题的降阶回溯算法[J]. 计算机工程与应用, 2014, 50(7): 67-70.
[11]	杜世民1，2，夏银水2，黄诚2，杨润萍1. 一种有效的面向软模块的VLSI布图规划算法[J]. 计算机工程与应用, 2014, 50(4): 50-56.
[12]	于屏方1，2，杜家利3，4. 扩充转移网络在自然语言句法处理中的应用 ——以歧义句和花园幽径句对照分析为例[J]. 计算机工程与应用, 2012, 48(17): 23-30.
[13]	贺新光，聂新艳，秦建新，夏卫生. 地下水流可视化多尺度数值模拟系统设计与实现[J]. 计算机工程与应用, 2011, 47(8): 226-231.
[14]	姚雄武，郑金华，潘文俊. 用进化算法和函数优化模型分析回溯算法上界[J]. 计算机工程与应用, 2010, 46(9): 26-30.
[15]	潘大志^1，2，杜勇³，谭代伦¹，刘志斌². 位运算在N皇后问题中的应用[J]. 计算机工程与应用, 2009, 45(32): 61-62.