邻接矩阵及其谱

邻接矩阵是把图变成矩阵最直接的方式：若节点 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。

为何重要：谱能界定扩张性与混合速度（谱间隙），检测结构（二部性、正则性），并支撑图同构的启发式方法。警示：谱不是完全不变量。不同的图可以同谱，共享特征值却是真正不同的形状。