代數連通度
圖的代數連通度（algebraic connectivity）是的拉普拉斯矩陣的第二小的特徵值（重特徵值要重複計算）。[1]這個特徵值大於0若且唯若是連通圖。這是一個簡單的推論，因為拉普拉斯矩陣的特徵值0的重數就是圖的連通分支的個數。這個值的大小反映了整個圖的連通程度。它可以用於分析網絡的穩定性與可同步性。
性質 編輯
圖 的代數連通度大於0若且唯若 是連通圖。而且，圖的代數連通度的值不大於（頂點）連通度。[2]設一個連通圖有 個頂點且直徑為 ，則代數連通度的一個下界是 ，[3]而且根據Brendan McKay的一個結果這個下界可以改進為 。[4]對於上圖中的例子， 。
不像傳統的連通度，代數連通度除了與頂點的連接方式有關以外，還與頂點的個數有關。對隨機圖，代數連通度隨頂點數增大而減小，隨平均度的增大而增大。[5]
代數連通度的具體定義依賴於所使用的拉普拉斯矩陣的類型。金芳蓉使用一種重新標度的拉普拉斯矩陣，消除了對頂點數的依賴，所以上下界有所不同。[6]
拉普拉斯矩陣自然地出現在網絡上的同步模型中，例如藏本模型，因而代數連通度標誌了網絡達到同步的容易程度。[7]也可以使用其他度量，例如平均距離（特徵路徑長度），[8]實際上代數連通度與平均距離（的倒數）密切相關。[4]
Fiedler向量 編輯
代數連通度的相關理論最早由Miroslav Fiedler提出。[9][10]為了紀念他，與代數連通度對應的特徵向量命名為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}。
另見 編輯
參考資料 編輯
- ^ Weisstein, Eric W. "Algebraic Connectivity." From MathWorld--A Wolfram Web Resource.
- ^ J.L. Gross and J. Yellen. Handbook of Graph Theory, CRC Press, 2004, page 314.
- ^ J.L. Gross and J. Yellen. Handbook of Graph Theory, CRC Press, 2004, page 571.
- ^ 4.0 4.1 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.
- ^ Synchronization and Connectivity of Discrete Complex Systems, Michael Holroyd, International Conference on Complex Systems, 2006.
- ^ F. Chung. Spectral Graph Theory, Providence, RI: Amer. Math. Soc., 1997.[1]
- ^ Tiago Pereira, Stability of Synchronized Motion in Complex Networks, arXiv:1112.2297v1, 2011.
- ^ D. Watts, Six Degrees: The Science of a Connected Age, Vintage, 2003.
- ^ M. Fiedler. "Algebraic connectivity of Graphs", Czechoslovak Mathematical Journal 23(98) (1973), 298–305.
- ^ M. Fiedler. "Laplacian of graphs and algebraic connectivity", Combinatorics and Graph Theory (Warsaw, 1987), Banach Center Publications 25(1) (1989), 57–70.