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