6.3
测试：a + b = c ### ==6.3 图的矩阵表示==
矩阵是图的一种重要代数表示，它将图的拓扑结构转化为数值阵列，便于利用代数工具（如矩阵乘法、特征值）分析图的路径与连通性质。本节涵盖四种核心矩阵。
==🔷 6.3.1 无向图的关联矩阵==
定义：设无向图 G = ⟨V, E⟩，其中 V = {v1, v2, …, vn}，E = {e1, e2, …, em}。定义矩阵 M(G) = (mij)n × m，其中 mij 是顶点 vi 与边 ej 的关联次数（取值为 0, 1, 2）。
- 示例矩阵： $$ \Large \left[ \begin{array}{c|rrrrr} & e_1 & e_2 & e_3 & e_4 & e_5 \\ \hline v_1 & 1 & 1 & 1 & 0 & 0 \\ v_2 & 0 & 1 & 1 & 1 & 0 \\ v_3 & 1 & 0 & 0 & 1 & 2 \\ v_4 & 0 & 0 & 0 & 0 & 0 \\ \end{array} \right] $$
| 性质 | 说明 |
|---|---|
| ① 列特征 | 每列恰有两个 1 或一个 2（环对应 2）。 |
| ② 行和 | 第 i 行元素之和 = d(vi)（顶点度数）。 |
| ③ 总和 | 全体元素之和 = 2m（握手定理的矩阵体现）。 |
| ④ 孤立点 | vi 为孤立点 ⇔ 第 i 行全为 0。 |
| ⑤ 平行边 | ej 与 ek 为平行边 ⇔ 第 j 列与第 k 列完全相同。 |
==🔷 6.3.2 有向图的关联矩阵==
定义：设无环有向图 D = ⟨V, E⟩，定义矩阵 M(D) = (mij)n × m，其中： - mij = 1，若 vi 为 ej 的 始点； - mij = −1，若 vi 为 ej 的 终点； - mij = 0，若 vi 与 ej 不关联。
- 示例矩阵： $$ \Large \left[ \begin{array}{c|rrrrr} & e_1 & e_2 & e_3 & e_4 & e_5 \\ \hline v_1 & 1 & -1 & 0 & 0 & 0 \\ v_2 & 0 & 1 & 1 & -1 & 0 \\ v_3 & -1 & 0 & -1 & 1 & 1 \\ v_4 & 0 & 0 & 0 & 0 & -1 \\ \end{array} \right] $$
| 性质 | 说明 |
|---|---|
| ① 列特征 | 每列恰有一个 1 和一个 −1。 |
| ② 出度与入度 | 第 i 行 1 的个数 = d+(vi)；−1 的个数 = d−(vi)。 |
| ③ 总和 | 全体 1 的个数 = 全体 −1 的个数 = m。 |
==🔷 6.3.3 有向图的邻接矩阵== ⭐
定义：设 D = ⟨V, E⟩，|V| = n。邻接矩阵 A(D) = (aij(1))n × n，其中 aij(1) 是从 vi 到 vj 的有向边条数。
示例矩阵： $$ \Large \left[ \begin{array}{c|cccc} & v_1 & v_2 & v_3 & v_4 \\ \hline v_1 & 1 & 0 & 0 & 0 \\ v_2 & 2 & 0 & 1 & 0 \\ v_3 & 1 & 0 & 0 & 1 \\ v_4 & 1 & 0 & 1 & 0 \\ \end{array} \right] $$
基本性质：
第 i 行和 = d+(vi)，第 j 列和 = d−(vj)。
元素总和 = m（长度为 1 的通路总数）。
定理 6.5（邻接矩阵的幂）
设 A 为 n 阶有向图 D 的邻接矩阵，则 Al（l ≥ 1）中的元素具有明确的组合意义： - aij(l)：从 vi 到 vj 长度为 l 的通路数目。 - aii(l)：从 vi 到自身长度为 l 的回路数目。 - $\sum_{i=1}^{n}\sum_{j=1}^{n} a_{ij}^{(l)}$：图中长度为 l 的通路总数。 - $\sum_{i=1}^{n} a_{ii}^{(l)}$：图中长度为 l 的回路总数。
推论：令 Br = A + A2 + … + Ar，则 Br 中的元素 bij(r) 表示从 vi 到 vj 长度不超过 r 的通路数。
- 📊 计算示例（基于示例矩阵）：
| 长度 l | 通路总数 | 回路总数 |
|---|---|---|
| 1 | 8 | 1 |
| 2 | 11 | 3 |
| 3 | 14 | 1 |
| 4 | 17 | 3 |
| ≤4 | 50 | 8 |
==🔷 6.3.4 有向图的可达矩阵==
定义：设 D = ⟨V, E⟩，V = {v1, …, vn}。可达矩阵 P(D) = (pij)n × n，其中： - pij = 1，若 vi 可达 vj（存在 vi 到 vj 的通路）； - pij = 0，否则。
- 示例矩阵： $$ \Large \left[ \begin{array}{c|rrrr} & v_1 & v_2 & v_3 & v_4 \\ \hline v_1 & 1 & 1 & 1 & 1 \\ v_2 & 0 & 1 & 1 & 1 \\ v_3 & 0 & 0 & 1 & 1 \\ v_4 & 0 & 0 & 1 & 1 \\ \end{array} \right] $$
| 性质 | 说明 |
|---|---|
| ① 对角线 | 主对角线元素恒为 1（每个顶点自身可达）。 |
| ② 强连通判定 | D 为强连通图 ⇔ P(D) 中所有元素均为 1。 |
==🔷作业==
- P138 5.18：练习关联矩阵、邻接矩阵与可达矩阵的构造与计算。