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

1、8.3 图的矩阵表示 矩阵是研究图的有关性质的最有效的工具，可运用图的矩阵运算求出结点间的路径、找回路和研究图的连通性等问题。 图的矩阵主要分为邻接矩阵，可达性矩阵和关联矩阵。 定义：设，是简单图，其中V=v1,v2,vn，定义一个nxn的矩阵A，并把其中各元素 表示成： 则称矩阵A为图G的邻接矩阵。 邻接矩阵 aij讨论定义：（1）在图的邻接矩阵中， 行中1的个数就是行中相应结点的出度 列中1的个数就是列中相应结点的入度（2）零图的邻接矩阵称为零矩阵，即矩阵中的所有元素均为0例： 图，和其邻接矩阵如下图所示： 根据该定理可以用邻接矩阵通过幂运算来计算两结点间路径的长度。定理：设A(G)是图G

2、的邻接矩阵，则(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的路径数 bij0，表示从vi到vj是可达的。 bij表示从结点vi到vj有长度分别为1，2，3，4的不同路径总数。 定义:设，是简单有向图，其中|V|=，定义一个 nn矩阵P，它的元素为：则P称为图G的可达性矩阵。 2 可达性矩阵 计算可达性矩阵的方法是：对于包含n个结点的

3、图G,首先给出邻接矩阵A，分别计算出A2,A3, ,An,则Bn = A+A2+A3+An ，在矩阵 Bn 中，若bij0，则对应的 Pij =1，否则Pij =0 例：给出下图G的 可达性矩阵 定义：设无向图，其中,令则称B为无向图G的关联矩阵。3 关联矩阵 例：写出无向图G的关联矩阵 定义：设无环有向图，其中,令则称B为有向图G的 关联矩阵。例：写出有向图G的关联矩阵8.4 赋权图及最短路径 定义 设G是有限图，如果对L(G)中任一条边l，都规定一个实数w(l)附在其上，则称G为有限赋权图，称w(l)为边l的权。规定w(uu)=0(其中uP(G),w(uv)(其中uvL(G)。 例: 权图

4、 w(ab)=5w(aa)=0w(bd)= w(ad)=8 abcd5124820定义：在一个权图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) 找到uiS，满足(3) S=P，则终止；否则令S=Sui， S=S-ui ，对 S中每一个定点v，计算转到(2)。例：利用Dijkstra算法求u0到其它结点 的最短路径。bacd762fe81443472356321u0g算法执行过程l(g)l(f)l(e)l(d)l(c)l(b)l(a)SS71248abcdefgu0172448abcdegu0 f27348abcdgu0 fe36948abcgu0 fed4696acgu0 fedb569cgu0 fedba69cu0 fedbag7u0 fed