邻接矩阵

邻接矩阵（adjacency matrix）用一个方阵记录图中各对顶点之间的边。给顶点指定次序后，矩阵第 $i$ 行、第 $j$ 列表示从顶点 $i$ 到顶点 $j$ 的邻接关系。它把图的局部连边转换为矩阵运算；尤其是矩阵的幂，可以记录指定长度的游走数量。

下文先讨论无向简单图：每对不同顶点之间至多一条边，没有自环。设顶点次序为 $a,b,c,d,e$，边为 $ab,ac,bc,cd,de$。先固定次序十分必要，因为同一张图重排顶点后，矩阵中的行列位置会同时变化。

从边逐项写成方阵

对 $n$ 顶点图 $G$，邻接矩阵 $A=(A_{ij})\in \{0,1{\}}^{n\times n}$ 定义为 $$A_{ij}=\{\begin{array}{cc}1,& \{v_i,v_j\}\in E(G),\\ 0,& \text{其他情形}.\end{array}$$ 无向性给出 $A=A^{𝖳}$，不含自环给出 $A_{ii}=0$。主例中，顶点 $a$ 只与 $b,c$ 相邻，所以第一行为 $(0,1,1,0,0)$；逐行写出得到 $$A=\left(\begin{array}{ccccc}0& 1& 1& 0& 0\\ 1& 0& 1& 0& 0\\ 1& 1& 0& 1& 0\\ 0& 0& 1& 0& 1\\ 0& 0& 0& 1& 0\end{array}\right).$$ 行和依次为 $2,2,3,2,1$，等于相应顶点的度。矩阵所有元素之和为十，每条边在对称位置出现两次，因此边数为五。每个零也有意义：例如 $A_{ae}=0$ 表示没有直接边，并不表示两点之间不存在较长路线。

a到e没有直接边，却有三步游走a、c、d、e；图中的顶点次序与矩阵行列一致。

矩阵平方与共同邻居

矩阵乘法规定 $$(A^2{)}_{ij}=\sum _{k=1}^n{A}_{ik}{A}_{kj}.$$ 在零一矩阵中，一个乘积为一，恰好表示两条边 $i-!k$ 和 $k-!j$ 同时存在。每一个这样的中间顶点都贡献一个两步游走。因此 $(A^2{)}_{ij}$ 是两点的共同邻居数；对角位置 $(A^2{)}_{ii}=\mathrm{deg}(v_i)$，计入的是走到一个邻居再原路返回的游走。

在主例中，$a$ 与 $d$ 的唯一共同邻居是 $c$，故 $$(A^2{)}_{ad}=0\cdot 0+1\cdot 0+1\cdot 1+0\cdot 0+0\cdot 1=1.$$ 而 $a$ 与 $e$ 没有共同邻居，故 $(A^2{)}_{ae}=0$。顶点 $a$ 有两个邻居，所以 $(A^2{)}_{aa}=2$，对应 $a,b,a$ 和 $a,c,a$。它们都重复了起点；将它们称为两条简单路径会导致概念错误。

矩阵幂计数游走的证明

长度为 $r$ 的游走是一串 $r+1$ 个顶点，相邻位置之间有边，允许重复顶点和边。约定 $A^0=I$，长度零的游走只把一个顶点留在自身。

定理。 对每个整数 $r\ge 0$，$(A^r{)}_{ij}$ 等于从 $v_i$ 到 $v_j$ 的长度恰为 $r$ 的游走数。

证明。 当 $r=0$ 时，同一点间有一条零步游走，不同点之间没有，与单位矩阵吻合。假设结论对 $r$ 成立。每条从 $i$ 到 $j$ 的 $r+1$ 步游走，都有一个唯一的倒数第二个顶点 $k$；删去最后一条边后，是一条从 $i$ 到 $k$ 的 $r$ 步游走。若 $A_{kj}=1$，每条这样的前缀都能接上最后一条边；若为零则一条也不能接。按 $k$ 分类，数量为 $$\sum _k(A^r{)}_{ik}{A}_{kj}=(A^{r+1}{)}_{ij}.$$ 不同 $k$ 的分类互不重叠，也覆盖全部游走，完成归纳。

主例中 $e$ 只有邻居 $d$，所以 $$(A^3{)}_{ae}=\sum _k(A^2{)}_{ak}{A}_{ke}=(A^2{)}_{ad}=1.$$ 这条三步游走就是图中的 $a,c,d,e$。结合一、二步计数均为零，才可断言它们的最短距离是三；某一幂为正仅表示有相应长度的游走，本身不保证它最短。

变式。 主例中的 $(A^2{)}_{ce}$ 是多少？因为 $e$ 的唯一邻居为 $d$，而 $cd$ 是边，所以答案为一，游走为 $c,d,e$。相应地，$(A^2{)}_{cc}=3$，因为 $c$ 可以经三个邻居分别返回。

闭游走与三角形

矩阵的迹为对角元素之和。$\mathrm{tr}(A^2)=\sum _i\mathrm{deg}(v_i)=2m$ 再次给出边数。对于简单无向图，三步闭游走必须依次经过一个三角形的三个不同顶点：若中途重复起点，下一步闭合便需要自环，而本图不允许自环。每个三角形可从三个顶点出发，沿两个方向走，故 $$\text{三角形数}=\frac{\mathrm{tr}(A^3)}{6}.$$ 主例只有 $abc$ 一个三角形，三个顶点各有两条三步闭游走，因此迹为六，除以六得到一。四步闭游走则可以沿一条边往返两次，所以不能直接把 $\mathrm{tr}(A^4)$ 除以八当作四环数。

标号、方向和权重的约定

若顶点依新次序 $\pi (1),\dots ,\pi (n)$ 排列，定义置换矩阵 $P$ 的第 $i$ 列为旧坐标中的第 $\pi (i)$ 个单位向量，则新邻接矩阵为 $P^{𝖳}AP$。左乘和右乘配合重排行列，边关系没有改变。

对有向图，本文取 $A_{ij}=1$ 表示 $i\to j$，行和为出度，列和为入度；矩阵一般不对称。若采用相反约定，整个矩阵需转置。含多重边时可令条目记录边的条数，幂计数会把不同边的选择分别计入。含权图若以边权为条目，则 $(A^r{)}_{ij}$ 累加的是每条游走上边权的乘积，而不是游走长度或最短路成本；计算最短路需要另一种加法与最小化规则。

邻接矩阵占据 $n^2$ 个位置，读取某对顶点是否相邻只需查看一个条目；稀疏图即便只有很少边，普通稠密矩阵仍使用平方空间。其价值在于直接表达线性运算和谱性质，具体存储应根据边数和要执行的运算决定。