樹圖的費德勒向量

$\newcommand{\mul}{\operatorname{mult}}$

我們先前看到了圖的第 $2$ 位拉普拉斯特徵向量，可以為圖分割提出一個合理的建議，同時也保證分割出來的區塊一定程度地連通。令 $G$ 為一個圖、$A$ 是 $\mathcal{S}_L(G)$ 或 $\ddot{\mathcal{S}}(G)$ 中的矩陣、$\lambda_2$ 為 $A$ 第 $2$ 小的特徵值，則我們稱 $A$ 上對應到 $\lambda_2$ 的特徵向量為 費德勒向量（Fiedler vector）。當 $\lambda_2$ 的重數為 $1$ 時，所有費德勒向量都在同一個方向上；當其重數大於 $1$ 時，則費德勒向量有不同方向可以選擇。

費德勒於 1975 年在 Czechoslovak Mathematical Journal 上連發了兩篇經典著作，其第二篇文章著重在樹圖的費德勒向量¹。以下定理著重在無賦權的拉普拉斯矩陣，以展示費德勒文章中的精神，但此定理對於賦權拉普拉斯矩陣也是對的。

定理 1（費德勒 1975）

令 $T$ 為一樹圖、$L$ 為其拉普拉斯矩陣、且 $\by$ 為其一費德勒向量。則以下兩種狀況恰有一種會發生。

$\by$ 中有至少一項為零。此時恰有一個點 $i$ 其存在鄰居 $j$ 使得 $(\by)_i = 0$ 且 $(\by)_j \neq 0$。除此之外，對於任何一條 $T$ 上從 $i$ 出發的路徑來說，$\by$ 各項的值不是嚴格遞增、嚴格遞減、就是均為零。我們稱 $\{i\}$ 為 $T$ 的 特徵集（characteristic set）。
$\by$ 各項均非零。此時恰有一條邊 $\{i,j\}$ 使得 $(\by)_i(\by)_j < 0$。不失一般性，令 $(\by)_i < 0 < (\by)_j$。除此之外，對於任何一條 $T$ 上從 $i$ 出發不經過 $j$ 的路徑來說，$\by$ 各項的值嚴格遞減；對於任何一條 $T$ 上從 $j$ 出發不經過 $i$ 的路徑來說，$\by$ 各項的值嚴格遞增。我們稱 $\{i,j\}$ 為 $T$ 的 特徵集（characteristic set）。

最後，特徵集的位置不會因為 $\by$ 的選取而有所不同。

回顧樹圖的特徵向量中所用的正點、負點、零點、邊界點、變號邊、以及同號邊等術語，此定理說明第一個情形下會有唯一的邊界點、而第二個情形下會有唯一的變號邊。

引理 2（費德勒 1975）

令 $G$ 為一圖且 $A\in\ddot{\mathcal{S}}(G)$、並令 $\bx$ 為 $A$ 的一個特徵向量。對於 $G$、$\bx$ 來說，任一邊界點的鄰居中，一定包含一個正點及一個負點。

由於邊界點一定有一個正點及一個負點為鄰居，也可視為是由負轉正的變號過程，因此直觀上來說，定理 1 第一個強調的重點是費德勒向量僅有一次「變號」。定理 1 的第二個重點是費德勒向量的單調性：樹圖的費德勒向量以特徵集為中心，所有向外的路徑上的 $\by$ 值只能遞增、遞減、或全為零。以下我們根據這兩點詳加說明。

僅有一次「變號」

由佩弗定理可知 $L$ 的最小的特徵值為單根，而且可選到其對應的特徵向量 $\bv_1$ 為逐項為正。令 $\lambda_2$ 為 $L$ 的第 $2$ 小的特徵向量，則 $n_-(L - \lambda_2 I) = 1$。另一方面，$\inp{\by}{\bv_1} = 0$ 告訴我們 $\by$ 上各項有正有負。將樹圖的特徵向量定理 4 套用在 $L$ 及 $\lambda_2$ 上，可知 $a_- + p \leq 1$。若 $\by$ 上有零，則必有邊界點，此時 $a_- = 0$ 且 $p = 1$；若 $\by$ 逐項非零，因有正有負，必有變號邊，此時 $a_- = 1$ 且 $p = 0$。因此費德勒向量在兩種情況下，都僅有一次「變號」。

單調性

在說明單調性之前，我們首先介紹一個通用的部份和等式。

引理 3（費德勒 1975）

令 $G$ 為一圖、$A$ 為其拉普拉斯矩陣，並令 $S\subseteq V(G)$、$\bx$ 為一可與 $A$ 相乘的向量，則

\[ \sum_{s\in S}(A\bx)_s = \sum_{s\in S,\ t\notin S}(\bx)_s - (\bx)_t. \]

證明

第一，我們觀察對任一點 $s$ 經過直接計算都有

\[ (A\bx)_s = \sum_{t: t\sim s} (\bx)_s - (\bx)_t. \]

接著我們把這個等式對 $S$ 中的所有 $s$ 加起來得到

\[ \begin{aligned} \sum_{s\in S}(A\bx)_s &= \sum_{s\in S}\sum_{t: t\sim s} (\bx)_s - (\bx)_t. \end{aligned} \]

我們發覺右式中待相加的各項都是跟邊有關，對於一條邊 $\{u,v\}$ 來說，

若 $u,v\in S$，則 $(\bx)_u - (\bx)_v$ 及 $(\bx)_v - (\bx)_u$ 各加了一次，所以互相扺消。
若 $u,v\notin S$，則完全沒加到。
若 $u\in S$ 且 $v\notin S$，則加到 $(\bx)_u - (\bx)_v$。

