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

谭屯子; 高随祥; 杨文国

首页> 中文期刊> 《中国科学院大学学报》 >判断一个无向图是否连通图的方法

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

开具论文收录证明 >>

期刊封面封底目录下载 >>

文献代查 >>

页面导航

摘要
著录项
相似文献
相关主题

摘要

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

著录项

来源
《中国科学院大学学报》 |2018年第5期|P.582-588|共7页
作者
谭屯子; 高随祥; 杨文国;
展开▼
作者单位

中国科学院大学数学科学学院北京100049;

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

展开▼
原文格式 PDF
正文语种 chi
中图分类图论;
关键词
连通性; 广度优先搜索; 深度优先搜索; 指数和; Laplacian矩阵; 逻辑和;

相似文献

中文文献
外文文献
专利

1. 判断一个无向图是否连通图的方法 [J] . 谭屯子 ,高随祥 ,杨文国 . 中国科学院研究生院学报 . 2018,第005期
2. 用矩阵判断无向图同构的几种方法 [J] . 张磊 ,李世群 . 衡阳师范学院学报 . 2011,第006期
3. 如何判断一个行业是否值得加入? [J] . 刘润 . 商界 . 2021,第009期
4. 如何判断一个数是否为数列中的项 [J] . 陈小红 . 新世纪智能 . 2019,第024期
5. 如何判断一个人是否具有领导人的潜力? [J] . . 五金科技 . 2018,第001期
6. 一种判断降膜管是否泄漏的新方法 [C] . 黄敏刚 . 第35全国氯碱行业技术年会暨第18届“佑利杯”论文交流会 . 2017
7. 具有唯一一个“割点源”的标号有向连通图的计数 [A] . 荆贺明 . 2006

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

摘要

著录项

相似文献

相关主题

期刊订阅