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

1、8.3 图的矩阵表示图的矩阵表示 矩阵是研究图的有关性质的最有效的工具，可运用图的矩阵是研究图的有关性质的最有效的工具，可运用图的矩阵运算求出结点间的路径、找回路和研究图的连通性矩阵运算求出结点间的路径、找回路和研究图的连通性等问题。等问题。图的矩阵主要分为邻接矩阵，可达性矩阵和关联矩阵。定义：设，是简单图，其中定义：设，是简单图，其中V=v1,v2,vn，定义一个定义一个nxn的矩阵的矩阵A，并把其中各元素，并把其中各元素 表示成：表示成：EvvEvvajijiij若若,0,1则称矩阵则称矩阵A A为图为图G G的邻接矩阵。的邻接矩阵。邻接矩阵邻接矩阵 aij讨论定义：讨论定义：（1）在图的

2、邻接矩阵中，）在图的邻接矩阵中，行中行中1的个数就是行中相应结点的出度的个数就是行中相应结点的出度 列中列中1的个数就是列中相应结点的入度的个数就是列中相应结点的入度（2）零图的邻接矩阵称为零矩阵，即矩阵中的所有元素均为）零图的邻接矩阵称为零矩阵，即矩阵中的所有元素均为0例：例：图，和其邻接矩阵如下图所示：图，和其邻接矩阵如下图所示：A根据该定理可以用邻接矩阵通过幂运算来计算两结点间根据该定理可以用邻接矩阵通过幂运算来计算两结点间路径的长度。路径的长度。定理：设A(G)是图G的邻接矩阵，则(A(G)l中i行j列元素aij(l)等于G中联结vi与vj的长度为l的路数目。若i=j,则aii(l)等

3、于G中联结vi与vi的长度为l的回路数目。例：利用邻接矩阵来计算图例：利用邻接矩阵来计算图G中两结点间路径的长度及中两结点间路径的长度及路径数。路径数。AAAA223AAA34AAA2A表示vi和vj之间具有长度为2的路径数3A表示vi和vj之间具有长度为3的路径数4A表示vi和vj之间具有长度为4的路径数 bij 0，表示从，表示从vi到到vj是可达的。是可达的。bij表示从结点表示从结点vi到到vj有长度分别为有长度分别为1，2，3，4的不同路径的不同路径总数。总数。43214AAAAB 定义定义:设，是简单有向图，其中设，是简单有向图，其中|V|=，定义一个定义一个 nn矩阵矩阵P，它的

4、元素为：，它的元素为：不存在任何路径到若至少存在一条路径到若jijiijvvvvp01则P称为图G的可达性矩阵。2 可达性矩阵可达性矩阵 计算可达性矩阵的方法是：计算可达性矩阵的方法是：对于包含对于包含n个结点的图个结点的图G,首先给出邻接矩阵首先给出邻接矩阵A，分别，分别计算出计算出A2,A3,An,则则Bn=A+A2+A3+An，在矩，在矩阵阵 Bn 中，若中，若bij0，则对应的，则对应的 Pij=1，否则，否则Pij=0 例：给出下图例：给出下图G的的 可达性矩阵可达性矩阵P43214AAAAB 定义：设无向图，其中定义：设无向图，其中,2121mneeeEvvvVmnijbB)(,令

5、jijiijevevb不关联若关联若01则称B为无向图G的关联矩阵。3 关联矩阵关联矩阵 例：写出无向图例：写出无向图G的关联矩阵的关联矩阵 定义：设无环有向图，其中定义：设无环有向图，其中,2121mneeeEvvvVmnijbB)(,令jijijiijevevevb不关联若的终点是若的起点是若01-1则称B为有向图G的 关联矩阵。例：写出有向图例：写出有向图G的关联矩阵的关联矩阵1v2v3v4v1e2e3e4e5e8.4 赋权图及最短路径赋权图及最短路径 n定义定义 设设G是有限图，如果对是有限图，如果对L(G)中任一条边中任一条边l，都规定一个实数都规定一个实数w(l)附在其上，则称附在

6、其上，则称G为有限赋为有限赋权图权图，称，称w(l)为为边边l的权的权。规定。规定w(uu)=0(其中其中u P(G),w(uv)(其其中中uv L(G)。例例:权图权图 w(ab)=5w(aa)=0w(bd)=w(ad)=8 abcd5124820n定义：定义：在一个权图在一个权图G中，任给两点中，任给两点u，v，从从u到到v可能有多条路，在这些路中，所带的权和最小的可能有多条路，在这些路中，所带的权和最小的那条路称为图中那条路称为图中u到到v的最短路的最短路。这条最短路所带。这条最短路所带的权和称为的权和称为u到到v的距离的距离，记为，记为d(u,v)。例例:最短路最短路 a到到c的路有：

7、的路有：(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=uS=u0 0，S=P-SS=P-S，对对 SS中每一个定点中每一个定点v,v,令令l(v)=w(ul(v)=w(u0 0,v),v)；(2)找到找到ui S，满足满足l(v)min)l(uSvi(3)S=P，则终止；否则令则终

8、止；否则令S=Sui，S=S-ui，对对 S中中每一个定点每一个定点v，计算计算v),w(u)l(ul(v),minl(v)iiSv转到转到(2)(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 fedbagc8bacd762fe8 1443472356321u0g利用利用Dijkstra算法求最短路径结果算法求最短路径结果bacd762fe81443472356321u0g