如果一個圖代表的是電腦彼此連結的網路，那這個圖的連通程度，將決定這個電腦網路的強健程度，因此評估一個圖的連通程度是圖論中的重要議題之一。如何評估圖的連通程度呢？考慮一個樹圖，我們會發現拿掉任何一個不是葉子的點，都會讓圖斷成兩個以上的連通區塊；直觀來說，我們會覺得樹圖儘管是連通圖，但連通程度是不是太好。若考慮 \(4\) 個點以上的圈圖 \(C_n\)，則至少要拿掉 \(2\) 個點，才能讓圖斷成兩塊以上；直觀上來說，圈圖的連通程度有稍微好一些。依照這個脈絡，我們可以將一個圖 \(G\) 的 連通度（connectivity） 定義為，若要把圖斷成兩塊以上，最少要拿掉的點數，記作 \(\kappa(G)\)。以上述例子來說，我們有樹圖 \(T\) 的連通度是 \(\kappa(T) = 1\)，而圈圖 \(C_n\) 的連通度是 \(\kappa(C_n) = 2\)。但這樣的定義對於完全圖 \(K_n\) 來說是不明確的，因為完全圖不管拿掉幾個點，都不可能斷成兩塊以上，因此有的書會直接定義 \(\kappa(K_n) = n - 1\)，或是只將連通度定義在非完全圖之上；這邊我們選擇使用後者。另外，我們也可以問若要把圖斷成兩塊以上，最少要拿掉的邊數，這個量被稱為圖的 邊連通度（edge connectivity）。為了與邊連通度區隔，有些時候會改把連通度稱為 點連通度（vertex connectivity），但在這篇文章中我們所說的連通度指的就是點連通度。

費德勒在 1973 年提出了代數連通度的想法，利用拉普拉斯矩陣特徵值，來評估圖的連通度。令 \(G\) 為一個圖，\(L\) 為其拉普拉斯矩陣，將其特徵向量由小排到大為 \(\lambda_1 \leq \cdots \leq \lambda_n\)，則 \(\lambda_2\) 被稱為 \(G\) 的 代數連通度（algebraic connectivity），記作 \(\lambda_2(G)\)。回顧 拉普拉斯矩陣性質 1，我們知道 \(\nul(L)\) 恰為 \(G\) 的連通區塊個數，所以 \(\lambda_2 = 0\) 等價於 \(G\) 有 \(2\) 個以上的連通區塊，也就是 \(G\) 不連通。這樣的性質說明了代數連通度與連通度的基本關聯，但費德勒更進一步證明了 \(\lambda_2(G) \leq \kappa(G)\)。在證明以前，我們先回顧一個代數連通度的基本性質。

性質 1

令 \(G\) 為一個圖，\(L\) 為其拉普拉斯矩陣。則

\[ \lambda_2(G) = \min_{\substack{\by\neq\bzero\\\by\perp\bone}} \frac{\by\trans L\by}{\by\trans\by}. \]

由於拉普拉斯矩陣總是有 \(\lambda_1 = 0\) 為其最小的特徵值，且 \(\bone\) 為一對應的特徵向量，將瑞利商定理套用在 \(L\) 和 \(\lambda_2\) 上即可得上述的性質。而這樣的性質也告訴我們，只要找到一個非零的 \(\by\) 且滿足 \(\by\perp\bone\)，則它的瑞利商將會是 \(\lambda_2(G)\) 的一個上界。接下來我們就來看看選取不同的 \(\by\) 可以得到什麼樣不同的上界。

定理 2（費德勒 1973）

任意非完全圖的圖 \(G\) 都滿足 \(\lambda_2(G) \leq \kappa(G)\)。

證明

