Chap9 图的矩阵表示

返回：0100 离散数学课程总目录 · 上一章：0108 树 · 下一章：0110 平面图

1、资料来源与学习目标

本章对应北大离散数学刘田老师“集合论与图论”第九章，课件实际标题是“第十章图的矩阵表示”。Auto_Tutor 中整理到的资料包括：

资料	内容
9.1 图的矩阵表示	有向图关联矩阵、无向图关联矩阵、基本关联矩阵、生成树判定、邻接矩阵、矩阵幂、可达矩阵、相邻矩阵、连通矩阵
009 习题与答案	习题 10.2、10.4，重点考察基本关联矩阵求生成树、邻接矩阵幂求通路与回路数量

本章的核心目标：把“图的结构问题”翻译成矩阵计算问题。关联矩阵服务于连通性和生成树，邻接矩阵服务于通路计数，可达矩阵和连通矩阵服务于可达性判断。

2、颜色标注

颜色	含义
粉色	必背定理、矩阵算法、习题直接使用的结论
蓝色	核心术语、矩阵名、图论对象
橙色	易错点、适用条件、下标方向
绿色	理解提示和操作步骤

3、章节主线

模块	本章要会什么	典型题型
关联矩阵	会按边和顶点写 `M(D)`、`M(G)`	判断度数、平行边、连通分支
基本关联矩阵	会删参考点行得到 `M_f(G)`	用行列式判定生成树
邻接矩阵	会从有向图写 `A(D)`	用行和列和求出度入度
矩阵幂	会用 `A^r` 统计长度为 `r` 的通路	通路数、回路数、距离
可达矩阵	会由 `B_{n-1}` 判断可达性	强连通判定
相邻矩阵	会写无向简单图的 `A(G)`	度数、通路数、连通矩阵

4、关联矩阵

4.1 有向图关联矩阵

设 D=<V,E> 是无环有向图：

1 2	V={v1,v2,...,vn} E={e1,e2,...,em}

有向图的关联矩阵：

1	M(D)=[m_ij]_{n*m}

其中：

1
2
3

m_ij =  1   vi 是 ej 的起点
m_ij = -1   vi 是 ej 的终点
m_ij =  0   vi 与 ej 不关联

这里的符号方向要记清：起点记 1，终点记 -1。有些教材会反过来约定，做题时以课件定义为准。

有向图关联矩阵性质：

每列和为 0：
sum_i m_ij = 0

每行绝对值和为该顶点度数：
d(v_i)=sum_j |m_ij|

每行中 1 的个数为出度 d+(v_i)，-1 的个数为入度 d-(v_i)。

握手定理：
sum_i sum_j m_ij = 0

如果两条有向边平行，并且方向也相同，那么它们在关联矩阵中对应相同两列。

4.2 无向图关联矩阵

设 G=<V,E> 是无环无向图：

1 2	V={v1,v2,...,vn} E={e1,e2,...,em}

无向图的关联矩阵：

1	M(G)=[m_ij]_{n*m}

其中：

1 2	m_ij = 1 vi 与 ej 关联 m_ij = 0 vi 与 ej 不关联

无向图关联矩阵性质：

每列和为 2：
sum_i m_ij = 2

所有元素总和为 2m：
sum_i sum_j m_ij = 2m

每行和为顶点度：
d(v_i)=sum_j m_ij

平行边对应相同两列。

若图有多个连通分支，适当排列顶点和边后，关联矩阵会呈现伪对角块：

1	M(G)=diag(M(G1), M(G2), ..., M(Gk))

每个对角块对应一个连通分支。

从“矩阵角度”看连通分支，就是矩阵能不能被整理成多个互不影响的对角块。

5、基本关联矩阵与生成树

5.1 基本关联矩阵

无向图基本关联矩阵：

1
2
3

任选一个顶点作为参考点；
从 M(G) 中删除参考点对应的行；
得到 M_f(G)。

这里 f 可以理解为 fundamental。

5.2 秩与连通性

定理 10.1：

1	若 G 连通，则 r(M(G))=n-1。

定理 10.2：

1	若 G 连通，则 r(M_f(G))=n-1。

推广到非连通图：

1 2	若 G 有 p 个连通分支，则 r(M_f(G))=n-p。

其中 M_f(G) 是从 M(G) 的每个对角块中删除任意一行后得到的矩阵。

推论：

1	G 连通 ⇔ r(M(G))=r(M_f(G))=n-1。

课件中秩的结论针对无向图关联矩阵，并注明在 F={0,1} 上讨论。复盘时重点记结果，不要把它直接套到任意实矩阵约定里。

5.3 用基本关联矩阵判定生成树

定理 10.3：

设 G 是连通图，M_f(G) 是基本关联矩阵。从 M_f(G) 中任取 n-1 列组成方阵 M_f'，这些列对应边集：

1	{e_i1, e_i2, ..., e_i(n-1)}

设 T 是由这些边导出的生成子图，则：

