線性代數在圖論的應用 (一)：鄰接矩陣

Posted on 01/18/2010 by ccjou

本文的閱讀等級：初級

針對給定的一個有限集合，集合裡的元素之間常存在某種關係。例如，一個國家中城市之間的飛航路線，產業聚落中公司之間的產品供應鏈，以及社交網路服務網站，如 Facebook，MySpace 的社群人際關係。圖論 (graph theory) 是一門描述集合裡元素彼此關係的數學領域，上述這些問題都可架構於圖論模型以利分析。

 
我們先回顧圖論的一些基本詞彙。圖 G=(V, E) 包含二類組成元件：頂點 (vertex) 集合 V=\{v_1,v_2,\ldots,v_n\} 與邊 (edge) 集合 E，\vert V\vert 與 \vert E\vert 分別表示頂點數與邊的總數。邊集合 E 中每個邊由一對相異的頂點所定義，表示為 e=\{x,y\}，我們稱頂點 x 和頂點 y 鄰接 (adjacent)，並稱頂點 x 和 y 與邊 e 有關聯 (incident)。如果兩個頂點存在不對稱關係，例如，公司 x 是公司 y 的買主，連接 x 和 y 的邊 \{x,y\} 具有方向性，稱為有向邊 (directed edge)，包含有向邊的圖稱為有向圖 (directed graph)。為了與無向邊區別，我們將有向邊記為 e=(x,y)，其中 x 是有向邊 e 的初始頂點，y 是終止頂點。本文僅考慮簡單圖，也就是說頂點與其自身不存在連接邊，且二鄰接頂點僅有一邊。

 
下面是一個描述家庭成員影響力的有向圖，5 個頂點 G, F, M, D, S 分別代表奶奶，父親，母親，女兒和兒子，每一個有向邊代表「某人可以影響另一人」。

family graph

家庭成員影響力圖

線性代數在圖論的應用就是運用代數方法解決圖論問題。我們介紹一個相當直覺化的矩陣表示法，稱為鄰接矩陣 (adjacency matrix)。以家庭成員圖說明，此圖包含 5 個成員，即 \vert V\vert=5，鄰接矩陣是一個 5\times 5 階矩陣 A=[a_{ij}]，若有向邊從 v_i 連至 v_j，則 a_{ij}=1，否則 a_{ij}=0。設 v_1=G，v_2=F，v_3=M，v_4=D，v_5=S，對應上圖的鄰接矩陣為

A=\begin{bmatrix} 0&1&1&0&0\\ 0&0&0&0&1\\ 0&1&0&1&0\\ 0&1&0&0&0\\ 1&0&1&0&0 \end{bmatrix}

 
家庭成員的頂點編號可以隨意安排，如果重排頂點編號排序，鄰接矩陣也隨之改變，但原圖的影響力結構維持不變，所以我們稱它為同構 (isomorphic)。兩個圖是否同構可從鄰接矩陣判斷，設圖 G 和圖 H 為定義於相同頂點集合的有向圖。令 A_G 和 A_H 分別為圖 G 和圖 H 的鄰接矩陣，同構不過就是將頂點排序而已。若存在排列矩陣 P 滿足

P^TA_GP=A_H

則 A_G 和 A_H 同構，詳細討論請參閱“矩陣視覺化”。排列矩陣 P 是正交矩陣，P^T=P^{-1}。因此，G 和 H 是同構圖的等價條件是 A_G 排列相似於 A_H。我們定義圖 G 的矩陣譜 (spectrum) 為鄰接矩陣 A 的特徵值集合，並附加其相重數。兩個相似矩陣有相同的特徵值 (見“相似變換下的不變性質”)，因此同構圖都有相同的矩陣譜，但反向陳述並不為真，具有相同矩陣譜未必是同構的，矩陣語言是有相同特徵值的兩矩陣未必是排列相似。若兩個不同構圖有相同的矩陣譜，我們稱之為同譜圖 (cospectral graph)。

cospectral graphs

同譜圖

由目視可判斷上面的無向圖 X 和 Y 具有不同的結構[1]。明顯地，無向圖的鄰接矩陣是對稱矩陣，如下：

