当l＝1时， A1＝A， 由A的定义， 定理显然成立。
若l＝k时定理成立， 则当l＝k＋1时， A k+1＝ A · Ak ，
所以
n aij (l+1) = aik × akj (l)
k=1
长度=1
aij (1)等于G中 联结vi与vj的长 度为1的路径条 数。
长度=l
共akj (l)条
vi
vk
vj
va
vb
vc
vd
图G2
12 3 4
ab c d
A1＝
0 1 11 1 0 11 1 1 01 1 1 10
A2＝
0 1 11 1 0 11 1 1 01 1 1 10
❖ 判别定理：图G1 ，G2同构的充要条件是：存在置换矩阵P，使得： A1＝PA2P。
❖ 其中A1，A2分别是G1 ，G2的邻接矩阵。 ❖ 如何判断两图同构是图论中一个困难问题
返回 结束
7.3.1 邻接矩阵
7
❖ 结论：
(1) 如果对l＝1， 2， …， n-1， Al的（i， j）项元素 （i≠j）都为零， 那么vi和vj之间无任何路相连接， 即vi和 vj不连通。 因此， vi和vj必属于G的不同的连通分支。
(2) 结点vi 到vj （i≠j）间的距离d（vi， vj）是使Al（l＝ 1， 2， …， n-1 ）的（i， j）项元素不为零的最小整数l。
0 2 0 0 0 2 0 2 0 0 A3 0 2 0 0 0 0 0 0 0 1 0 0 0 1 0
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
2 0 2 0 0 0 4 0 0 0 A4 2 0 2 0 0 0 0 0 1 0 0 0 0 0 1
返回 结束
7.3.1 邻接矩阵
9
(1) 由A中a(1)12＝1知， v1和v2是邻接的； 由A3中a(3)12＝ 2知， v1到v2长度为3的路有两条， 从图中可看出是v1 v2 v1 v2和v1 v2 v3 v2 。 (2) 由A2的主对角线上元素知， 每个结点都有长度为２ 的回路， 其中结点v2有两条： v2 v1 v2和v2 v3 v2 ， 其余 结点只有一条。
内容：关联矩阵，邻接矩阵，可达矩阵。 重点：1、有向图，无向图的关联矩阵，
2、有向图的邻接矩阵。 了解：有向图的可达矩阵。
返回 结束
7.3.1 图的矩阵表示
3
存储原则: 存储结点集和边集的信息.
（1）存储结点集； （2）存储边集：
存储每两个结点是 否有关系。
邻接矩阵
返回 结束
7.3.1 邻接矩阵
4
1.无向图的邻接矩阵 定义 1.6.2设 G (V , E)的顶点集为 V v1,v2 ,L ,vp，用 a表ij 示
G 中顶点vi与v j 之间的边数。称矩阵MA((GG)) (aij ) pp为 G 的邻
接矩阵。
例2下图所示 G 的邻接矩阵为： v3
e1
e2
v1 v2 v3 v4 v5
(3) Al的（i， i）项元素a(l)ii表示开始并结束于vi长度为l
的回路的数目。
返回 结束
7.3.1 邻接矩阵
8
例1 图G＝（V， E）的图形如图， 求邻接矩阵A和A2， A3， A4， 并分析其元素的图论意义。
解
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
10
设图Ｇ＝＜Ｖ，Ｅ＞如下图所示
０１００
A
００１１ １１０１
讨论
１０００
（1）图G的邻接矩阵中的元素为0和1，∴又称为布尔矩阵；
（2）图G的邻接矩阵中的元素的次序是无关紧要的，进行行和行、
列和列的交换，则得到相同矩阵。
∴若有二个简单有向图，则可得到二个对应的邻接矩阵，若对某一
矩阵进行行和行、列和列之间的交换后得到和另一矩阵相同的矩阵，
矩阵
(2) 若MA((GG))为无环图。则MA((GG)) 中第i 行(列)的元素之和等于顶点 vi 的度数；
(3) 两个图G与H 同构的充要条件是存在一个置换矩阵P，使得
MA((GG)) PT M (H )P 。

返回 结束
7.3.1 邻接矩阵
5
❖ 同构图 v1
v3
v2
v4
图G1
v1<->va v2<->vb v3<->vc v4<->vd
第七章 图论
1
引言
7.1 图的基本概念 7.2 路与连通 7.3 图的矩阵表示 7.4 最短路径问题 7.5 图的匹配 8.1 Euler图和Hamilton图 8.2 树 8.3 生成树 8.4 平面图
返回 结束
7.3 图的矩阵表示
2
❖ 图的矩阵表示
图的数学抽象是三元组，其形象直观的表 示即图的图形表示。为便于计算，特别为便 于用计算机处理图，下面介绍图的第三种表 示方法—图的矩阵表示。利用矩阵的运算还 可以了解到它的一些有关性质。
返回 结束
7.3.1 邻接矩阵
6
❖ 在邻接矩阵A的幂A2， A3， …矩阵中， 每个元素有特 定的含义。
❖ 定理 :设G是具有n个结点集｛v1， v2， …， vn｝ 的图， 其邻接矩 阵为A， 则Al（l＝1， 2， …）的（i， j）项元素a(l)ij是从vi到vj的长 度等于l的路的总数。
证明 : 归纳法
(3) 由于A3的主对角线上元素全为零， 所以G中没有长 度为３的回路。
(4) 由于a（１）34＝a（２）34＝a（３）34＝a（４）34＝０， 所以 结点v3和v4间无路， 它们属于不同的连通分支。
(5) d（v1， v3）＝２。 对其他元素读者自己可以找出它的意义。
返回 结束
7.3.1 邻接矩阵
则此二图同构。
（3）当有向图中的有向边表示关系时，邻接矩阵就是关系矩阵；
（4）零图的邻接矩阵称为零矩阵，即矩阵中的所有元素均为0；
（5）在图的邻接矩阵中，
①行中1的个数就是行中相应结点的引出次数
②列中1的个数就是列中相应结点的引入次数
返回 结束
7.3.1 邻接矩阵
❖ 矩阵的计算：
０１００
A
v1
e9
v2
e3
e5
e8
e7 e 6
v1
0
1
0
1
1
对应的邻接矩阵
v4 e4
AM(G(G))
v2 v3
1 0
0 2
2 0
1 0
1
0
v4
1
1
0
1
1
v5
v5 1 1 0 1 0
从图的邻接矩阵的定义容易得出以下性质：
(1) MA((GG)) 是一个对称矩阵；
相当于将单位 矩阵中相应的 行与行，或者 列与列互换的