2.1.5 圖的矩陣
圖
的不變量，指的是與相關的一個數，或者一個向量，它對任何一個與同構的圖而言都具有相同的數，或相同的向量。例如，對具有
個頂點的圖而言，就是一個不變量。同理，對具有
條邊的圖而言，就是一個不變量。圖的色數、最大獨立數等也是圖的不變量；圖的度序列顯然是圖的向量型不變量。一般而言，圖的不變量很難精準刻畫圖的結構與特征。
本小節介紹的圖的矩陣可精準刻畫圖的結構與特征，是計算機對圖進行信息處理的基礎。圖的基本矩陣有兩種：關聯矩陣和相鄰矩陣。本小節簡要介紹這兩類矩陣，以及代數圖論中的另一個核心矩陣——拉普拉斯矩陣。
設是一個
-圖，
，
，的關聯矩陣記作
，它是一個
矩陣，其中
是與
和
（
，
）相關聯的次數（0、1或2）。圖2.15所示為圖及其關聯矩陣。
圖2.15 圖
及其關聯矩陣
關聯矩陣是一種利用圖的頂點與邊之間的關聯關系來刻畫圖結構的矩陣。當圖的邊數較多時，進行關聯矩陣計算所需的存儲空間較大，此時可用鄰接矩陣來代替關聯矩陣。
鄰接矩陣是一種刻畫圖頂點之間相鄰關系的矩陣，定義如下。
設是階圖，。
矩陣
為圖的鄰接矩陣，其中
表示連接與
的邊的數量。
例如，圖2.15所示的圖對應的鄰接矩陣
為
鄰接矩陣具有下列特性。
（1）
是對稱矩陣，當且僅當無環時，的對角線元素均為0。
（2）是對角線元素為0的對稱0-1矩陣當且僅當是簡單圖。
注2.6 簡單圖與對角線元素均為0的0-1對稱矩陣一一對應。
這是因為：一方面，對于一個對角線元素均為0的0-1對稱矩陣
，可以唯一地構造出簡單圖，使
；另一方面，由鄰接矩陣的特性（2），結論成立。
基于注2.6，圖的許多性質可以利用矩陣進行研究。對定理2.5與定理2.6的證明可查閱文獻[3]。
定理2.5 設
表示簡單圖的鄰接矩陣，則有如下結論。
（1）的
次冪
的
元素
等于圖中長為
的
途徑數量[4]。
[4] 途徑是指點邊交互的序列v0e1v1e2…ekvk,其中ei = vi-1vi（i=1,2,…,k）。
（2）
。
（3）
是中以為一個頂點的三角形數量的兩倍?！ 〃€
下述定理刻畫了正則圖中鄰接矩陣與關聯矩陣之間的關系。
定理2.6 設
和分別為圖的關聯矩陣和鄰接矩陣，若是
-正則圖，則有
其中，
是的轉置矩陣，
是階單位矩陣。 █
設
是階簡單圖，，則矩陣
為圖的拉普拉斯矩陣。其中，為圖的鄰接矩陣，
為圖的對角矩陣，對角線上的元素
表示頂點在圖中的度數（
）；非對角線上的元素均為0。
拉普拉斯矩陣
具有下列特性。
（1）為對稱的半正定矩陣。
（2）的秩為
，其中為中連通分支的數量。
（3）對任意向量
，有
（4）的每行元素與每列元素之和都為0。
（5）中任意元素的代數余子式相等。