代数连通度

图的代数连通度（algebraic connectivity）是的拉普拉斯矩阵的第二小的特征值（重特征值要重复计算）。这个特征值大于0当且仅当是连通图。这是一个简单的推论，因为拉普拉斯矩阵的特征值0的重数就是图的连通分支的个数。这个值的大小反映了整个图的连通程度。它可以用于分析网络的稳定性与可同步性。

性质 
图的代数连通度大于0当且仅当是连通图。而且，图的代数连通度的值不大于（顶点）连通度。设一个连通图有个顶点且直径为，则代数连通度的一个下界是，而且根据Brendan McKay的一个结果这个下界可以改进为。对于上图中的例子，。

不像传统的连通度，代数连通度除了与顶点的连接方式有关以外，还与顶点的个数有关。对随机图，代数连通度随顶点数增大而减小，随平均度的增大而增大。

代数连通度的具体定义依赖于所使用的拉普拉斯矩阵的类型。金芳蓉使用一种重新标度的拉普拉斯矩阵，消除了对顶点数的依赖，所以上下界有所不同。

拉普拉斯矩阵自然地出现在网络上的同步模型中，例如藏本模型，因而代数连通度标志了网络达到同步的容易程度。也可以使用其他度量，例如平均距离（特征路径长度），实际上代数连通度与平均距离（的倒数）密切相关。

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}。

另见 

 连通图

参考资料 

代数图论
图的连通性