代數連通度
![](http://upload.wikimedia.org/wikipedia/commons/thumb/5/5b/6n-graf.svg/220px-6n-graf.svg.png)
圖的代數連通度(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.