查看“︁代数连通度”︁的源代码

[[File:6n-graf.svg|thumb|一个例图，6[[顶点 (图论)|顶点]]，直径3，[[连通图|连通度]]1，代数连通度0.722。]]
图<math>G</math>的'''代数连通度'''（algebraic connectivity）是<math>G</math>的[[拉普拉斯矩阵]]的第二小的[[特征值和特征向量|特征值]]（重特征值要重复计算）。<ref>Weisstein, Eric W. "Algebraic Connectivity." From MathWorld--A Wolfram Web Resource. </ref>这个特征值大于0当且仅当<math>G</math>是[[连通图]]。这是一个简单的推论，因为拉普拉斯矩阵的特征值0的重数就是图的连通分支的个数。这个值的大小反映了整个图的连通程度。它可以用于分析网络的稳定性与可同步性。

== 性质 ==
图<math>G</math>的代数连通度大于0当且仅当<math>G</math>是连通图。而且，图的代数连通度的值不大于（[[顶点 (图论)|顶点]]）连通度。<ref>J.L. Gross and J. Yellen. Handbook of Graph Theory, CRC Press, 2004, page 314. </ref>设一个连通图有<math>n</math>个[[顶点 (图论)|顶点]]且直径为<math>D</math>，则代数连通度的一个下界是<math>\frac 1{nD}</math>，<ref>J.L. Gross and J. Yellen. Handbook of Graph Theory, CRC Press, 2004, page 571. </ref>而且根据Brendan McKay的一个结果这个下界可以改进为<math>\frac 4{nD}</math>。<ref name="Bojan Mohar">Bojan Mohar, The Laplacian Spectrum of Graphs, in Graph Theory, Combinatorics, and Applications, Vol. 2, Ed. Y. Alavi, G. Chartrand, O. R. Oellermann, A. J. Schwenk, Wiley, 1991, pp. 871–898. </ref>对于上图中的例子，<math>4/18=0.222\le0.722\le1</math>。

不像传统的连通度，代数连通度除了与[[顶点 (图论)|顶点]]的连接方式有关以外，还与顶点的个数有关。对[[随机图]]，代数连通度随顶点数增大而减小，随平均度的增大而增大。<ref>Synchronization and Connectivity of Discrete Complex Systems, Michael Holroyd, International Conference on Complex Systems, 2006. </ref>

代数连通度的具体定义依赖于所使用的拉普拉斯矩阵的类型。[[金芳蓉]]使用一种重新标度的拉普拉斯矩阵，消除了对[[顶点 (图论)|顶点]]数的依赖，所以上下界有所不同。<ref>F. Chung. Spectral Graph Theory, Providence, RI: Amer. Math. Soc., 1997.[1] </ref>

拉普拉斯矩阵自然地出现在网络上的[[同步]]模型中，例如[[藏本模型]]，因而代数连通度标志了网络达到同步的容易程度。<ref>Tiago Pereira, Stability of Synchronized Motion in Complex Networks, arXiv:1112.2297v1, 2011. </ref>也可以使用其他度量，例如平均距离（特征路径长度），<ref>D. Watts, Six Degrees: The Science of a Connected Age, Vintage, 2003. </ref>实际上代数连通度与平均距离（的倒数）密切相关。<ref name="Bojan Mohar"></ref><gallery>
File:C60a.png|[[截角二十面體|截角二十面体]]，也是[[巴克明斯特富勒烯]]的结构图，连通度为3，而代数连通度为0.243。
</gallery>

== Fiedler向量 ==
代数连通度的相关理论最早由Miroslav Fiedler提出。<ref>M. Fiedler. "Algebraic connectivity of Graphs", Czechoslovak Mathematical Journal 23(98) (1973), 298–305. </ref><ref>M. Fiedler. "Laplacian of graphs and algebraic connectivity", Combinatorics and Graph Theory (Warsaw, 1987), Banach Center Publications 25(1) (1989), 57–70. </ref>为了纪念他，与代数连通度对应的特征向量命名为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}。

== 另见 ==

* [[连通图]]

== 参考资料 ==
<references />


[[Category:代数图论]]
[[Category:图的连通性]]