A_X=\begin{bmatrix} 0&1&1&0&0&0&0\\ 1&0&0&1&0&1&0\\ 1&0&0&0&1&0&1\\ 0&1&0&0&1&1&0\\ 0&0&1&1&0&0&1\\ 0&1&0&1&0&0&1\\ 0&0&1&0&1&1&0 \end{bmatrix}，A_Y=\begin{bmatrix} 0&1&1&1&1&1&1\\ 1&0&1&0&0&0&1\\ 1&1&0&1&0&0&0\\ 1&0&1&0&1&0&0\\ 1&0&0&1&0&1&0\\ 1&0&0&0&1&0&1\\ 1&1&0&0&0&1&0 \end{bmatrix}

鄰接矩陣 A_X 和 A_Y 有相同的特徵多項式：

p(t)=(t+2)(t+1)^2(t-1)^2(t^2-2t-6)

因此也有相同的矩陣譜

\{-2,-1^{(2)},1^{(2)},1\pm\sqrt{7}\}

上標括弧內的數字表示大於 1 的相重數。因此，X 和 Y 是同譜圖。鄰接矩陣的初步分析即顯示特徵多項式包含許多重要性質，它是線性代數於圖論應用的一個重要研究對象，日後將另文介紹。

 
接下來我們研究如何將鄰接矩陣推廣至任意頂點之間的鄰接關係。在一個有向圖中，我們定義漫步 (walk) 為由 v_i 至 v_j 的一序列頂點，其長度為 l：

v_i=u_0\to u_1\to\cdots\to u_l=v_j

也就是說漫步包含連接 u_k 和 u_{k+1} 的有向邊，k=0,1,\ldots,l-1。如果途經的頂點都不重複拜訪，也就是 u_k 彼此相異，則稱它為路徑 (path)。

 
鄰接矩陣的冪矩陣 A^l 其 (i,j) 元，以 (A^l)_{ij} 表示，等於從頂點 v_i 至 v_j 且長度為 l 的漫步總數。證明採用數學歸納法。若 l=1，A^{l}=A，鄰接矩陣直接指出長度為 1 的漫步數。假設 l=m 時原命題成立，(A^{m})_{ij} 即為長度等於 m，從 v_i 至 v_j 的漫步總數，計算矩陣乘法可得

\displaystyle (A^{m+1})_{ij}=\sum_{k=1}^n(A^{m})_{ik}a_{kj}

因為 a_{kj}=1 或 0，推論 (A^{m+1})_{ij} 即為長度 m+1，從 v_i 至 v_j 的漫步總數。

 
鄰接矩陣還可以回答圖中任何兩頂點是否連通。對於無向圖，若任何兩頂點之間都有路徑可抵，我們稱它是連通的 (connected)；對於有向圖，則稱為強連通 (strongly connected)。連通頂點 v_i 與 v_j 的最短漫步稱為 v_i 與 v_j 的距離，記為 d(v_i,v_j)，並以距離矩陣 D=[d_{ij}] 表示，d_{ij}=d(v_i,v_j)。在一連通圖或強連通圖中，最長的距離稱作該圖的直徑。注意，無向圖的距離矩陣是對稱的，但有向圖則未必。

 
如果 d(v_i,v_j)=d，對於 k<d，都有 (A^k)_{ij}=0，其道理是倘若不為零，則 v_i 和 v_j 的距離便小於 d。因為 n 階鄰接矩陣的直徑必小於 n，上述性質提供了由 A^k，k=0,1,\ldots,n-1，計算距離矩陣 D 的方法：若 (A^d)_{ij}\neq 0，且 (A^{k})_{ij}=0，k=0,1,\ldots,d-1，則 d(v_i,v_j)=d。抄錄家庭成員圖的 A，A^2，A^3 於下：

A=\begin{bmatrix} 0&1&1&0&0\\ 0&0&0&0&1\\ 0&1&0&1&0\\ 0&1&0&0&0\\ 1&0&1&0&0 \end{bmatrix},~A^2=\begin{bmatrix} 0&1&0&1&1\\ 1&0&1&0&0\\ 0&1&0&0&1\\ 0&0&0&0&1\\ 0&2&1&1&0 \end{bmatrix},~A^3=\begin{bmatrix} 1&1&1&0&1\\ 0&2&1&1&0\\ 1&0&1&0&1\\ 1&0&1&0&0\\ 0&2&0&1&2 \end{bmatrix}

