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

本文的閱讀等級:初級

針對給定的一個有限集合,集合裡的元素之間常存在某種關係。例如,一個國家中城市之間的飛航路線,產業聚落中公司之間的產品供應鏈,以及社交網路服務網站,如 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),並稱頂點 xy 與邊 e 有關聯 (incident)。如果兩個頂點存在不對稱關係,例如,公司 x 是公司 y 的買主,連接 xy 的邊 \{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=Gv_2=Fv_3=Mv_4=Dv_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_GA_H 分別為圖 G 和圖 H 的鄰接矩陣,同構不過就是將頂點排序而已。若存在排列矩陣 P 滿足

P^TA_GP=A_H

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

cospectral graphs

同譜圖

由目視可判斷上面的無向圖 XY 具有不同的結構[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_XA_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 的相重數。因此,XY 是同譜圖。鄰接矩陣的初步分析即顯示特徵多項式包含許多重要性質,它是線性代數於圖論應用的一個重要研究對象,日後將另文介紹。

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

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

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

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

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

因為 a_{kj}=10,推論 (A^{m+1})_{ij} 即為長度 m+1,從 v_iv_j 的漫步總數。

 
鄰接矩陣還可以回答圖中任何兩頂點是否連通。對於無向圖,若任何兩頂點之間都有路徑可抵,我們稱它是連通的 (connected);對於有向圖,則稱為強連通 (strongly connected)。連通頂點 v_iv_j 的最短漫步稱為 v_iv_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_iv_j 的距離便小於 d。因為 n 階鄰接矩陣的直徑必小於 n,上述性質提供了由 A^kk=0,1,\ldots,n-1,計算距離矩陣 D 的方法:若 (A^d)_{ij}\neq 0,且 (A^{k})_{ij}=0k=0,1,\ldots,d-1,則 d(v_i,v_j)=d。抄錄家庭成員圖的 AA^2A^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_iv_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_iv_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_0u_i 之間存在至少一個長度為 i 的路徑。因此,A^i 對應頂點 u_0u_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。

相關閱讀:
廣告
本篇發表於 線性代數專欄, 圖論, 應用之道 並標籤為 , , , , , , , 。將永久鏈結加入書籤。

發表迴響

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

WordPress.com Logo

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

Twitter picture

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

Facebook照片

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

Google+ photo

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

連結到 %s