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

• 作者: 杨文国 谭屯子 高随祥
• 来源期刊: 中国科学院大学学报
• 学科: 数学
• 关键词: 连通性 广度优先搜索 深度优先搜索 指数和 Laplacian矩阵 逻辑和
• 年，卷（期）: 2018,（5）
• 所属期刊栏目: 数学与物理学
• 页码范围: 582-588
• 页数: 7页
• 分类号: O157.5
• 语种: 中文
• DOI: 10.7523/j.issn.2095-6134.2018.05.002

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	高随祥	中国科学院大数据挖掘和知识管理重点实验室	47	413	11.0	19.0
2	杨文国	中国科学院大学数学科学学院	27	248	9.0	15.0
3	谭屯子	中国科学院大学数学科学学院	1	0	0.0	0.0