若l＝k时定理成立， 则当l＝k＋1时， A k+1＝ A · Ak ，
所以
n aij (l+1) = aik × akj (l)
长度=1
aij (1)等于G 联结vi与vj 度为1的路径 数。
长度=l
7.3.1 邻接矩阵
结论：
(1) 如果对l＝1， 2， …， n-1， Al的（i， j）项 （i≠j）都为零， 那么vi和vj之间无任何路相连接， 即 vj不连通。 因此， vi和vj必属于G的不同的连通分支。
， E e1 ,e2, eq 。用 bij表示顶点 vi 与边e j 关联的次数
或2)，称矩阵 B(G) (bij ) pq 为 G 的关联矩阵。
7.3.2 关联矩阵
例1 下图所示 的关联矩阵为：
Gv3
e 1 e2
e1 e2 e3 e4 e5 e6 e7 e
v1
e9
v2
e3
e5
内容：关联矩阵，邻接矩阵，可达矩阵。
重点：1、有向图，无向图的关联矩阵，
2、有向图的邻接矩阵。
7.3.1 图的矩阵表示
存储原则: 存储结点集和边集的信息.
（1）存储结点集； （2）存储边集：
存储每两个结点
邻接矩阵
7.3.1 邻接矩阵
1.无向图的邻接矩阵 定义 1.6.2设 G (V , E)的顶点集为 V v1,v2 , ,vp，用 a表ij 示
7.3.1 邻接矩阵
矩阵的计算：
０１００
A

００１１ １１０１
１０００
１０１０
A
AT

０２１０ １１３１
００１１
００１１
AT

１０１０ ０１００
０１１０
２１０１
AT

A

１２０１ ００１１
１１１２
7.3.2 邻接矩阵
有向图 D (下图所示)，求 A(D) 。
1 2 1 0 解：A(D) 0 0 1 0
0 0 0 1
7.3.2 关联矩阵
关联矩阵多用于简单无向图
一个图 G (V , E) 由它的顶点与边的关联关系唯一 确定；
无向图的关联矩阵
定义 1.6.1 设 G (V , E) 的顶点集和边集分别为 V v1,
7.3.1 邻接矩阵
2.有向图的邻接矩阵
1、设有向图 D V , E ，V v1,v2, ,vn ，
E m ，D 的邻接矩阵 A(D)
a(1) ij
nn
，
其中
a(1) ij
指
vi
邻接到
v j 的边的条数
(非负整数)。
7.3.1 图的矩阵表示
有向图的邻接 矩阵
例1
０１００
A

