判断一个无向图是否连通图的方法

doi:10.7523/j.issn.2095-6134.2018.05.002

中国科学院大学学报 ›› 2018, Vol. 35 ›› Issue (5): 582-588.DOI: 10.7523/j.issn.2095-6134.2018.05.002

判断一个无向图是否连通图的方法

谭屯子, 高随祥, 杨文国

中国科学院大学数学科学学院, 北京 100049;中国科学院大数据挖掘和知识管理重点实验室, 北京 100190

收稿日期:2017-02-18 修回日期:2017-11-15 发布日期:2018-09-15
通讯作者: YANG Wenguo
基金资助:
Supported by the National 973 Plan project(2011CB706900), the National 863 Plan project (2011AA01A102), the NSFC (11331012,11571015) and the "Strategic Priority Research Program" of Chinese Academy of Sciences (XDA06010302)

Determining the connectedness of an undirected graph

TAN Tunzi, GAO Suixiang, YANG Wenguo

School of Mathematical Sciences, University of Chinese Academy of Sciences, Beijing 100049, China;Key Laboratory of Big Data Mining and Knowledge Management of Chinese Academy of Sciences, Beijing 100190, China

Received:2017-02-18 Revised:2017-11-15 Published:2018-09-15
Supported by:
Supported by the National 973 Plan project(2011CB706900), the National 863 Plan project (2011AA01A102), the NSFC (11331012,11571015) and the "Strategic Priority Research Program" of Chinese Academy of Sciences (XDA06010302)

摘要/Abstract

摘要： 判断图的连通性质是一个经典的图论问题，也是应用图挖掘和图分解的重要子问题。除了图分解，图的连通性质也被运用于追踪疾病的传播、大型系统设计、社交网络分析和"Cayley图"的一些理论研究。首先综述几种重要的判断无向图是否是连通图的方法，例如广度优先搜索、深度优先搜索和图的拉普拉斯矩阵的特征值。此外，提出一些新方法，例如邻接矩阵的指数和及逻辑和，其中逻辑和是基于搜索方法的计算形式。在随机生成的超过10 000个顶点的图上测试了所有方法，结果显示广度优先搜索和逻辑和方法在超过100个顶点的大图上效果最好，逻辑和最快。

关键词: 连通性, 广度优先搜索, 深度优先搜索, 指数和, Laplacian矩阵, 逻辑和

Abstract: Determining the connectedness of an undirected graph is a frequent issue in practical graph mining and regarded as a key subproblem of the graph partitioning problem. Apart from graph partitioning, graph connectedness also plays an imperative role in tracking the spread of disease, VLSI design, social network analysis, and theoretical studies in graph theory such as "Cayley graph". This work reviews several important methods for determining the connectedness of an undirected graph, such as breadth-first search, depth-first search, and the eigenvalues of a graph Laplacian matrix. In addition, we propose several new methods, such as power sum and logical sum of adjacency matrix. We compare all the relevant methods empirically on random graphs with up to 10 000 vertices, and show that the breadth-first search and logical sum methods deliver good performances on large graphs with more than 100 vertices and the logical sum method is the fastest.

Key words: connectedness, breadth-first search, depth-first search, power sum, Laplacian matrix, logical sum

中图分类号:

O157.5

谭屯子, 高随祥, 杨文国. 判断一个无向图是否连通图的方法[J]. 中国科学院大学学报, 2018, 35(5): 582-588.

TAN Tunzi, GAO Suixiang, YANG Wenguo. Determining the connectedness of an undirected graph[J]. , 2018, 35(5): 582-588.

参考文献

[1] Alan G. Algorithmic graph theory[J]. Oberwolfach Reports, 1989, 3(1):379-460.
[2] Douglas B W. Introduction to graph theory[M]. 2nd ed. Upper Saddle River:Prentice hall, 2001.
[3] Robert S, Kevin W. Algorithms[M]. 4th ed. Boston:Addison-Wesley Professional, 2011.
[4] Santanu S R. Graph theory with algorithms and its applications:in applied science and technology[M]. India:Springer, 2013.
[5] Lorenzo B, Michele C, Giovanni R. A Branch-and-cut algorithm for the Equicut problem[J]. Mathematical Programming, 1997, 78(2):243-263.
[6] John E M. Branch and cut for the k-way Equipartition Problem[J]. Discrete Optimization, 2007, 4(1):87-102.
[7] Stefan E K, Franz R, Jens C. Solving graph Bisection problems with Semidefinite Programming[J]. INFORMS Journal on Computing, 2000, 12(3):177-191.
[8] Huang A, Zhu W. Connectedness of graphs and its application to connected matroids through covering-based rough sets[J]. Soft Computing, 2016, 20(5):1841-1851.
[9] Andrew B K, Jens L, Igor L M, et al. VLSI physical design:from Born graph partitioning to timing closure[M]. Hamburg:Springer, 2011.
[10] Maria C, Bernard R, Yori Z. Claw-free graphs with strongly perfect complements:fractional and integral version. part I. Basic graphs[J]. Discrete Applied Mathematics, 2011, 159(17):1971-1995.
[11] James A B. Graph theory and social networks:a technical comment on connectedness and connectivity[J]. Sociology, 1969, 3(2):215-232.
[12] Laszlo B. Some applications of graph contractions[J]. Journal of Graph Theory, 1977, 1(2):125-130.
[13] Edward F M. The shortest path through a maze[J]. In proceedings of the International Symposium on the Theory of Switching, 1959:285-292.
[14] Lee C Y. An algorithm for path connections and its applications[J]. IRE Transactions on Electronic Computers, 1961, 3(1):346-365.
[15] Thomas H C, Charles E L, Ronald L R, et al. Introduction to algorithms[M]. 3rd edition. Cambridge:MIT Press, 2001.
[16] Shimon E. Graph algorithms[M]. Cambridge and New York:Cambridge University Press, 2011.
[17] Pearson K. The problem of the random walk[J]. Nature, 1905, 72(1865):294.
[18] Kampen N G. Stochastic processes in physics and chemistry[M]. Revised and enlarged edition. Amsterdam/London/New York/Tokyo:Elsevier, 1992.
[19] Pierre D G. Scaling concepts in polymer physics[M]. Ithaca and London:Cornell University Press, 1979.
[20] Sriram V P, Steven S S. Computational discrete mathematics:combinatorics and graph theory with mathematica[M]. Cambridge:Cambridge University Press, 2009.
[21] Chung F. Spectral graph theory[M]. New York:American Mathematical Society, 1997.
[22] Michael W N. The Laplacian spectrum of graphs[D]. Manitoba:University of Manitoba, 2000.
[23] Li T Y. The Laguerre tteration in solving the symmetric tridiagonal eigenproblem, revisited[J]. SIAM Journal on Scientific Computing, 1994, 15(5):1145-1173.

判断一个无向图是否连通图的方法

Determining the connectedness of an undirected graph

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 2

编辑推荐

Metrics

本文评价

访问统计

联系我们

[1]	刘波, 陈华. 一种基于项重写的密码模块API安全性检测算法[J]. 中国科学院大学学报, 2013, 30(5): 699-705.
[2]	刘春雷, 徐兰菊. 有理函数上的狄雷克莱特征[J]. 中国科学院大学学报, 2005, 22(1): 1-10.