由此可推得

D=\begin{bmatrix} 0&1&1&2&2\\ 2&0&2&3&1\\ 3&1&0&1&2\\ 3&1&3&0&2\\ 1&2&1&2&0 \end{bmatrix}

從距離矩陣判斷此家庭人物圖是強連通，每一個成員都受其他人影響，且直徑為 3。

 
欲判定連通圖，可檢查任兩頂點 v_i 與 v_j 是否都有大於零的漫步數，即存在 k\in\{0,1,\ldots,n-1\} 滿足 (A^{k})_{ij}>0。我們可使用下面的矩陣組合來判斷給定的圖是否連通：

C=I+A+A^2+\cdots+A^{n-1}

如果 C 不含零元，則任兩個相異頂點都存在連通路徑，故為連通圖。另一個直接的方法是計算 (I+A)^{n-1}，根據二項式定理，

\displaystyle (I+A)^{n-1}=I+(n-1)A+\binom{n-1}{2}A^2+\cdots+(n-1)A^{n-2}+A^{n-1}

上式中各矩陣係數皆不為零，所以連通圖的檢查條件為 (I+A)^{n-1} 不包含零元。

 
另外補充一個關於無向連通圖的直徑與鄰接矩陣的特徵值關係。若一無向圖連通圖 G 的直徑為 d，則鄰接矩陣 A 有至少 d+1 個相異特徵值。證明於下。假設兩相異頂點 v_i 和 v_j 的距離等於直徑，即 d(v_i,v_j)=d，並設路徑為

v_i=u_0\to u_1\to\cdots\to u_d=v_j

對於每一 i=1,2,\ldots,d，頂點 u_0 與 u_i 之間存在至少一個長度為 i 的路徑。因此，A^i 對應頂點 u_0 和 u_i 的元必不為零，但 I, A,\ldots,A^{i-1} 的對應元全部等於零。換句話說，A^i 無法表示為 I,A,\ldots,A^{i-1} 的線性組合。所以，A 的最小多項式 (minimal polynomial，滿足 p(A)=0 且次數最小的多項式 p) 的次數至少為 d+1。因為 A 是一實對稱矩陣，故可對角化，等價條件是最小多項式不含重根 (“最小多項式 (下)”)，因此證明所求。

 
從冪矩陣 A^l 的跡數還可以得到有關圖結構的一些訊息。設 A 表示無向圖 G 的鄰接矩陣，令 \vert E\vert 為邊的總數，\vert T\vert 為三角形的總數，三頂點若彼此鄰接則構成一個三角形。不難證明下面的結果：

\begin{aligned} \mathrm{trace}A&=0\\ \mathrm{trace}A^2&=2\vert E\vert\\ \mathrm{trace}A^3&=6\vert T\vert\end{aligned}

計算上例無向圖 Y 其鄰接矩陣 A_Y 的冪矩陣：

A_Y^2=\begin{bmatrix} 6&2&2&2&2&2&2\\ 2&3&1&2&1&2&1\\ 2&1&3&1&2&1&2\\ 2&2&1&3&1&2&1\\ 2&1&2&1&3&1&2\\ 2&2&1&2&1&3&1\\ 2&1&2&1&2&1&3 \end{bmatrix},~ A_Y^3=\begin{bmatrix} 12&10&10&10&10&10&10\\ 10&4&7&4&6&4&7\\ 10&7&4&7&4&6&4\\ 10&4&7&4&7&4&6\\ 10&6&4&7&4&7&4\\ 10&4&6&4&7&4&7\\ 10&7&4&6&4&7&4 \end{bmatrix}

根據前面公式推知圖 Y 有 (1/2)\mathrm{trace}A^2_Y=12 條邊，包含 (1/6)\mathrm{trace}A_Y^3=6 個三角形。

 
參考來源：
[1] 共譜圖例引自 Chris Godsil 和 Gordon Royle 合著的 Algebraic Graph Theory，Springer，2001，pp 164。

相關閱讀：
This entry was posted in 線性代數專欄, 圖論, 應用之道 and tagged , , , , , , , . Bookmark the permalink.

Leave a comment