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

*******其中，d(u0,u)对应的最短路，其全部的点均属于S.***§8.3图的矩阵表示矩阵是研究图的有关性质的最有效的工具，可运用图的矩阵运算求出结点间的路径、找回路和研究图的连通性等问题。图的矩阵主要分为邻接矩阵，可达性矩阵和关联矩阵。定义：设Ｇ＝＜Ｖ，Ｅ＞是简单图，其中V={v1,v2,…vn}，定义一个nxn的矩阵A，并把其中各元素表示成：则称矩阵A为图G的邻接矩阵。１．邻接矩阵aij讨论定义：（1）在图的邻接矩阵中，①行中1的个数就是行中相应结点的出度②列中1的个数就是列中相应结点的入度（2）零图的邻接矩阵称为零矩阵，即矩阵中的所有元素均为0例：图Ｇ＝＜Ｖ，Ｅ＞和其邻接矩阵如下图所示：根据该定理可以用邻接矩阵通过幂运算来计算两结点间路径的长度。定理：设A(G)是图G的邻接矩阵，则(A(G))l中i行j列元素aij(l)等于G中联结vi与vj的长度为l的路数目。若i=j,则aii(l)等于G中联结vi与vi的长度为l的回路数目。例：利用邻接矩阵来计算图G中两结点间路径的长度及路径数。表示vi和vj之间具有长度为2的路径数表示vi和vj之间具有长度为3的路径数表示vi和vj之间具有长度为4的路径数bij?0，表示从vi到vj是可达的。bij表示从结点vi到vj有长度分别为1，2，3，4的不同路径总数。定义:设Ｇ＝＜Ｖ，Ｅ＞是简单有向图，其中|V|=ｎ，定义一个n×n矩阵P，它的元素为：则P称为图G的可达性矩阵。2．可达性矩阵计算可达性矩阵的方法是：对于包含n个结点的图G,首先给出邻接矩阵A，分别计算出A2,A3,…,An,则Bn=A+A2+A3+…+An，在矩阵Bn中，若bij≠0，则对应的Pij=1，否则Pij=0例：给出下图G的可达性矩阵定义：设无向图Ｇ＝＜Ｖ，Ｅ＞，其中,令则称B为无向图G的关联矩阵。3．关联矩阵例：写出无向图G的关联矩阵定义：设无环有向图Ｇ＝＜Ｖ，Ｅ＞，其中,令则称B为有向图G的关联矩阵。例：写出有向图G的关联矩阵§8.4赋权图及最短路径定义设G＝P,L是有限图，如果对L(G)中任一条边l，都规定一个实数w(l)附在其上，则称G为有限赋权图，称w(l)为边l的权。规定w(uu)=0(其中u?P(G)),w(uv)＝∞(其中uv?L(G))。例:权图w(ab)=5w(aa)=0w(bd)=∞w(ad)=8abcd5124820定义：在一个权图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。abcd5124820Dijkstra算法:能求出图中某个结点到其它任一结点的最短路径。(1)初始化，令S={u0}，S’=P-S，对S’中每一个定点v,令l(v)=w(u0,v)；(2)找到ui?S’，满足(3)S=P，则终止；否则令S=S∪{ui}，S’=S’-{ui}，对S’中每一个定点v，计算转到(2)。例：利用Dijkstra算法求u0到其它结点的最短路径。bacd762fe81443472356321u0g算法执行过程l(g)l(f)l(e)l(d)l(c)l(b)l(a)S’S712∞∞48abcdefgu01724∞48abcdegu0f273∞48abcdgu0fe36948abcgu0fed4696acgu0fedb569cgu0fedba69cu0fedbag7u0fedbagc8bacd762fe81443472356321u0g利用Dijkstra算法求最短路径结果bacd762fe81443472356321u0g***********************其中