《离散数学》第七章 图论-第3-4节ppt课件.ppt

《离散数学》第七章_图论-第3-4节ppt课件除用图形表示图外,还可用矩阵表示图,它的优点:(1)将图的问题变为数学计算问题,从而可借助计算机来研究图,进行相关的计算。(2)表示更清楚。知识点:,因此在用矩阵表示图时,先要将图的结点进行排序,若不具体说明排序,则默认为书写集合V时结点的顺序。7-、图的邻接矩阵或者i=jadjacent(邻接)以结点与结点之间的邻接关系确定的矩阵。定义7-=<V,E>,其中V={v1,v2,…,vn},则n阶方阵A(G)=(aij)nn,称为图G的邻接矩阵。其中第i行j列的元素。-(1)写出下面无向图的邻接矩阵0110010100110000000100010A(G)=-(2):写出下面有向图的邻接矩阵图的邻接矩阵例v2v1v3v40100001111011000A(G)=6.(1)邻接矩阵的主对角线元素aii=0。(2)主对角线以外的元素aijaij=1(i<>j),说明图G是完全图;aij=0(i<>j),说明图G是零图。(3)无向图的邻接矩阵是对称的;而有向图的邻接矩阵不一定对称;因为在无向图中一条无向边应看成方向相反的两条有向边,因此无向图的邻接矩阵关于主对角线对称。图的邻接矩阵说明:A(G)=0100001111011000v2v1v3v40110010100110000000100010A(G)=7.(4)结点的度数无向图:每行1的个数=每列1的个数=对应结点的度有向图:每行1的个数=对应结点的出度每列1的个数=对应结点的入度图的邻接矩阵说明:v2v1v3v4A(G)=0100001111011000011001010000001**********.图的邻接矩阵的应用(1)由邻接矩阵可计算出从vi到vj的长度为L的路的数目,也可计算从vi出发的长度为L的回路数。(2)计算结点vi与vj之间的距离。(3)判断G是否是连通图,及G中任意两个结点是否连通。:G中从结点v2到结点v3长度为2路数目为0。A3中:G中从结点v2到结点v3长度为3的路数目为2。A2中:G中长度为2的路(含回路)总数为8,其中6条为回路。A3中:G中长度为3的路(含回路)总数为10,其中0条为回路。v4v1v3v2v5aij(2)=ai1•a1j+ai2•a2j+ai3•a3j++ain•anjaij(L+1)=ai1•a1j(L)+ai2•a2j(L)+ai3•a3j(L)++ain•anj(L)10.