第 8 讲 · 图的矩阵表示 | L.D.J 的私家工坊

矩阵表示的意义，是把“沿边走”“能否到达”和“顶点与边是否关联”变成加法、乘法和布尔运算。

邻接矩阵记录一步连接

对顶点顺序 $v_1,\ldots,v_n$ ，有向简单图的邻接矩阵 $A=(a_{ij})$ 定义为：

a_{ij}= \begin{cases} 1,&(v_i,v_j)\in E,\\ 0,&\text{否则}. \end{cases}

第 $i$ 行和是 $v_i$ 的出度，第 $i$ 列和是入度。无向简单图的 $A$ 是对称矩阵，每行元素和就是对应顶点的度数。

顶点编号改变会改变矩阵行列顺序，却不改变图本身。若两图同构，它们的邻接矩阵只相差同一个顶点置换对行列的重排。

(A^k)_{ij}

等于从 $v_i$ 到 $v_j$ 、长度恰为 $k$ 的通路数。原因可以从矩阵乘法看出：

(A^{k+1})_{ij}=\sum_r(A^k)_{ir}A_{rj}.

每项先数 $i$ 到 $r$ 的 $k$ 步走法，再检查是否有最后一条边 $r\to j$ ；对所有可能的倒数第二个顶点 $r$ 求和，就无重无漏地得到 $k+1$ 步走法。

最小的使 $(A^k)_{ij}>0$ 的 $k$ 就是两点距离。这里数的是允许重复的通路，不是基本路径数量。

可达性矩阵 $R=(r_{ij})$ 在 $v_i$ 能到达 $v_j$ 时取 1。令 $B(M)$ 把矩阵中非零元素变成 1，则：

R=B(I+A+A^2+\cdots+A^{n-1}).

若一条可达通路重复顶点，就可以删掉中间的圈，所以总能找到长度不超过 $n-1$ 的基本通路；这解释了为什么不用继续加到无穷。

两个顶点位于同一强连通分支，当且仅当它们互相可达。因此逐元素乘积：

R\odot R^\mathsf T

的第 $i$ 行中，值为 1 的列恰好对应与 $v_i$ 同属一个 SCC 的顶点。

无向简单图有 $n$ 个顶点、 $m$ 条边时，关联矩阵是 $n\times m$ 矩阵；顶点 $v_i$ 与边 $e_j$ 关联时元素为 1。每一列恰有两个 1。

有向图可约定边的起点取 1、终点取 $-1$ ，其他位置取 0，于是每列恰有一个 1 和一个 $-1$ 。邻接矩阵适合描述“顶点到顶点”，关联矩阵适合描述“顶点到边”，不要只因都含 0、1 就混用。

课件最后给出代数图论的入口：研究邻接矩阵的特征值与图结构之间的联系。例如无向二分图的非零特征值关于 0 成对出现。这里不要求把所有结论展开证明，重点是看到矩阵不只是存储格式，它还能让线性代数成为研究图的工具。