００１１ １１０１
讨论
１０００
（1）图G的邻接矩阵中的元素为0和1，∴又称为布尔矩阵；
（2）图G的邻接矩阵中的元素的次序是无关紧要的，进行行和
列和列的交换，则得到相同矩阵。
∴若有二个简单有向图，则可得到二个对应的邻接矩阵，若对 矩阵进行行和行、列和列之间的交换后得到和另一矩阵相同的 则此二图同构。 （3）当有向图中的有向边表示关系时，邻接矩阵就是关系矩阵 （4）零图的邻接矩阵称为零矩阵，即矩阵中的所有元素均为0
2 0 2 0 0 0 4 0 0 0 A4 2 0 2 0 0 0 0 0 1 0
7.3.1 邻接矩阵
(1) 由A中a(1)12＝1知， v1和v2是邻接的； 由A3中a(3 2知， v1到v2长度为3的路有两条， 从图中可看出是 v1 v2和v1 v2 v3 v2 。 (2) 由A2的主对角线上元素知， 每个结点都有长度为 的回路， 其中结点v2有两条： v2 v1 v2和v2 v3 v2 ， 结点只有一条。
7.3.1 邻接矩阵
在邻接矩阵A的幂A2， A3， …矩阵中， 每个元素有 定的含义。
定理 :设G是具有n个结点集｛v1， v2， …， vn｝ 的图， 其邻 阵为A， 则Al（l＝1， 2， …）的（i， j）项元素a(l)ij是从vi到 度等于l的路的总数。
证明 : 归纳法
当l＝1时， A1＝A， 由A的定义， 定理显然成立。
e8 e7 e 6
v 4
对应的关联矩阵
e4
B(G)

v1 v2 v3

0 1 1
0 1 1
v4

0
0
0010 1000 0000 1211
01 10 00 00
v5
bij =
2 1
e j关联于xi，v5 e 0j是0自环0 0 0
e
j关联于xi，e
不是自环
j
1
1
1
从图的关联矩阵的定0义容e j易不得关出联以与下xi性质：
解
0 1 0 0 0 1 0 1 0 0 A 0 1 0 0 0 0 0 0 0 1 0 0 0 1 0
0 2 0 0 0 2 0 2 0 0 A3 0 2 0 0 0 0 0 0 0 1
1 0 1 0 0 0 2 0 0 0 A2 1 0 1 0 0 0 0 0 0 1 0 0 0 1 0
主对角线上的数表
主对角线上的数表示结
7.3.1 邻接矩阵
００１１
A2

A
A

２１０１ １１１１
０１００
１２１１
A4

A3

A

２２２３ ３３２３
２１０１
２１０１
A3

A2

A

１２１１ ２２１２
００１１
A2
表示i和j之间具有长度为2 的通路数，
元素不变， 所得的矩阵P就是可达性矩阵。 当n很大时， 这种求可达性矩阵的方法就很复杂
其中元素 pij (i
j)可由 Bn1
b(n1) ij
求得：
nn
7.3.3 有向图的可达性矩阵
根据可达性矩阵， 可知图中任意两个结 之间是否至少存在一条路以及是否存在回 利用有向图的邻接矩阵A， 分以下两步可 到可达性矩阵。
(1) 令Bn＝A＋A2＋…＋An,
(2) 将矩阵Ｂn中不为零的元素均改为１， 为
vie为j是e自j的环始，点且关联与xi v在i与De中j不e j以关x联i为起点，e 在 evji与为D中xei不je的j以关终x联i为点终点，e
不是自环
j
不是自环
j
7.3.2 关联矩阵
例2
有向图 D (下图所示)，求 AM(D(D) )。
1 1 0 0 0
解：MA((DD))

1 0
7.3.1 邻接矩阵
同构图 v1
v3
v2
v4
图G1
v1<->va v2<->vb v3<->vc v4<->vd
va vb
12 3 4
ab c
A1＝
0 1 11 1 0 11 1 1 01 1 1 10
A2＝
011 101 110 111
判别定理：图G1 ，G2同构的充要条件是：存在置换矩阵P，使 A1＝PA2P。
1 0 2
0 2 0
1 1 0
1

1
0

v4

1
1
0
1
1
v5
v5 1 1 0 1 0
从图的邻接矩阵的定义容易得出以下性质：
(1) MA((GG))是一个对称矩阵；
相当于 矩阵中 行与行 列与列
矩
(2) 若MA((GG))为无环图。则MA((GG)) 中第i 行(列)的元素之和等于顶点 vi 的度数；
A3
表示i和j之间具有长度为3
的通路数，
A4 表示i和j之间具有长度为4
的通路数，
7.3.1 邻接矩阵
３４２３
B4

A1

A2

A3

A4

５５４６ ７７４７
３２１２
bij表示从结点vi到vj有长度分别为1，2， 4的不同通路总数。
此时， bij0，表示从vi到vj是可达的。
0 0
1
1
1

0 0 1
7.3.3 有向图的可达性矩阵
有向图的可达性矩阵。(了解)
设D V , E 为有向图，V v1,v2, ,vn ，
令 pii 1 ，i 1, 2, , n
1
pij

0
vi可达vj (i j) 否则
可达性矩阵P ( pij )nn
第七章 图论
引言 7.1 图的基本概念 7.2 路与连通 7.3 图的矩阵表示 7.4 最短路径问题 7.5 图的匹配 8.1 Euler图和Hamilton图 8.2 树 8.3 生成树 8.4 平面图
7.3 图的矩阵表示
图的矩阵表示 图的数学抽象是三元组，其形象直观的
示即图的图形表示。为便于计算，特别为 于用计算机处理图，下面介绍图的第三种 示方法—图的矩阵表示。利用矩阵的运算 可以了解到它的一些有关性质。
(3) 由于A3的主对角线上元素全为零， 所以G中没有 度为３的回路。
(4) 由于a（１）34＝a（２）34＝a（３）34＝a（４）34＝０， 所 结点v3和v4间无路， 它们属于不同的连通分支。
(5) d（v1， v3）＝２。 对其他元素读者自己可以找出它的意义。
7.3.1 邻接矩阵
设图Ｇ＝＜Ｖ，Ｅ＞如下图所示
(2) 结点vi 到vj （i≠j）间的距离d（vi， vj）是使A 1， 2， …， n-1 ）的（i， j）项元素不为零的最小