离散数学课件第八章(第3讲).ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,8.3,图的矩阵表示,矩阵是研究图的有关性质的最有效的工具，可运用图的矩阵运算求出结点间的路径、找回路和研究图的连通性等问题。,图的矩阵主要分为邻接矩阵，可达性矩阵和关联矩阵。,定义：设，是简单图，其中,V=v,1,v,2,v,n,，定义一个,nxn,的矩阵,A,，并把其中各元素,表示成：,则称矩阵,A,为图,G,的邻接矩阵。,邻接矩阵,a,ij,讨论定义：,（,1,）在图的邻接矩阵中，,行中,1,的个数就是行中相应结点的出度,列中,1,的个数就是列中相应结点的入度,（,2,）零图的邻接矩阵称为零矩阵，即矩阵中的所有元素均为,0,例：图，和其邻接矩阵如下图所示：,根据该定理可以用邻接矩阵通过幂运算来计算两结点间路径的长度。,定理：设,A(G),是图,G,的邻接矩阵，则,(A(G),l,中,i,行,j,列元素,a,ij,(l),等于,G,中联结,v,i,与,v,j,的长度为,l,的路数目。若,i=j,则,a,ii,(l),等于,G,中联结,v,i,与,v,i,的长度为,l,的回路数目。,例：利用邻接矩阵来计算图,G,中两结点间路径的长度及路径数。,表示,v,i,和,v,j,之间具有长度为,2,的路径数,表示,v,i,和,v,j,之间具有长度为,3,的路径数,表示,v,i,和,v,j,之间具有长度为,4,的路径数,b,ij,0,，表示从,v,i,到,v,j,是可达的。,b,ij,表示从结点,v,i,到,v,j,有长度分别为,1,，,2,，,3,，,4,的不同路径总数。,定义,:,设，是简单有向图，其中,|V|=,，定义一个,nn,矩阵,P,，它的元素为：,则,P,称为图,G,的可达性矩阵。,2,可达性矩阵,计算可达性矩阵的方法是：,对于包含,n,个结点的图,G,首先给出邻接矩阵,A,，分别计算出,A,2,A,3,A,n,则,B,n,=A+A,2,+A,3,+A,n,，在矩阵,B,n,中，若,b,ij,0,，则对应的,P,ij,=1,，否则,P,ij,=0,例：给出下图,G,的 可达性矩阵,定义：设无向图，其中,令,则称,B,为无向图,G,的关联矩阵。,3,关联矩阵,例：写出无向图,G,的关联矩阵,定义：设无环有向图，其中,令,则称,B,为有向图,G,的 关联矩阵。,例：写出有向图,G,的关联矩阵,8.4,赋权图及最短路径,定义,设,G,是有限图，如果对,L(G),中任一条边,l，,都规定一个实数,w(l),附在其上，则称,G,为有限赋,权图,，称,w(l),为,边,l,的权,。规定,w(uu)=0,(,其中,u,P(G),),w(uv),(,其中,uv,L(G),),。,例:权图,w(ab)=5,w(aa)=0,w(bd)=,w(ad)=8,a,b,c,d,5,12,4,8,20,定义：,在一个权图,G,中，任给两点,u,，,v,，,从,u,到,v,可能有多条路，在这些路中，所带的权和最小的那条路称为图中,u,到,v,的最短路,。这条最短路所带的权和称为,u,到,v,的距离,，记为,d(u,v),。,例:最短路,a,到,c,的路有：,(1),(,a,b,c),长度为5+4=9;,(2),(,a,c),长度为12;,(3),(,a,d,c),长度为8+20=28。,最短路为：(,a,b,c)，,因此,a,到,c,的距离为9。,a,b,c,d,5,12,4,8,20,Dijkstra,算法,:,能求出图中某个结点到其它任一结点的最短路径。,(,1,),初始化，令,S=u,0,，S,=P-S，,对,S,中每一个定点,v,令,l(v)=w(u,0,v)；,(2),找到,u,i,S，,满足,(3),S=P，,则终止；否则令,S=S,u,i,，S=S-,u,i,，,对,S,中每一个定点,v，,计算,转到,(2)。,例：利用,Dijkstra,算法求,u,0,到其它结点 的最短路径。,b,a,c,d,7,6,2,f,e,8,1,4,4,3,4,7,2,3,5,6,3,2,1,u,0,g,算法执行过程,l(g),l(f),l(e),l(d),l(c),l(b),l(a),S,S,7,1,2,4,8,abcdefg,u,0,1,7,2,4,4,8,abcdeg,u,0,f,2,7,3,4,8,abcdg,u,0,fe,3,6,9,4,8,abcg,u,0,fed,4,6,9,6,acg,u,0,fedb,5,6,9,cg,u,0,fedba,6,9,c,u,0,fedbag,7,u,0,fedbagc,8,b,a,c,d,7,6,2,f,e,8,1,4,4,3,4,7,2,3,5,6,3,2,1,u,0,g,利用,Dijkstra,算法求最短路径结果,b,a,c,d,7,6,2,f,e,8,1,4,4,3,4,7,2,3,5,6,3,2,1,u,0,g,