線性代數在圖論的應用 (二):關聯矩陣

本文的閱讀等級:初級

線性代數在圖論的應用建立於圖的矩陣表達。我們曾在“線性代數在圖論的應用 (一):鄰接矩陣”討論了鄰接矩陣 (adjacency matrix),本文將介紹另一個重要的矩陣表達──關聯矩陣 (incidence matrix)。令 G=(V,E) 為一個有向圖,其中 V=\{v_1,\ldots,v_n\} 是頂點集合,E=\{e_1,\ldots,e_m\} 是有向邊集合。我們以 \vert V\vert\vert E\vert 分別表示頂點和邊的總數,即 \vert V\vert=n\vert E\vert=m。有序對 e_i=(v_j,v_k) 表示邊 e_i 的起始頂點是 v_j,終止頂點是 v_k,即 v_j\xrightarrow[]{~e_i~}v_k。我們定義關聯矩陣 A=[a_{ij}] 為一 m\times n 階矩陣,其中 a_{ij}=-1a_{ik}=+1e_i=(v_j,v_k),其餘元為零[1]。見下例:

關聯矩陣1

此圖的關聯矩陣為

\displaystyle  A=\bordermatrix{  ~&v_1&v_2&v_3&v_4&v_5\cr  e_1&-1&1&0&0&0\cr  e_2&1&0&-1&0&0\cr  e_3&-1&0&0&1&0\cr  e_4&0&-1&0&0&1\cr  e_5&0&0&1&0&-1\cr  e_6&0&0&0&1&-1  }

 
對於任一有向圖 G,關聯矩陣 A 的每一列所有元之和必為零 (因為每一列必包含兩個非零元,1-1),換句話說,A 的所有行向量和等於零向量。設 n 維向量 \mathbf{e}=(1,1,\ldots,1)^T,則 A\mathbf{e}=\mathbf{0},故 \mathbf{e} 屬於 A 的零空間 (nullspace)。由秩─零度定理可得

\hbox{rank}A=\dim C(A)=n-\dim N(A)\le n-1

這裡 N(A) 表示 A 的零空間,C(A) 表示 A 的行空間 (column space)。在甚麼情況下,不等式的等號成立?答案是 G 為一個連通圖 (connected graph)。若一圖 G 的任意兩頂點之間存在一序列的邊 (不論有向邊的方向為何),則稱之為連通圖。

 
定理一:若 G=(V,E) 是一個連通圖且 \vert V\vert=n,則 \hbox{rank}A=n-1。反之亦然。

假設 \mathbf{x}\in N(A),即 A\mathbf{x}=\mathbf{0}。若 v_i\sim v_j,意思是 v_iv_j 鄰接,即 (v_i,v_j)\in E(v_j,v_i)\in E,則 x_i=x_j。若 v_i\sim v_jv_j\sim v_k,則 x_i=x_j=x_k。根據傳遞性,若 v_pv_q 之間存在連通路徑,則 x_p=x_q。因為 G 是一個連通圖,推論所有 x_ii=1,\ldots,n,全部都相等。所以,N(A)=\hbox{span}\{\mathbf{e}\},即有 \dim N(A)=1。反向推論同樣成立。

 
定理一可以推廣至 G 有多個連通元件 (connected component) 的情況。

定理二:若 G=(V,E)k 個連通元件且 \vert V\vert=n,則 \hbox{rank}A=n-k

G_i=(V_i,E_i)i=1,\ldots,k,為圖 G 的連通元件,且 \vert V_i\vert=n_i。將頂點和邊重新排列 (如有必要),使 G 的關聯矩陣具有下列形式:

\displaystyle  A=\begin{bmatrix}  A_1&0&\cdots&0\\  0&A_2&\cdots&0\\  \vdots&\vdots&\ddots&\vdots\\  0&0&\cdots&A_k  \end{bmatrix}

其中 A_i 是連通元件 G_i 的關聯矩陣。因為 G_i 是一連通圖,定理一表明 \hbox{rank}A_i=n_i-1,即得

\displaystyle\begin{aligned}  \hbox{rank}A&=\hbox{rank}A_1+\cdots+\hbox{rank}A_k\\  &=(n_1-1)+\cdots+(n_k-1)\\  &=n_1+\cdots+n_k-k=n-k.\end{aligned}

 
以下設 G=(V,E) 為一連通有向圖,我們以電路學為例,解說關聯矩陣 A 的四個基本子空間的物理意義。

 
零空間:設想 \mathbf{x}=(x_1,\ldots,x_n)^T 的第 jx_j 表示頂點 v_j 上的電壓,則 m 維向量 A\mathbf{x} 的第 ix_k-x_j 表示有向邊 e_i=(v_j,v_k) 所連結的兩頂點的電壓差,如上例,

