本节对应原书 PDF 第 159–164 页。定义、定理、公式、例题及其原解答逐字取自原书；解释性文字为 AI 通俗化改写；标有「解读」的引用块为 AI 补充的额外直觉。

从以上的讨论可知,一个图可以用集合来表示,也可以用图形来表示. 另外还可以用矩阵来表示,这便于用代数方法来研究图的性质,也便于用计算机来处理图. 用矩阵表示图,必须将图的顶点和边编号. 在本节中,主要讨论图的关联矩阵,有向图的邻接矩阵,无向图的相邻矩阵,以及可达矩阵.

6.3.1 无向图的关联矩阵

设无向图 G=\langle V,E\rangle,V=\{v_1,v_2,\cdots,v_n\},E=\{e_1,e_2,\cdots,e_m\},令 m_{ij} 为顶点 v_i 与边 e_j 的关联次数,则称 (m_{ij})_{n\times m} 为 G 的关联矩阵,记作 M(G).

m_{ij} 的可能取值有 3 种：0(v_i 与 e_j 不关联),1(v_i 与 e_j 关联次数为 1),2(v_i 与 e_j 关联次数为 2,即 e_j 是以 v_i 为端点的环).

例 6.8 求图 6.15 所示无向图的关联矩阵.

解 设图 6.15 所示为 G,它的关联矩阵为

M(G)=\begin{pmatrix}1&1&1&0&0&0\\0&1&1&0&1&0\\0&0&0&1&1&0\\1&0&0&1&0&2\end{pmatrix}

原书图6.15

图 6.15

通过对 M(G) 的分析,可以看出关联矩阵 (m_{ij})_{n\times m} 有下面诸条性质：

(1) \sum_{i=1}^{n}m_{ij}=2(j=1,2,\cdots,m),即 M(G) 各列元素之和为 2,这正说明每条边关联两个顶点(环关联的两个顶点重合).

(2) \sum_{j=1}^{m}m_{ij}=d(v_i),即 M(G) 第 i 行元素之和为 v_i 的度数,i=1,2,\cdots,n.

(3) \sum_{i=1}^{n}d(v_i)=\sum_{i=1}^{n}\sum_{j=1}^{m}m_{ij}=\sum_{j=1}^{m}\sum_{i=1}^{n}m_{ij}=\sum_{j=1}^{m}2=2m,这正是握手定理的内容——各顶点度数之和等于边数的 2 倍.

(4) 第 j 列与第 k 列相同,当且仅当 e_j 与 e_k 是平行边.

(5) \sum_{j=1}^{m}m_{ij}=0,当且仅当顶点 v_i 为孤立点.

解读：关联矩阵是「顶点×边」的表格，每列恰好合计 2（环在这一列上写 2），所以行和就是度数——这正是握手定理在矩阵语言里的样子。

6.3.2 有向无环图的关联矩阵

设有向无环图 D=\langle V,E\rangle,V=\{v_1,v_2,\cdots,v_n\},E=\{e_1,e_2,\cdots,e_m\}. 令

m_{ij}=\begin{cases}1&v_i\text{ 为 }e_j\text{ 的始点}\\0&v_i\text{ 与 }e_j\text{ 不关联}\\-1&v_i\text{ 是 }e_j\text{ 的终点}\end{cases}

则称 (m_{ij})_{n\times m} 为 D 的关联矩阵,记作 M(D).

例 6.9 求图 6.16 所示有向无环图 D 的关联矩阵.

解

M(D)=\begin{pmatrix}-1&1&0&0&0&-1&1\\0&-1&1&0&0&0&0\\0&0&-1&-1&-1&1&-1\\1&0&0&1&1&0&0\end{pmatrix}

原书图6.16

图 6.16

容易看出 M(D) 有如下性质：

(1) 每列恰好有一个 1 和一个 -1,这是因为每条边有一个始点和一个终点(注意,规定图中无环).

(2) 1 的总个数等于 -1 的总个数,等于边数. 这是定理 6.1 的内容.

(3) 第 i 行中 1 的个数等于 v_i 的出度,-1 的个数等于 v_i 的入度.

(4) 第 j 列和第 k 列相同当且仅当 e_j 和 e_k 是平行边.

(5) 第 i 行全为 0 当且仅当 v_i 是孤立点.

解读：有向图用 +1/-1 区分始点与终点，于是「行里 1 的个数」直接读出出度、「-1 的个数」直接读出入度；规定无环，就是为了保证每列 1 与 -1 各恰好一个。

6.3.3 有向图的邻接矩阵

设有向图 D=\langle V,E\rangle,V=\{v_1,v_2,\cdots,v_n\},|E|=m. 令 a_{ij}^{(1)} 为顶点 v_i 邻接到顶点 v_j 的边的条数,称 (a_{ij}^{(1)})_{n\times n} 为 D 的邻接矩阵,记作 A(D).

例 6.10 求如图 6.17 所示有向图 D 的邻接矩阵.

解