令 \(S\subseteq V(G)\) 使得 \(G - S\) 會斷成兩塊以上且 \(\vert{}S\vert{} = \kappa(G)\)。如此一來，\(G - S\) 的點集可以分割為 \(A\) 和 \(B\) 兩塊，使得 \(E(A,B) = \emptyset\)。我們定義一個向量 \(\by\) 如下：

  1. 如果 \(i\in S\)，則 \((\by)_i = 0\)。
  2. 如果 \(i\in A\)，則 \((\by)_i = \frac{1}{\vert{}A\vert{}}\)。
  3. 如果 \(i\in B\)，則 \((\by)_i = -\frac{1}{\vert{}B\vert{}}\)。

直接計算可得 \(\by\perp\bone\)，因此根據性質 1 我們有

\[ \lambda_2(G) \leq \frac{\by\trans L\by}{\by\trans\by} = \frac{\sum_{\{i,j\}\in E(G)}((\by)_i - (\by)_j)^2}{\by\trans\by}, \]

其中 \(L\) 為 \(G\) 的拉普拉斯矩陣。我們可以觀察 \(((\by)_i - (\by)_j)^2\) 當 \(i,j\) 同時落在 \(S\)、同時落在 \(A\)、或同時落在 \(B\) 的時候為零。又加上 \(E(A,B) = \emptyset\)，我們只要考慮以下情況：

  1. 如果 \(\{i,j\}\in E(S,A)\)，則 \(((\by)_i - (\by)_j)^2 = \frac{1}{\vert{}A\vert{}^2}\)。
  2. 如果 \(\{i,j\}\in E(S,B)\)，則 \(((\by)_i - (\by)_j)^2 = \frac{1}{\vert{}B\vert{}^2}\)。

合起來看，我們知道

\[ \by\trans L\by \leq \frac{\vert{}E(S,A)\vert{}}{\vert{}A\vert{}^2} + \frac{\vert{}E(S,B)\vert{}}{\vert{}B\vert{}^2} \leq \vert{}S\vert{}\left(\frac{1}{\vert{}A\vert{}} + \frac{1}{\vert{}B\vert{}}\right). \]

這邊第二個不等式是由於 \(\vert{}E(S,A)\vert{} \leq \vert{}S\vert{}\vert{}A\vert{}\) 及 \(\vert{}E(S,B)\vert{} \leq \vert{}S\vert{}\vert{}B\vert{}\)。

另一方面，我們計算 \(\by\trans\by = \frac{1}{\vert{}A\vert{}} + \frac{1}{\vert{}B\vert{}}\)。總結所有計算，我們得到 \(\lambda_2(G) \leq \vert{}S\vert{} = \kappa(G)\)。\(\blacksquare\)

除了連通度以外，奇格常數也是另一種判斷圖連通程度的辦法。令 \(G\) 為一個圖，考慮所有可能的分割 \(A\dunion B = V(G)\)，圖 \(G\) 的 奇格常數（Cheeger constant） 定義為

\[ h(G) = \min_{A,B} \frac{\vert{}E(A,B)\vert{}}{\min\{\vert{}A\vert{},\vert{}B\vert{}\}}; \]

直觀來說，奇格常數想要問最少要拿掉多少邊才能把 \(G\) 斷成兩塊以上，但同時又希望斷出來的兩塊大小不要差太多，所以除掉較小的那塊的大小，來懲罰太過極端的分割1。圖的代數連通度也可以用來控制奇格常數，而證明的手法也是找適當的 \(\by\) 來套用引理 1。

定理 3（參考莫哈爾 1989）

令 \(G\) 為一圖。對任意分割 \(A\dunion B = V(G)\)，都有

\[ \lambda_2(G) \leq \vert{}E(A,B)\vert{}\left(\frac{1}{\vert{}A\vert{}} + \frac{1}{\vert{}B\vert{}}\right). \]

由此也可推得到 \(\lambda_2(G) \leq 2h(G)\)。

證明