綜合以上可能性，最後被加到的都是 $E(S, V\setminus S)$ 中的邊，因此證明此部份和等式。$\blacksquare$

回到單調性的討論上，引理 3 可以套用在樹圖的費德勒向量上。當 $T$ 是樹圖而 $\{u,v\}$ 是 $T$ 的一條邊時，$T$ 扣掉這條邊會得到兩個區塊，一個包含 $u$、一個包含 $v$。令 $S$ 為包含 $u$ 的區塊，則有

\[ \sum_{s\in S}(L\by)_s = (\by)_u - (\by)_v, \]

因而得到邊上的差值。由於 $L\by = \lambda_2\by$，我們還知道

\[ \lambda_2\sum_{s\in S}(\by)_s = (\by)_u - (\by)_v. \]

此時若 $S$ 內均是正點，則可知 $(\by)_u > (\by)_v$，若 $S$ 內均是負點，則 $(\by)_u < (\by)_v$。透過選取適當的邊 $\{u,v\}$，並搭配費德勒向量僅有一次「變號」的性質，則可得到遞增、遞減、或全為零的結果。

一致性

費德勒的定理最後述說特徵集的位置不會因為 $\by$ 的選取而有所不同。僅僅這句話說明了以下的可能性都不會發生：

有沒有可能有的費德勒向量上有零、有的完全沒有？
有沒有可能兩個費德勒向量給出來的特徵集是不同的？

若 $\lambda_2$ 的重數為 $1$，自然每個費德勒向量都是平行的，其上零和非零的結構都是一樣的，而邊界點或變號邊僅擇一發生，發生時位置也相同，所以具有一致性。

當重數為 $2$ 以上時，則利用高斯消去法，則必然存在一個費德勒向量包含零項，所以這個問題看似有可能發生。然而如果任一個費德勒向量包含零項，則必然存在一邊界點 $i$，根據樹圖的特徵向量定理 3 這個點也是派特點，而派特點也告訴我們 $i$ 對於任一費德勒向量都是零點，因此第一個問題不會發生。實際上，若我們把樹圖的特徵向量定理 3 套用在 $T$、$L$、$\lambda_2$、以及 $\by$ 上，並依其證明觀察

\[ (L - \lambda_2 I)\by = \begin{bmatrix} ? & \bb_1\trans & \cdots & \bb_c\trans \\ \bb_1 & A_1 & ~ & ~ \\ \vdots & ~ & \ddots & ~ \\ \bb_c & ~ & ~ & A_c \end{bmatrix} \begin{bmatrix} 0 \\ \by_1 \\ \vdots \\ \by_c \end{bmatrix} = \bzero, \]

會發現派特點加上柯西交錯定理會強迫 $n_-(A_1) = \cdots = n_-(A_c) = 0$。對每個 $k = 1,\ldots, c$ 來說，根據佩弗定理，若 $A_k$ 不可逆，則 $\ker(A_k)$ 維度為 $1$ 且包含一個逐項為正的向量。令 $B$ 為 $L - \lambda_2 I$ 去掉第 $i$ 行第 $i$ 列的子矩陣，則 $\nul(B)$ 恰等於 $A_1, \ldots, A_c$ 之中不可逆矩陣的個數。取 $\ker(B)$ 中的任一向量，在其第 $i$ 位補一個 $0$，若此向量左乘 $(\bb_1\trans, \ldots, \bb_c\trans)$ 為零，則這個補 $0$ 後的向量會落在 $\ker(L - \lambda_2 I)$ 中；實際上，所有 $L$ 的費德勒向量都可以用這種方法做出來，這表示 $i$ 在每一個費德勒向量上都是邊界點，因此第二個問題也不會發生。

費德勒所提出特徵集的可視為是樹圖的中心，若一個樹圖的特徵集大小為 $1$，則我們稱之為 第一類樹圖（Type I tree）；若一個樹圖的特徵集大小為 $2$，則被稱為 第二類樹圖（Type II tree）。到目前為止，除了直接計算出費德勒向量以外，並沒有有效的方法來判斷一個樹圖是第一類還是第二類。

另一方面，費德勒向量在樹圖上有許多良好性質，但文獻上對其它圖類的費德勒向量似乎就較少著墨，比如說圈圖的費德勒向量至今沒有較完整的描述。

總結來說，費德勒奠基了拉普拉斯矩陣的許多優美結果，同時也開啟了一系列研究的可能性。

想想以下問題：

利用樹圖的特徵向量文末的程式碼觀察樹圖的費德勒向量。
計算 $P_2$ 和 $P_3$ 的特徵集，它們分別屬於哪一類的樹圖。
計算 $K_{1,4}$ 的所有費德勒向量，描述派特點對特徵空間的影響。
證明引理 2。[提示：令 $\lambda$ 為對應的特徵值，$i$ 為一邊界點。觀察等式 $(A - \lambda I)\bx = \bzero$ 的第 $i$ 列。]
說明當一個向量空間的維度大於等於 $2$ 時，一定存在一個向量包含零項。[提示：高斯消去法。]
令 $T$ 為一樹圖而 $A\in\mathcal{S}_L(T)$，探討 $A$ 的費德勒向量的性質。
令 $T$ 為一樹圖而 $A\in\ddot{\mathcal{S}}(T)$，探討 $A$ 的費德勒向量的性質。