克希荷夫矩陣─樹定理

本文的閱讀等級:高級

G(V,E) 為一無向圖,其中 V 是頂點 (vertex) 集合,E 是邊 (edge) 集合,頂點數 n=\vert V\vert 稱為圖 G 的階 (order)。每一條無向邊 (以下簡稱邊) 有兩個頂點為其端點 (endpoint)。因此,一邊 e\in E 定義為 V 中兩頂點 uv 組成的集合或無序對,記為 e=\{u,v\}=\{v,u\},我們稱頂點 uv 鄰接 (adjacent),並稱頂點 uv 與邊 e 有關聯 (incident)。以下考慮簡單圖,意思是不存在自環 (self-loop),即一邊的兩端點為同一頂點,並且不存在重邊 (multiedge),即任意兩相異頂點至多僅存在一連接邊。若一圖的任兩頂點之間存在一序列鄰接頂點構成的連通路徑 (path),則稱為連通圖 (connected graph)。若 V'\subseteq VE'\subseteq E,我們說 G(V',E') 是圖 G(V,E) 的一個子圖 (subgraph)。圖 G=(V,E) 的一個連通元件是指子圖 G(V',E') 為一連通圖,但任意 u\in V'v\in V\setminus V' 之間不存在連通路徑。如果 G(V,E) 是一個不含迴圈 (cycle) 的連通圖,則稱為一棵樹 (tree)。換一個說法,G(V,E) 是一棵樹的一個等價條件為 G 是連通圖且 \vert E\vert=\vert V\vert-1。給定一連通圖 G(V,E),最小生成樹 (minimal spanning tree) 是一個連通子圖 G(V,S)\vert S\vert=\vert V\vert-1。若 G 不是連通圖,則不存在最小生成樹。標記頂點 (labeled vertex) 是指每一頂點都有一個識別記號 (例如 v_ii),具有標記頂點的圖稱為標記圖。本文討論一個經典的圖論問題:給定一簡單連通標記圖 G(V,E),共有多少棵不同的最小生成樹?這個問題的答案稱為克希荷夫矩陣─樹定理 (Kirchhoff’s matrix-tree theorem)。下面介紹一個優美的線性代數證明,預備知識包括量空間分析、行列式、特徵值與特徵向量。

 
對應 n 階圖 G=(V,E)V=\{v_1,\ldots,v_n\},鄰接矩陣 (adjacency matrix) A=[a_{ij}] 為一 n\times n 階矩陣,定義如下:a_{ij}=1\{v_i,v_j\}\in E,否則 a_{ij}=0 (見“線性代數在圖論的應用 (一):鄰接矩陣”)。因為 G 是簡單圖,每一 a_{ii}=0。明顯地,a_{ij}=a_{ji}A 是一對稱矩陣。對於頂點 v_i,分支度 (度數,degree) d_i 是與 v_i 有關聯的邊數,或者說與 v_i 鄰接的頂點數,即鄰接矩陣 A 的第 i 列 (row) 和,d_i=\sum_{j=1}^na_{ij}。對應圖 G(V,E)L=D-A 稱為拉普拉斯矩陣 (Laplacian),其中 D=\text{diag}(d_1,\ldots,d_n) 稱為分支度矩陣。因為 AD 是對稱矩陣,L 是對稱矩陣。拉普拉斯矩陣 L=[l_{ij}] 的主對角元 l_{ii} 等於頂點 i 的分支度 d_i,非主對角元 l_{ij}=-1 若頂點 ij 鄰接,否則 l_{ij}=0。見下例:G=(V,E),其中 V=\{1,2,3,4\}E=\{\{1,2\},\{1,3\},\{1,4\},\{2,4\},\{3,4\}\}

4-order graph

對應此 4 階圖的鄰接矩陣 A、分支度矩陣 D 和拉普拉斯矩陣 L 分別是

\displaystyle  A=\begin{bmatrix}  0&1&1&1\\  1&0&0&1\\  1&0&0&1\\  1&1&1&0  \end{bmatrix},~~D=\begin{bmatrix}  3&0&0&0\\  0&2&0&0\\  0&0&2&0\\  0&0&0&3  \end{bmatrix},~~L=\left[\!\!\begin{array}{rrrr}  3&-1&-1&-1\\  -1&2&0&-1\\  -1&0&2&-1\\  -1&-1&-1&3  \end{array}\!\!\right]

 
拉普拉斯矩陣 L 具有下列性質 (見“線性代數在圖論的應用 (三):拉普拉斯矩陣”):L 是半正定矩陣 (特徵值必不為負數),最小的特徵值為 0,對應特徵向量 \mathbf{e}=(1,\ldots,1)^T (由 L 的每一列和皆為零即可確認),且特徵值 0 的重數等於 G 的連通元件數。因為 L 是實對稱矩陣,故可正交對角化,推論 \hbox{rank}L 等於非零特徵值數 (見“幾何重數不大於代數重數的證明”)。因此,若 G 為一 n 階連通圖,則 L 的特徵值 0 的重數為 1,即有 \hbox{rank}L=n-1。若 G 不是連通圖,則 L 的特徵值 0 的重數大於 1,即有 \hbox{rank}L<n-1。我們將這個結論寫入定理一。

