| 判断一个无向图是否连通图的方法 |
| |
| 作者姓名： | 谭屯子 高随祥 杨文国 |
| |
| 作者单位： | 中国科学院大学数学科学学院, 北京 100049;中国科学院大数据挖掘和知识管理重点实验室, 北京 100190 |
| |
| 基金项目： | 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) |
| |
| 摘 要： | 判断图的连通性质是一个经典的图论问题，也是应用图挖掘和图分解的重要子问题。除了图分解，图的连通性质也被运用于追踪疾病的传播、大型系统设计、社交网络分析和"Cayley图"的一些理论研究。首先综述几种重要的判断无向图是否是连通图的方法，例如广度优先搜索、深度优先搜索和图的拉普拉斯矩阵的特征值。此外，提出一些新方法，例如邻接矩阵的指数和及逻辑和，其中逻辑和是基于搜索方法的计算形式。在随机生成的超过10 000个顶点的图上测试了所有方法，结果显示广度优先搜索和逻辑和方法在超过100个顶点的大图上效果最好，逻辑和最快。
|
| 关 键 词： | 连通性 广度优先搜索 深度优先搜索 指数和 Laplacian矩阵 逻辑和 |
| 收稿时间： | 2017-02-18 |
| 修稿时间： | 2017-11-15 |
Determining the connectedness of an undirected graph |
| |
| Authors: | TAN Tunzi GAO Suixiang YANG Wenguo |
| |
| Institution: | 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 |
| |
| 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. |
| |
| Keywords: | connectedness breadth-first search depth-first search power sum Laplacian matrix logical sum |
|
| 点击此处可从《》浏览原始摘要信息 |
| 点击此处可从《》下载免费的PDF全文 |
