测试：$a+b=c$

==6.3 图的矩阵表示==

矩阵是图的一种重要代数表示，它将图的拓扑结构转化为数值阵列，便于利用代数工具（如矩阵乘法、特征值）分析图的路径与连通性质。本节涵盖四种核心矩阵。

==🔷 6.3.1 无向图的关联矩阵==

定义：设无向图 $G = \langle V, E \rangle$，其中 $V = {v1, v_2, \dots, v_n}$，$E = {e_1, e_2, \dots, e_m}$。定义矩阵 $\mathbf{M}(G) = (m{ij}){n \times m}$，其中 **$m{ij}$ 是顶点 $v_i$ 与边 $e_j$ 的关联次数**（取值为 $0, 1, 2$）。

  • 示例矩阵：
性质 说明
① 列特征 每列恰有两个 $1$ 或一个 $2$（环对应 $2$）。
② 行和 第 $i$ 行元素之和 = $\mathbf{d(v_i)}$（顶点度数）。
③ 总和 全体元素之和 = $2m$（握手定理的矩阵体现）。
④ 孤立点 $v_i$ 为孤立点 $\iff$ 第 $i$ 行全为 $0$。
⑤ 平行边 $e_j$ 与 $e_k$ 为平行边 $\iff$ 第 $j$ 列与第 $k$ 列完全相同。

==🔷 6.3.2 有向图的关联矩阵==

定义：设无环有向图 $D = \langle V, E \rangle$，定义矩阵 $\mathbf{M}(D) = (m{ij}){n \times m}$，其中：

  • $m_{ij} = 1$，若 $v_i$ 为 $e_j$ 的 始点；
  • $m_{ij} = -1$，若 $v_i$ 为 $e_j$ 的 终点；
  • $m_{ij} = 0$，若 $v_i$ 与 $e_j$ 不关联。
  • 示例矩阵：
性质 说明
① 列特征 每列恰有一个 $1$ 和一个 $-1$。
② 出度与入度 第 $i$ 行 $1$ 的个数 = $d^+(v_i)$；$-1$ 的个数 = $d^-(v_i)$。
③ 总和 全体 $1$ 的个数 = 全体 $-1$ 的个数 = $m$。

==🔷 6.3.3 有向图的邻接矩阵== ⭐

定义：设 $D = \langle V, E \rangle$，$|V|=n$。邻接矩阵 $\mathbf{A}(D) = (a{ij}^{(1)}){n \times n}$，其中 $a_{ij}^{(1)}$ 是从 $v_i$ 到 $v_j$ 的有向边条数。

  • 示例矩阵：
  • 基本性质：
  • 第 $i$ 行和 = $d^+(v_i)$，第 $j$ 列和 = $d^-(v_j)$。
  • 元素总和 = $m$（长度为 $1$ 的通路总数）。

定理 6.5（邻接矩阵的幂）
设 $\mathbf{A}$ 为 $n$ 阶有向图 $D$ 的邻接矩阵，则 $\mathbf{A}^l$（$l \ge 1$）中的元素具有明确的组合意义：

  • $a_{ij}^{(l)}$：从 $v_i$ 到 $v_j$ 长度为 $l$ 的通路数目。
  • $a_{ii}^{(l)}$：从 $v_i$ 到自身长度为 $l$ 的回路数目。
  • $\sum{i=1}^{n}\sum{j=1}^{n} a_{ij}^{(l)}$：图中长度为 $l$ 的通路总数。
  • $\sum{i=1}^{n} a{ii}^{(l)}$：图中长度为 $l$ 的回路总数。

推论：令 $\mathbf{B}r = \mathbf{A} + \mathbf{A}^2 + \dots + \mathbf{A}^r$，则 $\mathbf{B}_r$ 中的元素 **$b{ij}^{(r)}$ 表示从 $v_i$ 到 $v_j$ 长度不超过 $r$** 的通路数。

  • 📊 计算示例（基于示例矩阵）：
长度 $l$ 通路总数 回路总数
1 8 1
2 11 3
3 14 1
4 17 3
≤4 50 8

==🔷 6.3.4 有向图的可达矩阵==

定义：设 $D = \langle V, E \rangle$，$V={v1,\dots,v_n}$。可达矩阵 $\mathbf{P}(D) = (p{ij})_{n \times n}$，其中：

  • $p_{ij} = 1$，若 $v_i$ 可达 $v_j$（存在 $v_i$ 到 $v_j$ 的通路）；
  • $p_{ij} = 0$，否则。
  • 示例矩阵：
性质 说明
① 对角线 主对角线元素恒为 $1$（每个顶点自身可达）。
② 强连通判定 $D$ 为强连通图 $\iff$ $\mathbf{P}(D)$ 中所有元素均为 $1$。

==🔷作业==

  • P138 5.18：练习关联矩阵、邻接矩阵与可达矩阵的构造与计算。