A(D)=\begin{pmatrix}1&2&1&0\\0&0&1&0\\0&0&0&1\\0&0&1&0\end{pmatrix}

原书图6.17

图 6.17

邻接矩阵有如下诸条性质：

(1) \sum_{j=1}^{n}a_{ij}^{(1)}=d^+(v_i). 这说明第 i 行元素之和为 v_i 的出度,i=1,2,\cdots,n. 进而,

\sum_{i=1}^{n}\sum_{j=1}^{n}a_{ij}^{(1)}=\sum_{i=1}^{n}d^+(v_i)=m

这说明各顶点的出度之和为 D 中边数 m.

(2) \sum_{i=1}^{n}a_{ij}^{(1)}=d^-(v_j). 这说明第 j 列元素之和为 v_j 的入度,j=1,2,\cdots,n. 同样,

\sum_{j=1}^{n}\sum_{i=1}^{n}a_{ij}^{(1)}=\sum_{j=1}^{n}d^-(v_j)=m

这说明各顶点的入度之和为 D 中边数.

可以利用 A(D) 计算 D 的各种长度的通路和回路数. 需要说明的是,这里不是在同构意义下,而是在定义意义下计算通路和回路数. 2 条通路或回路,只要表示它们的点边序列(或点序列,边序列)不同,就认为它们是不同的. 特别地,图形中的一条回路以不同的顶点作为始点和终点,在定义意义下认为它们是不同的. 如在图 6.17 中,v_2v_4v_2 和 v_4v_2v_4 在定义意义下是 2 条回路,而在图形中它们是一个回路. 对于通路,它在图形中的表示和定义意义下的表示是一致的. 如 e_2e_5 和 e_3e_5 是 2 条从 v_1 到 v_3 的长度为 2 的通路. 而在同构意义下,给定长度的通路和回路都只有一条. 在下面的叙述中把回路包含在通路中.

定理 6.6 设 A 为有向图 D 的邻接矩阵,D 的顶点集 V=\{v_1,v_2,\cdots,v_n\},则 A^l(l\geqslant 1) 的元素 a_{ij}^{(l)} 是 v_i 到 v_j 长度为 l 的通路数,\sum_{i,j}a_{ij}^{(l)} 是 D 中长度为 l 的通路总数,其中 \sum_{i}a_{ii}^{(l)} 是 D 中长度为 l 的回路总数.

证明 只需证明 a_{ij}^{(l)} 是 v_i 到 v_j 长度 l 的通路数. 对 l 做归纳证明.

归纳基础：当 l=1 时,长度为 l 的通路是一条边,由邻接矩阵的定义,结论成立.

归纳步骤：假设当 l\geqslant 1 时结论成立,考虑 v_i 到 v_j 长度为 l+1 的通路数. 一条 v_i 到 v_j 长度为 l+1 的通路由 v_i 到某个 v_k 长度为 l 的通路和边 (v_k,v_j) 构成. 根据归纳假设,a_{ik}^{(l)} 是 v_i 到 v_k 长度为 l 的通路数,而 a_{kj}^{(1)} 是 v_k 到 v_j 的边数. 于是,a_{ik}^{(l)}\cdot a_{kj}^{(1)} 是 v_i 到 v_k 再加一条边到 v_j 长度为 l+1 的通路数,从而 v_i 到 v_j 长度为 l+1 的通路数等于

\sum_{k}a_{ik}^{(l)}\cdot a_{kj}^{(1)}=a_{ij}^{(l+1)}

即,对 l+1 结论也成立.

推论 设 B_l=A+A^2+\cdots+A^l(l\geqslant 1),则 B_l 的元素 b_{ij}^{(l)} 是 D 中 v_i 到 v_j 长度小于等于 l 的通路数,\sum_{i,j}b_{ij}^{(l)} 是 D 中长度小于等于 l 的通路总数,其中 \sum_{i}b_{ii}^{(l)} 是 D 中长度小于等于 l 的回路总数.

解读：定理 6.6 只是矩阵乘法的定义在说话——a_{ij}^{(l+1)}=\sum_k a_{ik}^{(l)}a_{kj}^{(1)} 逐项枚举「先走 l 步到 v_k，再走一条边到 v_j」，所以幂矩阵的元素天然就是通路条数。

例 6.10(续) 在图 6.17 中

(1) v_1 到 v_4,v_1 到 v_1 长度为 3 的通路各为多少条?

(2) v_1 到自身长度为 1,2,3,4 的回路各为多少条?

(3) 长度为 4 的通路总数为多少条? 其中有多少条是回路?

(4) 长度小于等于 4 的回路有多少条?

解 根据定理 6.6,只需写出 D 的邻接矩阵 A 的前 4 次幂.

