，直径3，连通度1，代数连通度0.722。]]
图G的代数连通度（algebraic connectivity）是G的拉普拉斯矩阵的第二小的特征值（重特征值要重复计算）。这个特征值大于0当且仅当G是连通图。这是一个简单的推论，因为拉普拉斯矩阵的特征值0的重数就是图的连通分支的个数。这个值的大小反映了整个图的连通程度。它可以用于分析网络的稳定性与可同步性。
性质
图G的代数连通度大于0当且仅当G是连通图。而且，图的代数连通度的值不大于（顶点）连通度。设一个连通图有n个顶点且直径为D，则代数连通度的一个下界是\frac 1{nD}，而且根据Brendan McKay的一个结果这个下界可以改进为\frac 4{nD}。对于上图中的例子，4/18=0.222\le0.722\le1。
不像传统的连通度，代数连通度除了与顶点的连接方式有关以外，还与顶点的个数有关。对随机图，代数连通度随顶点数增大而减小，随平均度的增大而增大。
代数连通度的具体定义依赖于所使用的拉普拉斯矩阵的类型。金芳蓉使用一种重新标度的拉普拉斯矩阵，消除了对顶点数的依赖，所以上下界有所不同。
拉普拉斯矩阵自然地出现在网络上的同步模型中，例如藏本模型，因而代数连通度标志了网络达到同步的容易程度。也可以使用其他度量，例如平均距离（特征路径长度），实际上代数连通度与平均距离（的倒数）密切相关。
File:C60a.png|截角二十面体，也是巴克明斯特富勒烯的结构图，连通度为3，而代数连通度为0.243。
Fiedler向量
代数连通度的相关理论最早由Miroslav Fiedler提出。为了纪念他，与代数连通度对应的特征向量命名为Fiedler向量。Fieldler向量可用于图的划分。
用Fiedler向量对图进行划分
以首段中的图为例，Fiedler向量为(0.415, 0.309, 0.069, -0.221, 0.221, -0.794)。负值对应连通程度很差的点6，及其相邻的节点4；而正值对应其他顶点。因此可以根据Fiedler向量中的符号把图分成两部分：{1, 2, 3, 5}与{4, 6}。另外，值0.069非常接近0，可以单独成为一类，这样就把图分成三部分：{1, 2, 5}, {3}, {4, 6}。
另见
- 连通图
参考资料
评论 (0)