定理一:對於一 n 階圖 G,沿用前述記號,若 \hbox{rank}L=n-1,則 G 是連通圖;若 \hbox{rank}L<n-1,則 G 不是連通圖。

 
給定一無向簡單圖 G(V,E),對於每一 e_i=\{v_j,v_k\}\in E,任意指定 v_j 為邊 e_i 的起始頂點,v_k 為邊 e_i 的終止頂點。設 m=\vert E\vertn=\vert V\vert。我們定義圖 Gm\times n 階有向關聯矩陣 (oriented incidence matrix) B=[b_{ij}],其中 b_{ij}=1v_j 是邊 e_i 的起始頂點,b_{ij}=-1v_j 是邊 e_i 的終止頂點,b_{ij}=0v_j 不是邊 e_i 的一個端點 (見“線性代數在圖論的應用 (二):關聯矩陣”)。上例 4 階圖 G 的一個有向關聯矩陣為

\displaystyle  B=\left[\!\!\begin{array}{rrrr}  1&-1&0&0\\  1&0&-1&0\\  1&0&0&-1\\  0&1&0&-1\\  0&0&1&-1  \end{array}\!\!\right]

 
定理二:對於一 n 階圖 G

L=B^TB=D-A

有向關聯矩陣 B 的每一列有兩個非零元,1-1B 的第 j 行 (column) 的非零元的列指標對應與頂點 v_j 有關聯的邊。因為 B^TB(i,j) 元,記為 (B^TB)_{ij},是 B 的第 i 行與第 j 行的內積,故 (B^TB)_{ii} 等於頂點 v_i 的分支度 d_i,且當 i\neq j(B^TB)_{ij}=-1\{v_i,v_j\}\in E,否則 (B^TB)_{ij}=0。所以,B^TB=D-A=L。這個結果與下述事實相符:任一 n\times n 階實對稱半正定矩陣 L 可分解為 L=B^TB,其中 Bm\times n 階實矩陣,\hbox{rank}B=\hbox{rank}L (見“半正定矩陣的判別方法”)。

 
我們知道 n 階圖 G(V,E) 的最小生成樹 G(V,S) 必須滿足兩個條件:G(V,S) 是一個連通圖且 \vert S\vert=n-1。在不造成混淆的情況下,以 \left\langle S\right\rangle 代表子圖 G(V,S),並約定 \vert S\vert=n-1。因此,\left\langle S\right\rangle 是一最小生成樹的充要條件是 \left\langle S\right\rangle 是一連通圖。令 L_S=B_S^TB_S 為子圖 \left\langle S\right\rangle 的拉普拉斯矩陣,其中 B_S(n-1)\times n 階有向關聯矩陣。定理一與定理二表明子圖 \left\langle S\right\rangleG 的一最小生成樹等價於 \hbox{rank}B_S=\hbox{rank}L_S=n-1。考慮子圖 \left\langle S\right\rangleS=\{\{1,2\},\{1,3\},\{1,4\}\},如下所示:

4-order min spanning tree

對應 \left\langle S\right\rangle3\times 4 階有向關聯矩陣為

\displaystyle  B_S=\left[\!\!\begin{array}{rrrr}  1&-1&0&0\\  1&0&-1&0\\  1&0&0&-1  \end{array}\!\!\right]

不難確認 \hbox{rank}B_S=3,故 \left\langle S\right\rangle 是一最小生成樹。再看 \left\langle S'\right\rangleS'=\{\{1,2\},\{1,4\},\{2,4\}\},如下:

4-order subgraph

對應 \left\langle S'\right\rangle 的有向關聯矩陣為

