【图论】系列（二）图的连通性

与矩阵有关的衡量图的连通性的所有指标

目录

• 与矩阵有关的衡量图的连通性的所有指标
• • 1、邻接矩阵（Adjacency Matrix）
  • 2、拉普拉斯矩阵（Laplacian Matrix）
  • 3、广义拉普拉斯矩阵（Generalized Laplacian Matrix）
  • 4、不可约拉普拉斯矩阵（Irreducible Laplacian Matrix）
  • 5、冗余矩阵（Redundancy Matrix）
  • 6、传递矩阵（Propagation Matrix）
  • 7、节点相似度矩阵（Node Similarity Matrix）
  • 8、特征向量中心性（Eigenvector Centrality）
  • 9、谱半径（Spectral Radius）
  • 10、强连通分量矩阵（Strongly Connected Components Matrix）
  • 11、强连通性判定（Floyd-Warshall算法）

1、邻接矩阵（Adjacency Matrix）

邻接矩阵的幂次可以帮助判断图的连通性。通过计算邻接矩阵的高次幂（例如 A k {A^k} Ak），如果图是连通的，任意两点之间都有路径。

强连通性的作用：

• 如果图是强连通的，任意两个节点之间应该存在路径。如果图是强连通的，可以通过邻接矩阵的高次幂来验证：
  • 如果图是强连通的，那么存在一个整数k， 使得邻接矩阵的高次幂 A k {A^k} Ak中所有元素都大于零。这意味着通过
    
    标签：图论,系列,Matrix,拉普拉斯,矩阵,邻接矩阵,图是,连通性
    From： https://blog.csdn.net/qq_30066733/article/details/145130924