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

连通性; 广度优先搜索; 深度优先搜索; 指数和; Laplacian矩阵; 逻辑和 connectedness; breadth-first search; depth-first search; power sum; Laplacian matrix; logical sum

University of Chinese Academy of Sciences