鄰接矩陣及其譜

鄰接矩陣是把圖變成矩陣最直接的方式：若節點 i 與節點 j 相連就在 (i,j) 處放 1，否則放 0。對無向圖 A 對稱。它的特徵值列表，即譜，是一枚指紋，編碼了出人意料之多的圖結構。

最乾淨的事實關於通路：A^k 的 (i,j) 元素計數從 i 到 j 長度為 k 的通路數。沿對角線求和，就把 A 的冪與特徵值聯繫起來，因為 trace(A^k) = sum of lambda^k。故譜確實計數了每種長度的閉合通路，包括藉由 trace(A^3) 數出三角形。

極端特徵值也有意義。最大特徵值 lambda_max 被夾在平均度數與最大度數之間，控制通路計數的增長；對連通圖，佩龍-弗羅貝尼烏斯定理使它單重且帶正特徵向量。一個圖是二部圖當且僅當其譜關於零對稱，於是最小特徵值等於 -lambda_max。

為何重要：譜能界定擴張性與混合速度（譜間隙），檢測結構（二部性、正則性），並支撐圖同構的啟發式方法。警示：譜不是完全不變量。不同的圖可以同譜，共享特徵值卻是真正不同的形狀。