代數連通度

圖${\displaystyle G}$的代數連通度（algebraic connectivity）是${\displaystyle G}$的拉普拉斯矩陣的第二小的特徵值（重特徵值要重複計算）。^[1]這個特徵值大於0若且唯若${\displaystyle G}$是連通圖。這是一個簡單的推論，因為拉普拉斯矩陣的特徵值0的重數就是圖的連通分支的個數。這個值的大小反映了整個圖的連通程度。它可以用於分析網絡的穩定性與可同步性。

一個例圖，6頂點，直徑3，連通度1，代數連通度0.722。

性質

圖${\displaystyle G}$的代數連通度大於0若且唯若${\displaystyle G}$是連通圖。而且，圖的代數連通度的值不大於（頂點）連通度。^[2]設一個連通圖有${\displaystyle n}$個頂點且直徑為${\displaystyle D}$，則代數連通度的一個下界是${\displaystyle {\frac {1}{nD}}}$，^[3]而且根據Brendan McKay的一個結果這個下界可以改進為${\displaystyle {\frac {4}{nD}}}$。^[4]對於上圖中的例子，${\displaystyle 4/18=0.222\leq 0.722\leq 1}$。

不像傳統的連通度，代數連通度除了與頂點的連接方式有關以外，還與頂點的個數有關。對隨機圖，代數連通度隨頂點數增大而減小，隨平均度的增大而增大。^[5]

代數連通度的具體定義依賴於所使用的拉普拉斯矩陣的類型。金芳蓉使用一種重新標度的拉普拉斯矩陣，消除了對頂點數的依賴，所以上下界有所不同。^[6]

拉普拉斯矩陣自然地出現在網絡上的同步模型中，例如藏本模型，因而代數連通度標誌了網絡達到同步的容易程度。^[7]也可以使用其他度量，例如平均距離（特徵路徑長度），^[8]實際上代數連通度與平均距離（的倒數）密切相關。^[4]

• 
  截角二十面體，也是巴克明斯特富勒烯的結構圖，連通度為3，而代數連通度為0.243。

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

另見

• 連通圖