图的矩阵表示

把图的边关系写进矩阵，就能用线性代数研究图的结构与路径计数。

定义

设图 $G$ 的顶点为 $v_1,\dots,v_n$，其邻接矩阵 $A=(a_{ij})$ 是 $n$ 阶方阵，$a_{ij}$ 等于顶点 $v_i$ 到 $v_j$ 的边数。无向简单图的邻接矩阵是对称的 $0$-$1$ 矩阵，即布尔矩阵的特例（见布尔矩阵）。

关联矩阵 $M=(m_{ij})$ 以行为顶点、列为边，$m_{ij}=1$ 当且仅当顶点 $v_i$ 与边 $e_j$ 关联。

性质

$A^k$ 的 $(i,j)$ 元等于从 $v_i$ 到 $v_j$ 长度为 $k$ 的途径数，因此可用矩阵幂计算路径数，并由此比较图的结构（见图的同构）。

示例

路径图 $v_1-v_2-v_3$ 的邻接矩阵为

$$\begin{pmatrix}0&1&0\\1&0&1\\0&1&0\end{pmatrix}$$

其平方的 $(1,3)$ 元为 $1$，即 $v_1$ 到 $v_3$ 恰有 $1$ 条长度为 $2$ 的途径。