鄰接矩陣

在圖論和計算機科學中，鄰接矩陣（英語：adjacency matrix）是一種方陣，用來表示有限圖。它的每個元素代表各點之間是否有邊相連。

作爲特例，簡單圖的鄰接矩陣是(0,1)矩陣並且對角線元素都爲0。無向圖的鄰接矩陣是對稱矩陣。圖和其鄰接矩陣的特徵值和特徵向量之間的關系是譜圖理論的研究對象。

圖的關聯矩陣需要和鄰接矩陣區分。它是圖的另一種矩陣表示方式，它的元素表示各個節點-邊對是否相關。還有圖的度數矩陣，含有每個結點的度數信息。

距離矩陣可算是鄰接矩陣的擴充。

定義

階為$n$的圖$G$的鄰接矩陣$A$是$n\times n$的。將$G$的頂點標籤為$v_{1},v_{2},...,v_{n}$。若$(v_{i},v_{j})\in E(G)$，$A_{ij}=1$，否則$A_{ij}=0$。也可以用大於0的值表示邊的權值，例如可以用邊權值表示一個點到另一個點的距離。

無向圖的鄰接矩陣是對稱矩陣。

例子

無向圖

無向圖的鄰接矩陣計算方法是每條邊爲對應的單元加上1，而每個自環加上2。這樣讓某一節點的度數可以通過鄰接矩陣的對應行或者列求和得到。

無向圖	鄰接矩陣
	${\begin{pmatrix}2&1&0&0&1&0\\1&0&1&0&1&0\\0&1&0&1&0&0\\0&0&1&0&1&1\\1&1&0&1&0&0\\0&0&0&1&0&0\end{pmatrix}}$ 從左到右、從上到下分別代表1–6節點。

有向圖

有向圖的鄰接矩陣可以是不對稱的。我們可以定義有向圖的鄰接矩陣中的某個元素A_ij代表：

1. 從i指向j的邊的數目
2. 從j指向i的邊的數目

第一種定義廣泛用於圖論和社會網絡分析（如：社會學、政治學、經濟學、心理學）。第二種更加常見於其他應用學科（如：動態系統、物理、網絡學），這些學科有時用鄰接矩陣A表示圖上的線性動力。

在第一種定義下，有向圖的某個節點的入度可以通過對應的列（column）求和而得，出度可以通過對應的行（row）求和而得。在第二種定義下，入度可以通過對應的行（row）求和而得，出度可以通過對應的列（column）求和而得。

有向圖	鄰接矩陣
	${\begin{pmatrix}0&1&0&1\\0&0&0&1\\1&1&0&0\\0&0&1&0\\\end{pmatrix}}$ 從左到右、從上到下分別代表1–4節點。 採用有向圖鄰接矩陣的第一種定義

特性

設圖$G$的鄰接矩陣為$A$，邊的取值為1。

• 如果頂點有自我連接產生的自環（loop），則在矩陣的主對角線上會有非零的值；如果沒有自環，則主對角線上全部是0。
• $A^{n}$的元素$A_{ij}^{n}$可以表示由頂點$i$到頂點$j$長度為$n$的徑的數目。
• $G$沒有有向圈若且唯若$I-A$可逆。$(I-A)^{-1}$的元素$ij$表示由頂點$i$到頂點$j$的所有徑的數目。因為：$(I-A)^{-1}=I+A+A^{2}+A^{3}+...$

應用

傳球問題

A、B、C、D四人傳球6次，從A開始，最終回到A手裡，有多少種傳法？

非矩陣解法：

1. m個人傳n次球，$\sum _{i=1}^{[{\frac {n}{2}}]}(m-1)^{i}(m-2)^{n-2i}C_{n-1-i}^{i-1}$
2. $(m-1)P_{n+1}=1-P_{n},P_{n}={\frac {1}{m}}(1-({\frac {-1}{m-1}})^{n-1})$，將P_n乘上總傳法數$(m-1)^{n}$

矩陣解法：

$A={\begin{bmatrix}0&1&1&1\\1&0&1&1\\1&1&0&1\\1&1&1&0\\\end{bmatrix}},A^{6}={\begin{bmatrix}183&182&182&182\\182&183&182&182\\182&182&183&182\\182&182&182&183\\\end{bmatrix}}$

圖論算法的計算機實踐

參見：鄰接表和十字鍊表

鄰接矩陣法是比較簡單的圖論問題建模方法，它以方形二維陣列的形式存儲圖的數據。它在算法應用中的主要特點包括：

• 各元素的取值與邊的輸入順序無關。
• 利用輸入數據建圖之前，因為不一定每對點之間都有邊相連，所以先要執行將所有邊的權值設為無效值的初始化步驟。以此法建模有$n$個點和$m$條邊的圖，其初始化需要$O(n^{2})$的時間複雜度，建圖的時間則為$O(m)$。
• 以此法建模有$n$個點和$m$條邊的圖，其內存空間開銷的規模是$O(n^{2})$。

主要缺點包括：

• 遍曆元素時，存在的邊和不存在的邊都不得不檢查一遍，導致遍歷效率低。
• 不能存儲重複的邊。
• 當頂點數量多時，內存空間開銷會很大。
• 存儲稀疏圖時會得到稀疏矩陣，空間利用率不高。
• 存儲無向圖時，由於此時矩陣是對稱的，而對稱位置上的成對元素保存的信息是重複的，導致空間利用率不高。

隨機過程

在隨機過程理論中，表示單步狀態變化的轉移矩陣就是一種鄰接矩陣。