7.3 图的矩阵表示.ppt

1、1,7.3 图的矩阵表示,无向图的关联矩阵 有向图的关联矩阵 有向图的邻接矩阵 无向图的邻接矩阵（补充） 有向图的可达矩阵,2,无向图的关联矩阵,定义 设无向图G=, V=v1, v2, , vn, E=e1, e2, , em, 令mij为vi与ej的关联次数，称(mij)nm为G的关联矩阵，记为M(G).,3,例7.3.1 求下图G的关联矩阵,上图G的关联矩阵:,4,无向图的关联矩阵（续）,性质：,（5） 当且仅当vi为孤立点。,5,有向图的关联矩阵,定义 设无环有向图D=, V=v1, v2, , vn, E=e1, e2, , em, 令 则称(mij)nm为D的关联矩阵，记为M(D)

2、.,6,例7.3.2 求图G的关联矩阵。,上图G的关联矩阵:,7,有向图的关联矩阵(续),性质 (1) 每一列恰好有一个1和一个-1 (2) 第i行1 的个数等于d+(vi), -1 的个数等于d-(vi) (3) 1的总个数等于-1的总个数, 且都等于m (4) 平行边对应的列相同,8,定义 设有向图D=, V=v1, v2, , vn, E=e1, e2, , em, 令 为顶点vi邻接到顶点vj边的条数，称( )mn为D的邻接矩阵, 记作A(D), 简记为A.,有向图的邻接矩阵,9,例7.3.3求下图G的邻接矩阵。,上图G的邻接矩阵：,10,有向图的邻接矩阵（续）,性质,11,D中的通路

3、及回路数,定理 设A为n阶有向图D的邻接矩阵, 则Al(l1)中 元素 为D中vi到vj长度为 l 的通路数， 为vi到自身长度为 l 的回路数， 为D中长度为 l 的通路总数， 为D中长度为 l 的回路总数.,12,注： 定理中所说的通路和回路，是在定义意义下的，而非同构意义下的，即当表示通路或回路的点边序列不同时认为它们是不同的通路或回路。,D中的通路及回路数（续）,13,证明: 施归纳于l。 当l1时， A1A， 由A的定义， 定理显然成立。 若lk时定理成立， 则当lk1时， A k+1AkA，,所以,D中的通路及回路数（续）,14,根据邻接矩阵定义arj是联结vr和vj的长度为1的路

4、数目,a(k)ir是联结vi和vr的长度为k的路数目,故上式右边的每一项表示由vi经过k条边到vr,再由vr 经过1条边到vj的总长度为k+1的路的数目 。对所有r求和,即得a(k+1)ij是所有从vi到vj的长度等于k+1的路的总数,故命题对k+1成立。,D中的通路及回路数（续）,15,D中的通路及回路数(续),推论 设Bl=A+A2+Al(l1), 则Bl中元素 为D中长度小于或等于l 的通路数， 为D中长度小于或等于l 的回路数.,16,例7.3.4 有向图D如图所示, 求A, A2, A3, A4, 并回答诸问题： (1) D中长度为1, 2, 3, 4的通路各有多 少条？其中回路分别

5、为多少条？ (2) D中长度小于或等于4的通路为多 少条？其中有多少条回路？,D中的通路及回路数(续),17,例7.3.4(续),长度 通路 回路,合计 50 8,1,8 1,2,11 3,3,14 1,4,17 3,18,无向图的邻接矩阵（补充）,定义 设GV ,E是有n个结点的简单图， 则n阶方阵（aij）称为G的邻接矩阵。 其中,如下图所示的图G， 其邻接矩阵A为,19,显然无向图的邻接矩阵必是对称的。,无向图的邻接矩阵（补充）,20,定理 设G是具有n个结点v1, v2, ,vn 的图， 其邻接矩阵为A， 则Al（k1， 2， ）的（i， j）项元素a(l)ij是从vi到vj的长度等于

6、l的通路的总数。,无向图的邻接矩阵（补充）,21,由定理可得出以下结论： 1) 如果对l1， 2， ， n-1， Al的（i， j）项元素（ij）都为零， 那么vi和vj之间无任何路相连接， 即vi和vj不连通。 因此， vi和vj必属于G的不同的连通分支。 2) 结点vi 到vj （ij）间的距离d（vi， vj）是使Al（l1， 2， ， n-1 ）的（i， j）项元素不为零的最小整数l。,无向图的邻接矩阵（补充）,22,例7.3.5 图GV ,E的图形如下图， 求邻接矩阵A和A2， A3， A4， 并分析其元素的图论意义。,无向图的邻接矩阵（补充）,23,解,无向图的邻接矩阵（补充）,2

7、4,有向图的可达矩阵,定义 设D=为有向图, V=v1, v2, , vn, 令 称(pij)nn为D的可达矩阵, 记作P(D), 简记为P. 性质: P(D)主对角线上的元素全为1. D强连通当且仅当P(D)的元素全为1.,25,有向图的可达矩阵(续),例7.3.6 右图所示的有向图D的可达矩阵为,26,根据可达矩阵， 可知图中任意两个结点之间是否至少存在一条通路。 根据n个结点的图中，如果两点之间有通路，则至少存在一条长度不大于n-1的通路，因此， 分以下两步可得到可达性矩阵。,有向图的可达矩阵(续),27,1) 令Bn-1AA2An-1, 2) 将矩阵n-1中非对角线的不为零的元素均改为

8、， 为零的元素不变，对角线元素全部为1，所得的矩阵P就是可达矩阵。 当n很大时， 这种求可达性矩阵的方法就很复杂。 下面再介绍一种更简便的求可达性矩阵的方法。,有向图的可达矩阵(续),因可达矩阵是一个元素仅为或的矩阵（称为布尔矩阵）， 而在研究可达性问题时， 我们对于两个结点间具有路的数目并不感兴趣， 所关心的只是两结点间是否有路存在。 因此， 我们可将矩阵A，A2, An,分别改为布尔矩阵A(1)， A(2)， ， A(n-1)。,有向图的可达矩阵(续),由此有 A(2)A(1)A(1)AA A(3)A(2)A(1) A(n-1)A(n-2)A(1) 对P中非对角线元素： PA(1)A(2)A(n-1) 相应的矩阵加法和乘法称为矩阵的布尔加和布尔乘。,有向图的可达矩阵(续),令B和C的布尔和、布尔积分别记为BC和B C，其定义为 (BC)ij=bijcij (B C)ij= (bikckj) i,j=1,2,n。其中bij，cij分别是B和C的i行j列元素。,有向图的可达矩阵(续),例7.3.7求出下图所示图的可达矩阵。,有向图的