A=\begin{pmatrix}1&2&1&0\\0&0&1&0\\0&0&0&1\\0&0&1&0\end{pmatrix}\qquad A^2=\begin{pmatrix}1&2&3&1\\0&0&0&1\\0&0&1&0\\0&0&0&1\end{pmatrix}
A^3=\begin{pmatrix}1&2&4&3\\0&0&1&0\\0&0&0&1\\0&0&1&0\end{pmatrix}\qquad A^4=\begin{pmatrix}1&2&6&4\\0&0&0&1\\0&0&1&0\\0&0&0&1\end{pmatrix}

(1) v_1 到 v_4,v_1 到 v_1 长度为 3 的通路数由 A^3 中 a_{14}^{(3)}=3 和 a_{11}^{(3)}=0 给出,即分别为 3 条和 0 条.

(2) v_1 到 v_1 长度为 1,2,3,4 的回路数分别为 a_{11}^{(1)}=1,a_{11}^{(2)}=1,a_{11}^{(3)}=1,a_{11}^{(4)}=1 给出,即都是 1 条.

(3) D 中长度为 4 的通路总数为 A^4 中全体元素之和 \sum_{i=1}^{4}\sum_{j=1}^{4}a_{ij}^{(4)}=16 给出,即 16 条,其中回路数为 \sum_{i=1}^{4}a_{ii}^{(4)}=3 给出,即 3 条.

(4) D 中长度小于等于 4 的回路数为 \sum_{l=1}^{4}\sum_{i=1}^{4}a_{ii}^{(l)},其结果为 1+3+1+3=8.

6.3.4 有向图的可达矩阵

设有向图 D=\langle V,E\rangle,其中 V=\{v_1,v_2,\cdots,v_n\},令

p_{ij}=\begin{cases}1&\text{若 }v_i\text{ 可达 }v_j\\0&\text{否则}\end{cases}\qquad 1\leqslant i,j\leqslant n

称 (p_{ij})_{n\times n} 为 D 的可达矩阵,记作 P(D),简记 P.

有向图的可达矩阵有下述性质：

(1) 主对角线上的元素全为 1,即 p_{ii}=1,1\leqslant i\leqslant n.

(2) D 是强连通的当且仅当 P(D) 的元素全为 1.

(3) 根据定理 6.3,p_{ij}=1 当且仅当 b_{ij}^{(n-1)}\neq 0,1\leqslant i,j\leqslant n 且 i\neq j.

例 6.10(续) 写出图 6.17 的可达矩阵,并问：它是强连通的吗?

解

B_3=A+A^2+A^3=\begin{pmatrix}3&6&8&4\\0&0&2&1\\0&0&1&2\\0&0&2&1\end{pmatrix}

由性质(1)和(3),得

P=\begin{pmatrix}1&1&1&1\\0&1&1&1\\0&0&1&1\\0&0&1&1\end{pmatrix}

该图不是强连通的,但由 P 可以看出,它是单向连通的.

类似地,无向图也有相邻矩阵和可达矩阵. 设无向简单图 G=\langle V,E\rangle,其中 V=\{v_1,v_2,\cdots,v_n\},令 a_{ij}^{(1)} 为顶点 v_i 与 v_j 之间边的条数,称 (a_{ij}^{(1)})_{n\times n} 为 G 的相邻矩阵,记作 A(G).

令

p_{ij}=\begin{cases}1&\text{若 }v_i\text{ 可达 }v_j\\0&\text{否则}\end{cases}\qquad 1\leqslant i,j\leqslant n

称 (p_{ij})_{n\times n} 为 G 的可达矩阵,记作 P(G),简记作 P.

A(G) 和 P(G) 都是对称的. 与有向图的邻接矩阵类似,也可以用相邻矩阵的幂求 G 中各种长度的通路数和回路数.

例 6.11 写出图 6.18 所示无向图 G 的相邻矩阵,并求 v_1 到 v_2 长度为 3 的通路数和 v_1 到 v_1 长度为 3 的回路数.

解 G 的相邻矩阵

A=\begin{pmatrix}0&1&0&1\\1&0&1&1\\0&1&0&0\\1&1&0&0\end{pmatrix}

原书图6.18

图 6.18

计算

A^2=\begin{pmatrix}2&1&1&1\\1&3&0&1\\1&0&1&1\\1&1&1&2\end{pmatrix}\qquad A^3=\begin{pmatrix}2&4&1&3\\4&2&3&4\\1&3&0&1\\3&4&1&2\end{pmatrix}

由 a_{12}^{(3)}=3,v_1 到 v_2 长度为 3 的通路有 3 条,它们是 v_1v_2v_1v_2,v_1v_2v_3v_2,v_1v_4v_1v_2. 由 a_{11}^{(3)}=2,v_1 到 v_1 长度为 3 的回路有 2 条,它们是 v_1v_2v_4v_1,v_1v_4v_2v_1. 这 2 条回路在图中是一条回路.

解读：可达矩阵可以看作「邻接矩阵幂的定性版」：只要 v_i 到 v_j 在 n-1 步内走得通（由定理 6.3 保证），对应位置就记 1；主对角线全为 1 是因为约定每个顶点到自身总是可达的。