1	T 是 G 的生成树 ⇔ det(M_f') != 0。

操作步骤：

1. 忽略环，写出关联矩阵 M(G)。
2. 任选参考点，删除该行，得到基本关联矩阵 M_f(G)。
3. 枚举所有 n-1 阶子方阵。
4. 计算行列式。
5. 行列式非 0 的边集，就是生成树。

这条定理把第 8 章的“生成树问题”变成了矩阵的“选列 + 求行列式”问题。

6、有向图邻接矩阵与通路计数

6.1 有向图邻接矩阵

设 D=<V,E> 是有向图，V={v1,v2,...,vn}。

有向图邻接矩阵：

1 2	A(D)=[a_ij]_{n*n} a_ij = 从 vi 到 vj 的边数

性质：

第 i 行和 = v_i 的出度 d+(v_i)
第 j 列和 = v_j 的入度 d-(v_j)
所有元素总和 = 边数 m
主对角线元素总和 = 环个数

邻接矩阵最常见的下标错误是把方向看反。课件约定是：行表示起点，列表示终点，所以 a_ij 是 vi -> vj 的边数。

6.2 邻接矩阵幂

设：

1 2	A^r = [a_ij^(r)] B_r = A + A^2 + ... + A^r = [b_ij^(r)]

定理 10.4：

1	a_ij^(r) = 从 vi 到 vj 长度为 r 的通路总数。

于是：

1 2	sum_i sum_j a_ij^(r) = 长度为 r 的通路总数 sum_i a_ii^(r) = 长度为 r 的回路总数

推论：

1
2
3

b_ij^(r) = 从 vi 到 vj 长度 <= r 的通路总数
sum_i sum_j b_ij^(r) = 长度 <= r 的通路总数
sum_i b_ii^(r) = 长度 <= r 的回路总数

证明思路是归纳法：

r=1 时，A 本身就是边数矩阵。

假设 A^k 已经能统计长度为 k 的通路。
长度 k+1 的通路可以看成：
vi --长度 k--> vt --长度 1--> vj

所以：
a_ij^(k+1)=sum_t a_it^(k) * a_tj

这正好就是矩阵乘法。

7、可达矩阵

有向图可达矩阵：

1
2
3

P(D)=[p_ij]_{n*n}
p_ij = 1   从 vi 可达 vj
p_ij = 0   从 vi 不可达 vj

性质：

1
2
3

主对角线元素都是 1。
强连通图的可达矩阵全为 1。
若 i != j，则 p_ij=1 ⇔ b_ij^(n-1)>0。

为什么只需要看 n-1：

1 2	如果 vi 能到 vj，总能找到一条不重复顶点的路；在 n 个顶点中，不重复顶点的路长度最多为 n-1。

8、无向图相邻矩阵与连通矩阵

8.1 无向图相邻矩阵

设 G=<V,E> 是无向简单图，V={v1,v2,...,vn}。

无向图相邻矩阵：

A(G)=[a_ij]_{n*n}

a_ii = 0

a_ij = 1   vi 与 vj 相邻，i != j
a_ij = 0   vi 与 vj 不相邻

性质：

A(G) 对称：
a_ij = a_ji

每行或每列的和为顶点度：
d(v_i)=sum_j a_ij

所有元素总和：
sum_i sum_j a_ij = 2m

8.2 相邻矩阵幂

设：

1 2	A^r=[a_ij^(r)] B_r=A+A^2+...+A^r

定理 10.5：

1 2	a_ij^(r) = 从 vi 到 vj 长度为 r 的通路总数。 sum_i a_ii^(r) = 长度为 r 的回路总数。

推论：

a_ii^(2)=d(v_i)

若 G 连通：
d(v_i,v_j)=min{r | a_ij^(r) != 0}

无向图里 A^r 统计的是长度为 r 的通路。由于无向边可以来回走，A^2 的对角线自然会数到“从顶点出发走一条边再走回来”的次数，所以 a_ii^(2)=d(v_i)。

8.3 连通矩阵

无向图连通矩阵：

1
2
3

P(G)=[p_ij]_{n*n}
p_ij = 1   vi 与 vj 连通
p_ij = 0   vi 与 vj 不连通

性质：

1
2
3

主对角线元素都是 1。
连通图的连通矩阵全为 1。
若 i != j，则 p_ij=1 ⇔ b_ij^(n-1)>0。

如果图有多个连通分支，适当重排顶点后，连通矩阵也会成为伪对角阵，每个对角块对应一个连通分支。

9、一页公式表

对象	矩阵	关键结论
有向图关联矩阵	`M(D)`	每列和为 `0`；行中 `1` 数出度，`-1` 数入度
无向图关联矩阵	`M(G)`	每列和为 `2`；每行和为顶点度
基本关联矩阵	`M_f(G)`	`G` 连通时 `r(M_f)=n-1`
生成树判定	`M_f'`	`det(M_f') != 0` iff 对应边集为生成树
有向图邻接矩阵	`A(D)`	行和为出度，列和为入度
矩阵幂	`A^r`	`a_ij^(r)` 统计长度为 `r` 的通路
累加矩阵	`B_r`	`b_ij^(r)` 统计长度 `<=r` 的通路
可达矩阵	`P(D)`	强连通 iff 全 `1`
无向图相邻矩阵	`A(G)`	对称；行和为度；`a_ii^(2)=d(v_i)`
连通矩阵	`P(G)`	连通 iff 全 `1`

10、习题与答案

习题 10.2：利用基本关联矩阵求所有生成树

题目给出的图有 5 个顶点、6 条边：

e1: v1-v4
e2: v2-v4
e3: v2-v3
e4: v1-v2
e5: v3-v4
e6: v4-v5

写出无向图关联矩阵：

        e1 e2 e3 e4 e5 e6
v1      1  0  0  1  0  0
v2      0  1  1  1  0  0
v3      0  0  1  0  1  0
v4      1  1  0  0  1  1
v5      0  0  0  0  0  1

以 v5 为参考点，删除 v5 所在行，得到基本关联矩阵：

        e1 e2 e3 e4 e5 e6
v1      1  0  0  1  0  0
v2      0  1  1  1  0  0
v3      0  0  1  0  1  0
v4      1  1  0  0  1  1

因为图有 n=5 个顶点，所以每棵生成树要选 n-1=4 条边。

普通枚举要计算：

C(6,4)=15

个 4 阶子方阵的行列式。但 e6 是桥，任何生成树都必须包含 e6，所以只需要从其余 5 条边里再选 3 条：

C(5,3)=10

答案中计算这些 4 阶子方阵后，有 2 个行列式为 0，其余 8 个非 0，所以共有 8 棵生成树。

所有生成树对应边集如下：

编号	生成树边集
a	`{e1,e2,e3,e6}`
b	`{e1,e2,e5,e6}`
c	`{e1,e3,e4,e6}`
d	`{e1,e3,e5,e6}`
e	`{e1,e4,e5,e6}`
f	`{e2,e3,e4,e6}`
g	`{e2,e4,e5,e6}`
h	`{e3,e4,e5,e6}`

答案：图 G 的生成树共有 8 棵，如上表所列。

习题 10.4：用邻接矩阵幂求通路和回路

题目给出有向图 D，答案中使用的邻接矩阵为：

计算：

为了统计长度小于等于 r 的通路，令：

1	B_r = A + A^2 + ... + A^r

于是：

逐问答案如下：

问题	读矩阵位置	答案
1. `v1` 到 `v4` 长度为 `1,2,3,4` 的通路数	`A,A^2,A^3,A^4` 的 `(1,4)` 元	`0,0,2,2`
2. `v1` 到 `v4` 长度 `<=3` 的通路数	`B3` 的 `(1,4)` 元	`2`
3. `v1` 到 `v1` 长度为 `1,2,3,4` 的回路数	`A,A^2,A^3,A^4` 的 `(1,1)` 元	`1,1,3,5`
4. `v4` 到 `v4` 长度 `<=3` 的回路数	`B3` 的 `(4,4)` 元	`1`
5. `D` 中长度为 `4` 的通路，不含回路	`A^4` 总和减迹	`33`
6. `D` 中长度为 `4` 的回路	`A^4` 的迹	`11`
7. `D` 中长度 `<=4` 的通路及回路	`B4` 总和与迹	通路 `88` 条，其中回路 `22` 条
8. `D` 的可达矩阵	每个顶点均可达每个顶点	全 `1` 矩阵

可达矩阵：

因此 D 是强连通图。

第 5 问说“不含回路”的长度 4 通路，所以要用 A^4 的所有元素总和减去主对角线和。这里 A^4 总和为 44，主对角线和为 11，所以答案是 44-11=33。

11、易错点

易错点	正确处理
有向图邻接矩阵下标方向写反	`a_ij` 表示 `vi -> vj` 的边数
有向图关联矩阵正负号混乱	本课件中起点为 `1`，终点为 `-1`
无向图关联矩阵套到有环图	本章定义默认无环；环要先忽略或单独处理
生成树枚举忘记桥	桥必在每棵生成树中，可减少枚举
把通路数和回路数混在一起	通路总数看全矩阵元素和，回路总数看迹
可达矩阵只看 `A`	要看 `A+A^2+...+A^(n-1)` 是否出现正数

12、复盘清单

学完本章后，至少要能做到：

1. 给定有向图，写出 M(D) 和 A(D)。
2. 给定无向图，写出 M(G)、M_f(G)、A(G)。
3. 解释为什么连通图的基本关联矩阵秩为 n-1。
4. 用 det(M_f') != 0 判断一组 n-1 条边是否构成生成树。
5. 用 A^r 的元素读出长度为 r 的通路数。
6. 用 trace(A^r) 读出长度为 r 的回路数。
7. 用 B_r=A+...+A^r 统计长度不超过 r 的通路。
8. 写出可达矩阵和连通矩阵，并判断强连通或连通。