\displaystyle  B_{S'}=\left[\!\!\begin{array}{rrrr}  1&-1&0&0\\  1&0&0&-1\\  0&1&0&-1  \end{array}\!\!\right]

其中第 2 列等於第 1 列與第 3 列的和,可知 \hbox{rank}B_{S'}=2<3,故 \left\langle S'\right\rangle 不是最小生成樹。

 
計算 B_S 的矩陣秩固然得以判定 \left\langle S\right\rangle 是否為一最小生成樹,但我們冀望更簡單的算法。因為 B_S 的每一列有兩個非零元,1-1n 維常數向量 \mathbf{e}=(1,\ldots,1)^T 滿足 B_S\mathbf{e}=\mathbf{0},或表示為 \mathbf{b}_1+\cdots+\mathbf{b}_n=\mathbf{0},其中 \mathbf{b}_j\in\mathbb{R}^{n-1} 代表 B_S 的第 j 個行向量。對於任一 1\le j\le n\mathbf{b}_j 可寫成其餘 n-1 個行向量的線性組合,即 \mathbf{b}_j\in\hbox{span}\{\mathbf{b}_1,\ldots,\mathbf{b}_{j-1},\mathbf{b}_{j+1},\ldots,\mathbf{b}_n\},說明 B_S 的行空間為 C(B_S)=\hbox{span}\{\mathbf{b}_1,\ldots,\mathbf{b}_{j-1},\mathbf{b}_{j+1},\ldots,\mathbf{b}_n\}。若 \hbox{rank}B_S=n-1,則 B_S 的任何 n-1 個行向量組成一線性獨立集。反之,若 \hbox{rank}B_S<n-1,則 B_S 的任何 n-1 個行向量組成一線性相關集。我們可以從 (n-1)\times n 階矩陣 B_S 隨意選取 n-1 個行向量構造一個 (n-1) 階方陣,記為 \tilde{B}_S。若 \det \tilde{B}_S\neq 0,則 \left\langle S\right\rangle 是最小生成樹;若 \det \tilde{B}_S=0,則 \left\langle S\right\rangle 不是最小生成樹。還有一個小問題:如果 \left\langle S\right\rangle 是最小生成樹,\det\tilde{B}_S 的數值是多少?此數值是否隨著選取不同的 n-1 個行向量而改變?以前述最小生成樹 \left\langle S\right\rangle 為例,使用基本列運算的取代、交換,並僅允許乘入 1-1 至各列,可得梯形矩陣:

\displaystyle\begin{aligned}  B_S=\left[\!\!\begin{array}{rrrr}  1&-1&0&0\\  1&0&-1&0\\  1&0&0&-1  \end{array}\!\!\right]&\sim  \left[\!\!\begin{array}{rrrr}  1&-1&0&0\\  0&1&-1&0\\  1&0&0&-1  \end{array}\!\!\right]\\  &\sim  \left[\!\!\begin{array}{rrrr}  1&-1&0&0\\  0&1&-1&0\\  0&1&0&-1  \end{array}\!\!\right]\\  &\sim\left[\!\!\begin{array}{rrrr}  1&-1&0&0\\  0&1&-1&0\\  0&0&1&-1  \end{array}\!\!\right]=B_T  \end{aligned}

上面 \sim 表示列等價 (row equivalent)。基本列運算將 B_S 轉換至梯形矩陣 B_T 的實際作為是移動 \left\langle S\right\rangle 的邊使之成為一道路圖 (path graph) G(V,T),記為 \left\langle T\right\rangle,其中 \{v_i,v_{i+1}\}\in T1\le i\le n-1。基本列運算不改變矩陣秩,故 \hbox{rank}B_T=\hbox{rank}B_S,可知 \left\langle T\right\rangle 是一個最小生成樹。不僅如此,我們使用限制乘數為 \pm 1 的基本列運算不改變 \det \tilde{B}_S 的大小,僅可能變更 \det \tilde{B}_S 的正負號,也就是說,\vert\det\tilde{B}_T\vert=\vert\det\tilde{B}_S\vert。明顯地,刪去梯形矩陣 B_T 的任何一個行向量後得到的方陣 \tilde{B}_T 是三角矩陣,且主對角元為 1-1。因此,不論如何選取 B_Sn-1 個行向量,\vert\det\tilde{B}_S\vert=\vert\det\tilde{B}_T\vert=1

定理三:對於一 n 階圖 G,子圖 \left\langle S\right\rangle 滿足 \vert S\vert=n-1\tilde{B}_SB_S 的任何一個 (n-1) 階子陣。若 \vert\det\tilde{B}_S\vert=1,則 \left\langle S\right\rangle 是一最小生成樹;若 \det\tilde{B}_S=0,則 \left\langle S\right\rangle 不是最小生成樹。

 
回到本文的問題,簡單連通標記圖 G(V,E) 有多少個不同的最小生成樹?令 t(G) 表示圖 G 的最小生成樹總數。令 J 表示每一元為 1 的常數矩陣,也就是說 J=\mathbf{e}\mathbf{e}^T,其中 \mathbf{e}=(1,\ldots,1)^T。定理四說拉普拉斯矩陣 L 的伴隨矩陣 (adjugate,classical adjoint) \hbox{adj}\,L 是一常數矩陣,每一元皆為 t(G)

 
定理四:對於一標記圖 G

\hbox{adj}\,L=t(G)J

下面是一些有用的伴隨矩陣性質 (見“伴隨矩陣”):令 PQn\times n 階矩陣。

  1. P(\hbox{adj}\,P)=(\det P)I
  2. \hbox{adj}\,(PQ)=(\hbox{adj}\,P)(\hbox{adj}\,Q)
  3. \hbox{rank}P=n-1,則 \hbox{rank}(\hbox{adj}\,P)=1
  4. \hbox{rank}P<n-1,則 \hbox{rank}(\hbox{adj}\,P)=0
  5. \hbox{adj}\,(kP)=k^{n-1}\hbox{adj}\,P
  6. \hbox{adj}\,(P^T)=(\hbox{adj}\,P)^T

我們先證明 \hbox{adj}\,L=cJ,其中 c 是實數。設 G 是一 n 階簡單圖。若 G 是非連通圖,則 \hbox{rank}L<n-1,因此 \hbox{rank}(\hbox{adj}\,L)=0,即 \hbox{adj}\,L=0 (c=0)。若 G 是連通圖,則 \hbox{rank}L=n-1。因為

L(\hbox{adj}\,L)=(\det L)I=0

可知 \hbox{adj}\,L 的每一行屬於 L 的零空間 N(L)。但 \dim N(L)=n-\hbox{rank}L=1L\mathbf{e}=\mathbf{0},推得 N(L)=\hbox{span}\{\mathbf{e}\}。所以,\hbox{adj}\,L 的每一行可表示為 \mathbf{e} 的倍數。又 L=B^TB 是對稱矩陣,\hbox{adj}\,L 也是對稱矩陣。以上結果可推論 \hbox{adj}\,L=c\mathbf{e}\mathbf{e}^T=cJ

 
剩下來的問題是計算 c。伴隨矩陣 \hbox{adj}\,L(i,j) 元等於 L(j,i) 元的餘因子 (cofactor),即

\displaystyle  (\hbox{adj}\,L)_{ij}=c_{ji}=(-1)^{i+j}\det\tilde{L}_{ji}

其中 \tilde{L}_{ji} 代表移除 L 的第 j 列和第 i 行之後得到的 (n-1) 階方陣。因為 c=c_{ij}1\le i,j\le n,可考慮 c=c_{nn}=\det\tilde{L}_{nn},其中 \tilde{L}_{nn}=\tilde{B}_n^T\tilde{B}_n\tilde{B}_n 代表刪除有向關聯矩陣 B 的第 n 行所得到的 m\times (n-1) 階子陣。利用 Cauchy-Binet 公式 (見“Cauchy-Binet 公式”),

\displaystyle  \det\tilde{L}_{nn}=\det(\tilde{B}^T_n\tilde{B}_n)=\sum_{S}(\det\tilde{B}_S^T)(\det\tilde{B}_S)=\sum_S(\det\tilde{B}_S)^2

其中 S 表示從 m 個列選取 n-1 個的組合 (列指標集),共有 \binom{m}{n-1} 種選取方式,\tilde{B}_S 是從 \tilde{B}_n 挑選對應 Sn-1 個列所形成的方陣。套用定理三,推得 \det\tilde{L}_{nn}=t(G),證畢。

 
繼續討論前,先看一個問題:包含 n 個頂點的標記樹共有多少個?答案是 n^{n-2},稱為 Cayley 公式。我們曾經介紹德國數學家普呂弗 (Heinz Prüfer) 提出的證明 (見“電影《心靈捕手》的數學問題 (三)”),下面說明如何利用定理四證明 Cayley 公式。每一個包含 n 個頂點的標記樹與 n 階完全圖 (complete graph) 的最小生成樹有一對一的對應關係 (完全圖是指任意兩相異頂點皆有一邊連接)。考慮等價的問題:n 階完全圖,記為 K_n,共有多少個最小生成樹?完全圖 K_n 的拉普拉斯矩陣為 (見“線性代數在圖論的應用 (三):拉普拉斯矩陣”)

\displaystyle  L_K=nI-J=\left[\!\!\begin{array}{cccc} n-1&-1&\cdots&-1\\ -1&n-1&\cdots&-1\\ \vdots&\vdots&\ddots&\vdots\\ -1&-1&\cdots&n-1 \end{array}\!\!\right]

這種特殊形態的矩陣稱為組合矩陣 (combinatorial matrix),一般形式如下:

\displaystyle  C=xI+yJ=\begin{bmatrix} x+y&y&\cdots&y\\ y&x+y&\cdots&y\\ \vdots&\vdots&\ddots&\vdots\\ y&y&\cdots&x+y \end{bmatrix}

Cn\times n 階,則伴隨矩陣為 (見“特殊矩陣 (17):組合矩陣”)

\displaystyle  \hbox{adj}\,C=x^{n-2}(x+ny)I-x^{n-2}yJ

代入 x=ny=-1,就有 \hbox{adj}\,L_K=\hbox{adj}\,(nI-J)=n^{n-2}J,即得 Cayley 公式 t(K_n)=n^{n-2}

 
定理四可推演出 t(G) 的簡明公式,稱為克希荷夫矩陣─樹定理。

 
克希荷夫矩陣─樹定理::對於一 n 階簡單標記圖 G

\displaystyle  t(G)=\frac{1}{n^2}\det(L+J)

使用 J^2=nJLJ=0,寫出

\begin{aligned}  (L+J)(nI-J)&=nL+nJ-LJ-J^2\\  &=nL+nJ-nJ\\  &=nL.\end{aligned}

等號兩邊取伴隨矩陣,左邊是

\begin{aligned}  \hbox{adj}\,((L+J)(nI-J))&=(\hbox{adj}\,(L+J))(\hbox{adj}\,(nI-J))\\  &=n^{n-2}\hbox{adj}\,(L+J)J,  \end{aligned}

右邊是 (套用定理四) \hbox{adj}\,(nL)=n^{n-1}\hbox{adj}\,L=n^{n-1}t(G)J。合併可得

\hbox{adj}\,(L+J)J=nt(G)J

等號兩邊左乘 L+J(L+J)\hbox{adj}\,(L+J)J=nt(G)(L+J)J,繼續化簡為

\displaystyle  \det(L+J)J=nt(G)J^2=n^2t(G)J

比較 J 的係數即證明所求。

 
下面給出 t(G) 的另一個表達式。考慮 n 階連通圖 G,令 L 的非零特徵值為 \lambda_1,\ldots,\lambda_{n-1}。因為 L 是實對稱矩陣,所有的特徵向量 \{\mathbf{e},\mathbf{x}_1,\ldots,\mathbf{x}_{n-1}\} 組成一正交集,其中 L\mathbf{e}=\mathbf{0},且 L\mathbf{x}_i=\lambda_i\mathbf{x}_i\mathbf{x}_i\in\hbox{span}\{\mathbf{e}\}^\perp。因此,(L+J)\mathbf{e}=L\mathbf{e}+\mathbf{e}\mathbf{e}^T\mathbf{e}=n\mathbf{e},且 (L+J)\mathbf{x}_i=L\mathbf{x}_i+\mathbf{e}\mathbf{e}^T\mathbf{x}_i=\lambda_i\mathbf{x}_ii=1,\ldots,n-1。合併以上結果,L+J 的特徵值為 n,\lambda_1,\ldots,\lambda_{n-1},可知 \det(L+J)=n\lambda_1\cdots\lambda_{n-1},故圖 G 的最小生成樹總數為

\displaystyle  t(G)=\frac{1}{n}\lambda_1\cdots\lambda_{n-1}

 
最後我們計算前例 4 階圖的最小生成樹數。寫出

\displaystyle  L+J=\left[\!\!\begin{array}{rrrr}  4&0&0&0\\  0&3&1&0\\  0&1&3&0\\  0&0&0&4  \end{array}\!\!\right]

t(G)=4^{-2}\det(L+J)=4^{-2}\cdot 128=8。另外,L 的非零特徵值為 2,4,4,由此亦可得 t(G)=(1/4)\cdot 2\cdot 4\cdot 4=8。讀者不妨自行畫出所有的最小生成樹。

Advertisements
本篇發表於 圖論 並標籤為 , , , , , , , 。將永久鏈結加入書籤。

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com Logo

您的留言將使用 WordPress.com 帳號。 登出 / 變更 )

Twitter picture

您的留言將使用 Twitter 帳號。 登出 / 變更 )

Facebook照片

您的留言將使用 Facebook 帳號。 登出 / 變更 )

Google+ photo

您的留言將使用 Google+ 帳號。 登出 / 變更 )

連結到 %s