定理7-3.1 设G是具有结点集{v1，
v2，…，vn}和邻接矩阵A的图，则矩
阵AL（l=1，2，…）的第i行第j列的
元素aij(L)=m，表示图G中从结点vi到
vj长度为L的路有m条（即路的数
证明：
目）。
❖ （从vi到vj的长度为l的路可看作从vi到vk
的长度为1的路，再联结vk到vj的长度为l-
❖ 例7-3.2：求下图中图例G的从结点v2到结点v3长
度为2和3的路数目及所有长度为2和3的路数 目分。析 利用定理7-3.1 ，求图中长度为m的路数
目，只需要先写出图的邻接矩阵，然后计算邻
接矩阵的m次方即可。
v5 v1
v2
v4 v3
v5 图v1G的邻接 矩阵为v2
v4 v3
G中从结点v2到结点v3长度 为2通路数目为0，G中长 度为2的路（含回路）总数 为8，其中6条为回路。
7-3 图的矩阵表示
除用图形表示图外，还可用矩阵表示图，它的优点： (1)将图的问题变为数学计算问题，从而可借助计算 机来研究图，进行相关的计算。
(2)表示更清楚。 知识点：
1.邻接矩阵 邻接矩阵求两点间不同长度的路的条数
2.可达性矩阵 3.完全关联矩阵 由于矩阵的行和列有固定的次序，因此在用矩阵表 示图时，先要将图的结点进行排序，若不具体说明 排序，则默认为书写集合V时结点的顺序。
➢(3)无向图的邻接矩阵是对称的；
因而为有在向无图向的图邻中接一矩条阵无不向一边定应对看称成v；4 方向相反的两条v3
有向边，因此无向图的邻接矩阵关于主对角线对称。
01100 10100 A(G)= 1 1 0 0 0 00001 00010
01 0 0
v1
v v 1 v 2 v 3 v 4 v25
A3中： G中长度为3的路
图的邻接矩阵的应用
(1)由邻接矩阵可计算出从vi到vj的长度为L的 路的数目，可计算从vi出发的长度为L的回 路数。
定理7-3.1 设G是具有结点集{v1，v2，…，vn} 和邻接矩阵A的图，则矩阵AL（l=1， 2，…）的第i行第j列的元素aij(L)=m，表示 图aGij(2中)=a从i1•a结1j+点ai2v•ai到2j+vaji3长•a3度j+为+La的in•a路nj 有m条 （a即ij(L+路1)=的ai1数•a1目j(L)）+a。i2•a2j(L)+ai3•a3j(L)++ain•anj(L)
图的邻接矩阵的应用
(3)判断G是否是连通图，及G中任意两个结点是否连通。
A(G)= 0 0 1 1
11 0 1
v4
v3
10 0 0
图的邻接矩阵
01 0 0
说明： ➢(1)邻接矩阵的主对角线元素aii=0。A(G)=
00 11
1 0
1 1
➢(2)主对角线以外的元素aij ▪aij=1 (i<>j)，说明图G是完全图；v1
1 0 0 v02
▪aij=0 (i<>j)，说明图G是零图。
图的邻接矩阵例
例7-3.1 (1) 写出下面无向图的邻接矩阵
v1 v2 v3 v4 v5 v1 0 1 1 0 0 v2 1 0 1 0 0 A(G)v=3 1 1 0 0 0 v4 0 0 0 0 1 v5 0 0 0 1 0
图的邻接矩阵例
例7-3.1(2)：写出下面有向图的邻
接矩阵
v1
v2
01 0 0
由
故
而aik是结点vi到vk长度为1的路的数目，
是结点vk到vj长度为p的路的数目，
所以上式右边的每一项表示从vi经过一条边到vk，再
由vk经过一条长度为p的路到vj的总长度为p+1的路的
数目，对所有k求和，
是所有从vi到vj的长度
为p+1的路的数目。所以对l=p+1成立。
证毕。
图的邻接矩阵求不同长度的路
▪有向图: ▪每行1的个数=对应结点的出度 ▪每列1的个数=对应结点的入度
图的邻接矩阵的应用
(1)由邻接矩阵可计算出从vi到vj的长度为L的 路的数
目，也可计算从vi出发的长度为L的回路数 。
(2)计算结点vi与vj之间的距离。
(3)判断G是否是连通图，及G中任意两个结点
v5 图G的邻接 v1
aij(2)=ai1•a1j+ai2•a2j+ai3•a3j++ain•anj
G中从结点v2到结点v3长度 为3的通路数目为2， G中 长度为3的路（含回路）总
图的邻接矩阵的
v5 v1
应用 (若2)计算结点vi与vj之间的距中离至。少有一个v不4 为0，v3
v2
则可断定vi与vj相连接，求
中不为0的最小的L即为d<vi,vj>。
如： d<v1,v2>=1,d<v1,v3>=2， d<v5,v4>=1,d<v1,v4>= ∞
矩阵为v2 aij(L+1)=ai1•a1j(L)+ai2•a2j(L)+ai3•a3j(L)++ain•anj(L)
v4 v3
A2中：G中从结点v2到结点 v3长度为2路数目为0。
A3中：G中从结点v2到结点 v3长度为3的路数目为2。
A2中：G中长度为2的路(含 回路)总数为8，其中6条为 回路。
图的邻接矩阵说明： A(G)= 0 0 1 1 11 0 1
10 0 0
➢(4)结点的度数
v1 v2
00 11
11 00
11 11
00 00
00 00
v A
v3 v4
11 00
4v 5 00
11 00 00
00 00 00
00 00
00 11
11 v030
▪无向图：
▪每行1的个数=每列1的个数=对应结点的度
预备知识
预备知识
一、图的邻接矩阵
❖ 以结点与结点之间的邻接关系确定的矩阵。
❖ 定义7-3.1 设简单图G=<V,E>，其中 V={v1,v2,…,vn}，则n阶方阵A(G)=(aij)nn ，称为 图G的邻接矩阵。 a其ij 中 1 0 第,, i行 v v j列ii,,v v的jj 元 素E E或 或 =ejnt(邻接)
1的路。）
❖ 用数学归纳法：
❖ 1）当l=2时，成立。
❖ 2）设l=p时命题对l成立，即aij(p)表示 图G中有几条从结点vi到vj长度为p的路
vn}和邻接矩阵A的图，则矩阵AL（l=1，
2，…）的第i行第j列的元素aij(L)=m，表
示图G中从结点vi到vj长度为L的路有m条
3)证明l＝p＋（1时即定理路成的立数。 目）。