\displaystyle  A\mathbf{x}=\left[\!\!\begin{array}{rrrrr}  -1&1&0&0&0\\  1&0&-1&0&0\\  -1&0&0&1&0\\  0&-1&0&0&1\\  0&0&1&0&-1\\  0&0&0&1&-1  \end{array}\!\!\right]\begin{bmatrix}  x_1\\  x_2\\  x_3\\  x_4\\  x_5  \end{bmatrix}=\begin{bmatrix}  x_2-x_1\\  x_1-x_3\\  x_4-x_1\\  x_5-x_2\\  x_3-x_5\\  x_4-x_5  \end{bmatrix}

線性方程 A\mathbf{x}=\mathbf{b} 可以解釋如下:給定電壓差 b_1,\ldots,b_m,求出頂點的實際電壓 x_1,\ldots,x_n?因為我們可以升高或降低等量的頂點電壓,即 x_j+cj=1,\ldots,n,可知 \mathbf{x}=(c,\ldots,c)^T 屬於 A 的零空間,所以當 A\mathbf{x}=\mathbf{b} 有解時,我們可以得到無窮多組解。

 
行空間:我們明瞭 C(A)\mathbb{R}^m 的一子空間,但 C(A) 未必充滿整個 \mathbb{R}^m。若 \mathbf{b} 屬於行空間 C(A),則 A\mathbf{x}=\mathbf{b} 有解。具體地說,\mathbf{b} 必須滿足甚麼條件方使 A\mathbf{x}=\mathbf{b} 有解?以上例說明計算程序。寫出增廣矩陣 \begin{bmatrix}  A|\mathbf{b}  \end{bmatrix},使用高斯消去法化簡可得一梯形矩陣:

\displaystyle  \left[\!\!\begin{array}{rrrrrcc}  -1&1&0&0&0&\vline&b_1\\  1&0&-1&0&0&\vline&b_2\\  -1&0&0&1&0&\vline&b_3\\  0&-1&0&0&1&\vline&b_4\\  0&0&1&0&-1&\vline&b_5\\  0&0&0&1&-1&\vline&b_6  \end{array}\!\!\right]\to\left[\!\!\begin{array}{rcrrccc}  -1&1&0&0&0&\vline&b_1\\  0&1&-1&0&0&\vline&b_1+b_2\\  0&0&-1&1&0&\vline&b_2+b_3\\  0&0&0&-1&1&\vline&b_1-b_3+b_4\\  0&0&0&0&0&\vline&b_1+b_2+b_4+b_5\\  0&0&0&0&0&\vline&b_2+b_3+b_5-b_6  \end{array}\!\!\right]

線性方程 A\mathbf{x}=\mathbf{b} 有解的充要條件是梯形矩陣有完整的零列,即

\displaystyle  b_1+b_2+b_4+b_5=0,~~~b_2+b_3+b_5-b_6=0

下圖顯示 G 的兩個迴路 (loop):

關聯矩陣2

因為電壓差 b_i 對應有向邊 e_i,上面兩式表明:每一迴路上所有的電壓差總和必為零,稱為克希荷夫 (Kirchhoff) 電壓定律。

 
左零空間:因為左零空間 N(A^T)C(A) 的正交補餘 (見“線性代數基本定理 (二)”),\mathbf{b}\in C(A) 必正交於 N(A^T)。由克希荷夫電壓定律可知 N(A^T) 的基底向量為

\displaystyle  (1,1,0,1,1,0)^T,~~~(0,1,1,0,1,-1)^T

經過適當重排序,從上面兩個基底向量可讀出兩個獨立的簡單迴路 (一迴路不包含更小的迴路):

\displaystyle  L_1:e_1\to e_4\to e_5\to e_2,~~~L_2:e_3\to -e_6\to e_5\to e_2

換句話說,每一獨立迴路產生左零空間的一個基底向量,數值 1-1 表示有向邊是否與迴路方向一致或相反。

 
列空間:若 \mathbf{c} 屬於列空間 C(A^T),則線性方程 A^T\mathbf{y}=\mathbf{c} 有解。但 \mathbf{y}\mathbf{c} 代表甚麼意思呢?仍用上例說明,寫出

