鄰接矩陣

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

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

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

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

定義

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

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

例子

無向圖

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

無向圖	鄰接矩陣
	${\displaystyle {\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的邊的數目

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

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

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

特性

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

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

應用

傳球問題

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

非矩陣解法：

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

矩陣解法：

${\displaystyle 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}}}$

圖論演算法的電腦實踐

參見：鄰接表和十字鏈結串列

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

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

主要缺點包括：

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

隨機過程

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

參考資料

1. 梁冰; 馮林. 6.1.4. 吳文虎 (主審); 房鳴 (主審); 孫琳 (責任編輯) (編). 程序设计算法基础. 大學生創意·創新·創業教育與實踐系列教材 1. 北京: 高等教育出版社. 2018: 130–131. ISBN 978-7-04-049192-0 （中文（中國大陸））.
2. Borgatti, Steve; Everett, Martin; Johnson, Jeffrey, Analyzing Social Networks 2nd, SAGE, p. 20, 2018
3. Newman, Mark, Networks 2nd, Oxford University Press, p. 110, 2018
4. 劉亞國. 图论中邻接矩阵的应用. 張家口職業技術學院學報. 2007, (4) [2014-01-12]. （原始內容存檔於2014-01-12） （中文（中國大陸））.
5. 吳煒超. 馬濤; 何萬程; 郭子偉 , 編. 传球问题的终极解法. 《人教網刊》第4期. 2011年6月23日 [2019年12月15日]. （原始內容存檔於2016年3月5日） （中文（中國大陸））.