定義 \(\by\) 如下：

  1. 若 \(i\in A\)，則 \((\by)_i = \frac{1}{\vert{}A\vert{}}\)。
  2. 若 \(i\in B\)，則 \((\by)_i = -\frac{1}{\vert{}B\vert{}}\)。

如此一來，\(\by\perp\bone\)。接下來我們令 \(L\) 為 \(G\) 的拉普拉普矩陣並套用引理 1，透過直接計算可得

\[ \by\trans L \by \leq \vert{}E(A,B)\vert{}\left(\frac{1}{\vert{}A\vert{}} + \frac{1}{\vert{}B\vert{}}\right)^2 \]

以及 \(\by\trans\by = \frac{1}{\vert{}A\vert{}} + \frac{1}{\vert{}B\vert{}}\)。結合兩者，即可得定理中的第一個不等式。

有了第一個不等式，我們可以令 \(A\dunion B = V(G)\) 為得到奇格常數的最佳分割；且不失一般性，可假設 \(\vert{}A\vert{} \leq \vert{}B\vert{}\)。如此有 \(h(G) = \frac{\vert{}E(A,B)\vert{}}{\vert{}A\vert{}}\) 的關係。套用在不等式中則有

\[ \lambda_2(G) \leq \vert{}E(A,B)\vert{}\left(\frac{1}{\vert{}A\vert{}} + \frac{1}{\vert{}B\vert{}}\right) = h(G)\left(1 + \frac{\vert{}A\vert{}}{\vert{}B\vert{}}\right) \leq 2h(G). \]

這邊最後一個不等式是基於 \(\vert{}A\vert{} \leq \vert{}B\vert{}\)。\(\blacksquare\)

本篇文章介紹了代數連通度以及它與連通度、奇格常數的關係，這三個量都可以幫助我們了解圖的連通程度。另一方面，費德勒更進一步提出絕對代數連通度的觀念；給定一個 \(m\) 條邊的圖 \(G\)，考慮所有符合 \(\tr(A) = 2m\) 的賦權拉普拉斯矩陣 \(A\) 的第 \(2\) 小的特徵值，則圖 \(G\) 的 絕對代數連通度（absolute algebraic connectivity） 為這些值的最大值。絕對代數連通度在後續的文獻裡，被證明可以給出一種等邊長的圖嵌入。然而有效地計算絕對代數連通度、以及它的特徵值重數，仍是一個待解的問題。

想想以下問題：

  1. 任選一個圖，計算它的點連通度、邊連通度、奇格常數、以及代數連通度。
  2. 探討圖的點連通度及邊連通度的關係，有沒有可能一個總是比另一個大，或是兩者不可比較？
  3. 證明圖的邊連通度也是 \(\lambda_2(G)\) 的上界。

延伸閱讀：

  1. F. R. K. Chung. Spectral Graph Theory. American Mathematical Society, 1997.
  2. M. Fiedler. Algebraic connectivity of graphs. Czechoslovak Math. J., 23:298–305, 1973.
  3. M. Fiedler. Absolute algebraic connectivity of trees. Linear Multilinear Algebra, 26:85–106, 1990.
  4. B. Mohar. Isoperimetric numbers of graphs. J. Combin. Theory Ser. A, 47:274–291, 1989.
  5. B. Osting. Extremal Graph Realizations and Graph Laplacian Eigenvalues. SIAM J. Discrete Math., 37:1630–1644, 2023.

  1. 在考慮一個點集 \(A\) 的區塊大小時，除了使用點數 \(\vert{}A\vert{}\) 以外，也可以改用 \(\operatorname{Vol}(A) = \sum_{i\in A}\deg(i)\)。有不同版本的奇格常數，它的分子是除以 \(\min\{\operatorname{Vol}(A), \operatorname{Vol}(B)\}\)；這個版本的奇格常數和 標準化拉普拉斯矩陣（normalized Laplacian matrix） 有密切關係，這部份可以參考金芳蓉教授的著作 Spectral Graph Theory。 ↩