7-3 图的矩阵表示给定一个图 G=<V,E>，使用图形表示法很容易把图的结构展现出来，而且这种表示直观明了。
但这只在结点和边 (或弧 )的数目相当小的情况下才是可行的。显然这限制了图的利用。本节提供另一种图的表示法 —— 图的矩阵表示法。它不仅克服了图形表示法的不足，而且这种表示可以充分利用现代工具电子计算机，以达到研究图的目的。
一个简单图 G=<V,E>由 V中每两个结点间的邻接关系唯一地确定，这种关系可以用一个矩阵给出，
而矩阵形式与图中结点的编序有密切关系，这是用矩阵表示图值得注意的一点。
一、邻接矩阵定义 7-3.1 设 G=<V,E>是一个简单图，它有 n个结点 V={v1,v2,…vn},则 n阶方阵 A(G)=(aij)n× n称为 图 G的 邻接矩阵 (adjacency matrix) 。 其中：
1 vi adj vj
0 vi nadj vj 或 i=j
adj表示邻接,nadj表示不邻接。
aij=
0 1 0 0
A(G1)= 0 0 1 1
1 1 0 1
1 0 0 0
例如
0 1 1 1 1
1 0 1 0 0
A(G)= 1 1 0 1 0
1 0 1 0 1
1 0 0 1 0
无向图的邻接矩阵是对称矩阵，有向图的邻接矩阵不一定是对称的。
288页图
7-3,1
288页图
7-3,2
G1
288页图 7-3,2 G2
G2只是将 G1的两个结点 v1和 v2调换
0 0 1 1
1 0 0 0
A(G1)= 1 1 0 1
0 1 0 0
图 G2的邻接矩阵是将图 G1的邻接矩阵第一、
二行对调，第一、二列对调得到的。
对于给定图 G，显然不会因结点编序不同而使其结构发生任何变化，即图的结点所有不同的编序实际上仍表示同一个图。换句话说，这些结点的不同编序的图都是同构的，并且它们的邻接矩阵都是相似的。于是 G与 H同构?存在置换矩阵 P，
使 A(H)=P-1A(G)P，今后将略去这种由于 V中结点编序而引起邻接矩阵的任意性，而取该图的任一个邻接矩阵作为该图的矩阵表示。
邻接矩阵可展示相应图的一些性质：若邻接矩阵的元素全为零，则其对应的图是零图；
若 (无向图 )邻接矩阵的元素除主对角线元素外全为 1，则其对应的图是简单完全图。
(有向图 )邻接矩阵的元素除主对角线元素外全为 1，则其对应的图是有向完全图和强连通图。
当给定的简单图是无向图时，邻接矩阵是对称矩阵；反之，若给定任何对称矩阵 A，显然可以唯一地作出以 A为其邻接矩阵的简单图 G。于是，所有 n个结点的不同编序的简单图的集合与所有 n阶对称矩阵的集合可建立一一对应。
当给定的图是简单有向图时，其邻接矩阵并非一定是对称矩阵，但所有 n个结点的不同编序的简单图的集合，与所有 n阶邻接矩阵的集合亦可建立一一对应。
不仅如此，通过对矩阵元素的一些计算还可以得到对应图的某些数量的特征。
在给定简单有向图的邻接矩阵中，第 i行元素是由结点 vi出发的弧所确定，故第 i行中值为 1的元素数目等于结点 vi的出度。同理，第 j列中值为
1的元素数目等于结点 vj的入度。即 d+(vi)=
和 d-(vj)= 。
1
n
ik
k
a
1
n
kj
k
a
利用邻接矩阵计算长度为 k的路径条数,
按照普通 矩阵 乘法计算 n阶方阵 A(G)=(aij)n× n的 l次幂,所得乘积矩阵中的第 i行第 j列的元素,就是从结点 vi到结点 vj的长度为 l的路径条数。
(aij (l) )n× n= (A(G)) l =
a11 a12...a1n a11 a12...a1n a11 a12...a1n
a21 a22...a2n a21 a22...a2n … a21 a22...a2n
...,.,…,..,..,..,..,..,..
an1 an2...ann an1 an2...ann an1 an2...ann
共 l个
n
其中 aij (l) =? aik × akj (l-1)
k=1
.,,
例 290页例 1
定理 7-3.1 设 A(G)是图 G=<V,E>的邻接矩阵，则 (A(G))l中的 i
行 j列元素 aij (l)等于 G中联结 vi与 vj的长度为 l的路径条数。
证明思路：对 l用数学归纳法证明。
1) 当 l=1时,aij (2)等于 G中联结 vi与 vj的长度为 2的路径条数。
2)设命题对 l成立，即,aij (l)等于 G中联结 vi与 vj的长度为 l的路径条数。
3)现证 l+1时也成立。即 (A(G))l+1=(A(G)),(A(G))l
n
aij (l+1) =? aik × akj (l)
k=1
对 k求和即得结论。
vkvi vj
长度 =1
长度 =l
共 akj (l)条练习
300页（ 1）
求出图 7-3.9中有向图的邻接矩阵 A，找出从 v1到 v4长度为
2和 4的路，用计算 A2,A3,A4来验证这结论。
解
A=
0 1 0 1
0 0 1 1
0 1 0 1
0 1 0 0
0 1 1 1
0 2 0 1
0 2 1 1
0 0 1 1
A2=
0 2 1 2
0 2 2 2
0 2 1 2
0 2 0 1
A3=
0 4 2 3
0 4 1 3
0 4 2 3
0 2 2 2
A4=
从 v1到 v4长度为 2的路为 v1 v2 v4
从 v1到 v4长度为 4的路有,v1 v2 v4 v2 v4
v1 v2 v3 v2 v4 v1 v4 v2 4 v3 v4
在一些实际问题中，有时要判定图中结点 vi到结点 vj是否可达，或者说 vi到 vj是否存在路。如果利用图 G的邻接矩阵 A，则可计算 A2,A3,···,An,···。
当发现其中某个 Al的 aij(l)≥1，就表明 vi可达 vj或 vi到 vj
存在一条路。但这种计算繁琐量大，又不知计算 Al
到何时为止。
根据定理 7-2.1的推论可知，如果有向图 G有 n
个结点,vi到 vj有一条路，则必然有一条长度不大于 n的通路，因此，只需考虑 aij(l)就可以了，其中
1≤l≤n。即只要计算 Bn=A+A2+A3+···+An。
如果关心的是结点间可达性或结点间是否有路，
至于结点间的路存在多少条及长度是多少无关紧要，
那么便可用可达矩阵来表示结点间可达性。
二、、可达矩阵可达性矩阵的求法有两种：
1) 计算矩阵 Bn=A+A2+A3+…+A n
令矩阵 Bn中不为零的元素等于 1，为零的元素不变，
得到 P。 见例题 1。
2) 令 P =A∨ A(2) ∨ A(3) ∨ … ∨ A(n)
其中 A(i)(i=1,2,…,n) 为布尔矩阵。 见例题 2。
定义 7-3.2 设 G=<V,E>是一个简单有向图，它有 n
个已经编序的结点 V={v1,v2,…vn}，定义 n阶方阵
P(G)=(pij)n× n称为 图 G的 可达性矩阵 。 其中：
1 从 vi到 vj至少存在一条路。
0 从 vi到 vj不存在路。pij=
可见，可达矩阵表明了图中任意两结点间是否至少存在一条路以及在结点处是否有回路。
从图 G的邻接矩阵 A可以得到可达矩阵 P，即令
Bn=A+A2+A3+…+A n，再从 Bn中非零元素改为 1而零元素不变，这种变换后的矩阵即是可达矩阵 P。
练习：
300页（ 2）（ 3）
I = 1,2,3,……,n
第 i步：如果 A[ j,i]=1，则将第 i行加到第 j行。
（在具体计算中可以通过 Warshall算法实现）
300页（ 2） 如果 u可达 v，它们之间可能不止一条路，在所有这些路中，最短路的长度称为 u和 v之间的距离（或短程线），
记作 d<u,v>，如果从 u到 v是不可达的，则通常写成 d<u,v> =∞
距离矩阵为
0 1 2 1
∞ 0 1 1
∞ 1 0 1
∞ 1 2 0
dij=1表示存在边 <vi,vj>。
300页（ 3）
用 Warshall算法求可达性矩阵。
邻接矩阵为
0 0 0 0 0
1 0 1 1 0
1 0 0 0 0
0 0 1 0 0
0 0 0 0 0
A=
i=1时，因为 A的第一行全为 0，
所以 A不变。
i=2时，因为 A的第 2列全为 0，
所以 A不变。
i=3时，因为 A[2,3]=A[4,3]=0，将第 3
行加到第 2行和第 4行。
0 0 0 0 0
1 0 1 1 0
1 0 0 0 0
1 0 1 0 0
0 0 0 0 0
A,=
i=5时，因为 A的第 5列全为 0，所以 A不变。
0 0 0 0 0
1 0 1 1 0
1 0 0 0 0
1 0 1 0 0
0 0 0 0 0
P=
故 A的可达性矩阵为距离矩阵为
0 ∞ ∞ ∞ ∞
1 0 1 1 ∞
1 ∞ 0 ∞ ∞
2 ∞ 1 0 ∞
∞ ∞ ∞ ∞ 0
三、关联矩阵
1、无向图的关联矩阵举例 294页图 7-3.5
定义 7-3.3 给定无向 图 G=<V,E>,设 v1,v2,…,vp?V,
e1,…,eq?E,称 p× q阶矩阵 M (G)=(mij)p× q 为图 G的 完全关联矩阵 （ incidence matrix）。其中,
1 若 vi关联 ej。
0 若 vi不 关联 ej。mij=
无向图的关联矩阵 反映出来图的性质,
1) 每一条边关联两个结点,故每一列中只有两个 1。
2) 每一行中元素之和等于该行对应的结点度数。
3) 一行中元素全为 0，其对应结点为孤立点。
4) 两个平行边其对应的两列相同。
5) 同一个图当结点或边的编号不同时，其对应的矩阵只有行序列序的差别。
2、有向图的关联矩阵举例 294页图 7-3.6
定义 7-3.4 给定简单有向 图 G=<V,E>,设 v1,v2,…,
vp?V,e1,…,eq?E,称 p× q阶矩阵 M (G)=(mij)p× q 为图
G的 完全关联矩阵 (incidence matrix)。其中,
1 若 vi是 ej的起点 。
-1 若 vi是 ej的终点 。
0 若 vi不 关联 ej。
mij=
有向图的关联矩阵的特点：
(1)每一列中有一个 1和一个 -1，对应一边一个始点、一个终点，元素和为零。
(2)每一行元素的绝对值之和为对应点的度数。 -1
的个数等于入度,1的个数等于出度。
有向图 G的两行相加定义为：第 i行第 j列的对应元素 算术相加 ；相当于删除结点 vi与结点 vj之间的关联边，
合并结点 vi和 vj 。合并后得到的新结点记为 vi,j 。
无向图 G的两行相加定义为：第 i行第 j列的对应元素 模 2相加 ；相当于删除结点 vi与结点 vj之间的关联边，
合并结点 vi和 vj 。合并后得到的新结点记为 vi,j 。
3、关联矩阵的秩练习,
300页（ 4）
定理 7-3.2 如果一个连通 图 G=<V,E>,有个 r结点,
则其完全关联矩阵 M(G)的秩为 r-1,即 rank M (G)=r-1 。
证明思路,只对无向图证明利用线性代数中矩阵的初等（行、列）变换不改变矩阵的秩的结论和方法。
定理 7-3.2的推论 如果一个连通 图 G=<V,E>,有个 r结点,w个最大连通子图,则图 G的完全关联矩阵
M(G)的秩为 r- w,即 rank M (G)=r-w 。
300页（ 4）
写出如图 7-3.11所示的图 G的完全关联矩阵，并验证其秩如定理 7-3.2所述。
e1 e2 e3 e4 e5 e6 e7 e8 e9
A 1 0 0 0 0 1 0 1 0
B 0 1 1 0 0 0 1 0 0
C 0 0 0 1 1 0 0 1 0
D 1 1 0 0 0 0 0 0 1
E 0 0 0 0 1 1 1 0 0
F 0 0 1 1 0 0 0 0 1
完全关联矩阵为,
此图为连通图，
由定理 7-3.2，其秩为 5。
但这只在结点和边 (或弧 )的数目相当小的情况下才是可行的。显然这限制了图的利用。本节提供另一种图的表示法 —— 图的矩阵表示法。它不仅克服了图形表示法的不足，而且这种表示可以充分利用现代工具电子计算机，以达到研究图的目的。
一个简单图 G=<V,E>由 V中每两个结点间的邻接关系唯一地确定，这种关系可以用一个矩阵给出，
而矩阵形式与图中结点的编序有密切关系，这是用矩阵表示图值得注意的一点。
一、邻接矩阵定义 7-3.1 设 G=<V,E>是一个简单图，它有 n个结点 V={v1,v2,…vn},则 n阶方阵 A(G)=(aij)n× n称为 图 G的 邻接矩阵 (adjacency matrix) 。 其中：
1 vi adj vj
0 vi nadj vj 或 i=j
adj表示邻接,nadj表示不邻接。
aij=
0 1 0 0
A(G1)= 0 0 1 1
1 1 0 1
1 0 0 0
例如
0 1 1 1 1
1 0 1 0 0
A(G)= 1 1 0 1 0
1 0 1 0 1
1 0 0 1 0
无向图的邻接矩阵是对称矩阵，有向图的邻接矩阵不一定是对称的。
288页图
7-3,1
288页图
7-3,2
G1
288页图 7-3,2 G2
G2只是将 G1的两个结点 v1和 v2调换
0 0 1 1
1 0 0 0
A(G1)= 1 1 0 1
0 1 0 0
图 G2的邻接矩阵是将图 G1的邻接矩阵第一、
二行对调，第一、二列对调得到的。
对于给定图 G，显然不会因结点编序不同而使其结构发生任何变化，即图的结点所有不同的编序实际上仍表示同一个图。换句话说，这些结点的不同编序的图都是同构的，并且它们的邻接矩阵都是相似的。于是 G与 H同构?存在置换矩阵 P，
使 A(H)=P-1A(G)P，今后将略去这种由于 V中结点编序而引起邻接矩阵的任意性，而取该图的任一个邻接矩阵作为该图的矩阵表示。
邻接矩阵可展示相应图的一些性质：若邻接矩阵的元素全为零，则其对应的图是零图；
若 (无向图 )邻接矩阵的元素除主对角线元素外全为 1，则其对应的图是简单完全图。
(有向图 )邻接矩阵的元素除主对角线元素外全为 1，则其对应的图是有向完全图和强连通图。
当给定的简单图是无向图时，邻接矩阵是对称矩阵；反之，若给定任何对称矩阵 A，显然可以唯一地作出以 A为其邻接矩阵的简单图 G。于是，所有 n个结点的不同编序的简单图的集合与所有 n阶对称矩阵的集合可建立一一对应。
当给定的图是简单有向图时，其邻接矩阵并非一定是对称矩阵，但所有 n个结点的不同编序的简单图的集合，与所有 n阶邻接矩阵的集合亦可建立一一对应。
不仅如此，通过对矩阵元素的一些计算还可以得到对应图的某些数量的特征。
在给定简单有向图的邻接矩阵中，第 i行元素是由结点 vi出发的弧所确定，故第 i行中值为 1的元素数目等于结点 vi的出度。同理，第 j列中值为
1的元素数目等于结点 vj的入度。即 d+(vi)=
和 d-(vj)= 。
1
n
ik
k
a
1
n
kj
k
a
利用邻接矩阵计算长度为 k的路径条数,
按照普通 矩阵 乘法计算 n阶方阵 A(G)=(aij)n× n的 l次幂,所得乘积矩阵中的第 i行第 j列的元素,就是从结点 vi到结点 vj的长度为 l的路径条数。
(aij (l) )n× n= (A(G)) l =
a11 a12...a1n a11 a12...a1n a11 a12...a1n
a21 a22...a2n a21 a22...a2n … a21 a22...a2n
...,.,…,..,..,..,..,..,..
an1 an2...ann an1 an2...ann an1 an2...ann
共 l个
n
其中 aij (l) =? aik × akj (l-1)
k=1
.,,
例 290页例 1
定理 7-3.1 设 A(G)是图 G=<V,E>的邻接矩阵，则 (A(G))l中的 i
行 j列元素 aij (l)等于 G中联结 vi与 vj的长度为 l的路径条数。
证明思路：对 l用数学归纳法证明。
1) 当 l=1时,aij (2)等于 G中联结 vi与 vj的长度为 2的路径条数。
2)设命题对 l成立，即,aij (l)等于 G中联结 vi与 vj的长度为 l的路径条数。
3)现证 l+1时也成立。即 (A(G))l+1=(A(G)),(A(G))l
n
aij (l+1) =? aik × akj (l)
k=1
对 k求和即得结论。
vkvi vj
长度 =1
长度 =l
共 akj (l)条练习
300页（ 1）
求出图 7-3.9中有向图的邻接矩阵 A，找出从 v1到 v4长度为
2和 4的路，用计算 A2,A3,A4来验证这结论。
解
A=
0 1 0 1
0 0 1 1
0 1 0 1
0 1 0 0
0 1 1 1
0 2 0 1
0 2 1 1
0 0 1 1
A2=
0 2 1 2
0 2 2 2
0 2 1 2
0 2 0 1
A3=
0 4 2 3
0 4 1 3
0 4 2 3
0 2 2 2
A4=
从 v1到 v4长度为 2的路为 v1 v2 v4
从 v1到 v4长度为 4的路有,v1 v2 v4 v2 v4
v1 v2 v3 v2 v4 v1 v4 v2 4 v3 v4
在一些实际问题中，有时要判定图中结点 vi到结点 vj是否可达，或者说 vi到 vj是否存在路。如果利用图 G的邻接矩阵 A，则可计算 A2,A3,···,An,···。
当发现其中某个 Al的 aij(l)≥1，就表明 vi可达 vj或 vi到 vj
存在一条路。但这种计算繁琐量大，又不知计算 Al
到何时为止。
根据定理 7-2.1的推论可知，如果有向图 G有 n
个结点,vi到 vj有一条路，则必然有一条长度不大于 n的通路，因此，只需考虑 aij(l)就可以了，其中
1≤l≤n。即只要计算 Bn=A+A2+A3+···+An。
如果关心的是结点间可达性或结点间是否有路，
至于结点间的路存在多少条及长度是多少无关紧要，
那么便可用可达矩阵来表示结点间可达性。
二、、可达矩阵可达性矩阵的求法有两种：
1) 计算矩阵 Bn=A+A2+A3+…+A n
令矩阵 Bn中不为零的元素等于 1，为零的元素不变，
得到 P。 见例题 1。
2) 令 P =A∨ A(2) ∨ A(3) ∨ … ∨ A(n)
其中 A(i)(i=1,2,…,n) 为布尔矩阵。 见例题 2。
定义 7-3.2 设 G=<V,E>是一个简单有向图，它有 n
个已经编序的结点 V={v1,v2,…vn}，定义 n阶方阵
P(G)=(pij)n× n称为 图 G的 可达性矩阵 。 其中：
1 从 vi到 vj至少存在一条路。
0 从 vi到 vj不存在路。pij=
可见，可达矩阵表明了图中任意两结点间是否至少存在一条路以及在结点处是否有回路。
从图 G的邻接矩阵 A可以得到可达矩阵 P，即令
Bn=A+A2+A3+…+A n，再从 Bn中非零元素改为 1而零元素不变，这种变换后的矩阵即是可达矩阵 P。
练习：
300页（ 2）（ 3）
I = 1,2,3,……,n
第 i步：如果 A[ j,i]=1，则将第 i行加到第 j行。
（在具体计算中可以通过 Warshall算法实现）
300页（ 2） 如果 u可达 v，它们之间可能不止一条路，在所有这些路中，最短路的长度称为 u和 v之间的距离（或短程线），
记作 d<u,v>，如果从 u到 v是不可达的，则通常写成 d<u,v> =∞
距离矩阵为
0 1 2 1
∞ 0 1 1
∞ 1 0 1
∞ 1 2 0
dij=1表示存在边 <vi,vj>。
300页（ 3）
用 Warshall算法求可达性矩阵。
邻接矩阵为
0 0 0 0 0
1 0 1 1 0
1 0 0 0 0
0 0 1 0 0
0 0 0 0 0
A=
i=1时，因为 A的第一行全为 0，
所以 A不变。
i=2时，因为 A的第 2列全为 0，
所以 A不变。
i=3时，因为 A[2,3]=A[4,3]=0，将第 3
行加到第 2行和第 4行。
0 0 0 0 0
1 0 1 1 0
1 0 0 0 0
1 0 1 0 0
0 0 0 0 0
A,=
i=5时，因为 A的第 5列全为 0，所以 A不变。
0 0 0 0 0
1 0 1 1 0
1 0 0 0 0
1 0 1 0 0
0 0 0 0 0
P=
故 A的可达性矩阵为距离矩阵为
0 ∞ ∞ ∞ ∞
1 0 1 1 ∞
1 ∞ 0 ∞ ∞
2 ∞ 1 0 ∞
∞ ∞ ∞ ∞ 0
三、关联矩阵
1、无向图的关联矩阵举例 294页图 7-3.5
定义 7-3.3 给定无向 图 G=<V,E>,设 v1,v2,…,vp?V,
e1,…,eq?E,称 p× q阶矩阵 M (G)=(mij)p× q 为图 G的 完全关联矩阵 （ incidence matrix）。其中,
1 若 vi关联 ej。
0 若 vi不 关联 ej。mij=
无向图的关联矩阵 反映出来图的性质,
1) 每一条边关联两个结点,故每一列中只有两个 1。
2) 每一行中元素之和等于该行对应的结点度数。
3) 一行中元素全为 0，其对应结点为孤立点。
4) 两个平行边其对应的两列相同。
5) 同一个图当结点或边的编号不同时，其对应的矩阵只有行序列序的差别。
2、有向图的关联矩阵举例 294页图 7-3.6
定义 7-3.4 给定简单有向 图 G=<V,E>,设 v1,v2,…,
vp?V,e1,…,eq?E,称 p× q阶矩阵 M (G)=(mij)p× q 为图
G的 完全关联矩阵 (incidence matrix)。其中,
1 若 vi是 ej的起点 。
-1 若 vi是 ej的终点 。
0 若 vi不 关联 ej。
mij=
有向图的关联矩阵的特点：
(1)每一列中有一个 1和一个 -1，对应一边一个始点、一个终点，元素和为零。
(2)每一行元素的绝对值之和为对应点的度数。 -1
的个数等于入度,1的个数等于出度。
有向图 G的两行相加定义为：第 i行第 j列的对应元素 算术相加 ；相当于删除结点 vi与结点 vj之间的关联边，
合并结点 vi和 vj 。合并后得到的新结点记为 vi,j 。
无向图 G的两行相加定义为：第 i行第 j列的对应元素 模 2相加 ；相当于删除结点 vi与结点 vj之间的关联边，
合并结点 vi和 vj 。合并后得到的新结点记为 vi,j 。
3、关联矩阵的秩练习,
300页（ 4）
定理 7-3.2 如果一个连通 图 G=<V,E>,有个 r结点,
则其完全关联矩阵 M(G)的秩为 r-1,即 rank M (G)=r-1 。
证明思路,只对无向图证明利用线性代数中矩阵的初等（行、列）变换不改变矩阵的秩的结论和方法。
定理 7-3.2的推论 如果一个连通 图 G=<V,E>,有个 r结点,w个最大连通子图,则图 G的完全关联矩阵
M(G)的秩为 r- w,即 rank M (G)=r-w 。
300页（ 4）
写出如图 7-3.11所示的图 G的完全关联矩阵，并验证其秩如定理 7-3.2所述。
e1 e2 e3 e4 e5 e6 e7 e8 e9
A 1 0 0 0 0 1 0 1 0
B 0 1 1 0 0 0 1 0 0
C 0 0 0 1 1 0 0 1 0
D 1 1 0 0 0 0 0 0 1
E 0 0 0 0 1 1 1 0 0
F 0 0 1 1 0 0 0 0 1
完全关联矩阵为,
此图为连通图，
由定理 7-3.2，其秩为 5。