\displaystyle  A^T\mathbf{y}=\left[\!\!\begin{array}{rrrrrr}  -1&1&-1&0&0&0\\  1&0&0&-1&0&0\\  0&-1&0&0&1&0\\  0&0&1&0&0&1\\  0&0&0&1&-1&-1  \end{array}\!\!\right]\begin{bmatrix}  y_1\\  y_2\\  y_3\\  y_4\\  y_5\\  y_6  \end{bmatrix}=\begin{bmatrix}  c_1\\  c_2\\  c_3\\  c_4\\  c_5  \end{bmatrix}=\mathbf{c}

設想 \mathbf{y}=(y_1,\ldots,y_m)^T 的第 iy_i 表示有向邊 e_i 所指方向的電流,而 \mathbf{c}=(c_1,\ldots,c_n)^T 的第 jc_j 表示頂點 v_j 上的電流源 (current source)。第一個式子 -y_1+y_2-y_3=c_1 說明流入頂點 v_1 的電流 (等號左邊) 等於該點的電流源大小。所以線性方程 A^T\mathbf{y}=\mathbf{c} 代表的意義是:每一頂點的所有流入電流總和必為零,稱為克希荷夫 (Kirchhoff) 電流定律。那麼 \mathbf{c} 又必須滿足甚麼條件才使 A^T\mathbf{y}=\mathbf{c} 有解?列空間 C(A^T) 是零空間 N(A) 的正交補餘,故 \mathbf{c}\in C(A^T) 必正交於零空間的基底向量 \mathbf{e},即

\displaystyle  c_1+c_2+\cdots+c_n=0

換句話說,惟當所有電流源的總和為零,即從外部流入頂點的淨電流為零,克希荷夫電流定律才成立。如果所有頂點不存在電流源,即 \mathbf{c}=\mathbf{0},則克希荷夫電流定律變成 A^T\mathbf{y}=\mathbf{0}。這時任一合法電流 \mathbf{y} 必可表示為左零空間 N(A^T) 的基底向量的線性組合,以上例來說,

\displaystyle  \mathbf{y}=\alpha(1,1,0,1,1,0)^T+\beta(0,1,1,0,1,-1)^T

 
最後總結連通有向圖 G=(V,E) 的關聯矩陣 A 的四個基本子空間性質:

  • 零空間:\dim N(A)=1N(A)=\hbox{span}\{\mathbf{e}\}
  • 行空間:\dim C(A)=n-1,其中 n=\vert V\vert。因為 A\mathbf{e}=\mathbf{0},可以證明 A 的任意 n-1 個行皆可形成線性獨立集 (證明見[2])。
  • 左零空間:\dim N(A^T)=m-n+1,其中 m=\vert E\vert。每一迴路構成 N(A^T) 的一個基向量。
  • 列空間:\dim C(A^T)=n-1。挑選 An-1 個線性獨立列,其對應圖必不含迴路。證明留給讀者自行完成。

 
註解:
[1] 無向圖亦可定義關聯矩陣 A=[a_{ij}]。若無向邊 e_i 連接 v_jv_k,則 a_{ij}=1a_{ik}=1,否則設為零。無向圖和有向圖的關聯矩陣有不同的性質,應用也隨之不同,在此省略討論。
[2] 寫出關聯矩陣的行向量表達 A=\begin{bmatrix}  \mathbf{a}_1&\cdots&\mathbf{a}_n  \end{bmatrix}。因為 A\mathbf{e}=\mathbf{0},即 \mathbf{a}_1+\cdots+\mathbf{a}_n=\mathbf{0},每一 \mathbf{a}_j 必可表示為其餘行向量的線性組合。在不失一般性的提前下,假設 \{\mathbf{a}_1,\ldots,\mathbf{a}_{n-1}\} 為一線性相關集,推論 \mathbf{a}_n\not\in\hbox{span}\{\mathbf{a}_1,\ldots,\mathbf{a}_{n-1}\},否則 \dim C(A)<n-1。換句話說,\mathbf{a}_n 無法表示成 \mathbf{a}_1,\ldots,\mathbf{a}_{n-1} 的線性組合,產生矛盾。

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

發表迴響

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

WordPress.com Logo

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

Twitter picture

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

Facebook照片

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

Google+ photo

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

連結到 %s