《图的矩阵表示》PPT课件.ppt

1,计算机科学领域有许多算法涉及图。计算机存储图的一种最简单有效的方法就是矩阵。矩阵是由数字组成的矩阵表格，一般用大写字母表示。（元素、行、列）。图论有效地利用了矩阵，将其作为表达图及其性质的有效工具和手段。,图在计算机中怎么表示?图跟矩阵是否一一对应?2007-11-10 18:27 提问者：Nimitz|浏览次数：1408次课本上有讲关于图的矩阵表示,但并没有提到这个问题.图(有向图或者无向图)跟矩阵是否一一对应呢?即一个矩阵是否能够唯一确定一个图,一个图是否能唯一确定一个矩阵?如果是这样的话,图在计算机中就好表示了.我一直在思考这个问题.谢谢了!图一般可以用邻结矩阵来表示，是双射得。比如跳马问题等就是这么处理得！,2,用邻接矩阵表示一个图时 1、输出一个图的边数，以及两端顶点 2、增加、删除一条边（输出新图对应的邻接矩阵）,3,4,14.4 图的矩阵表示,无向图的关联矩阵有向无环图的关联矩阵有向图的邻接矩阵有向图中的通路数与回路数有向图的可达矩阵,5,无向图的关联矩阵,设无向图G=,V=v1,v2,vn,E=e1,e2,em.令mij为vi与ej的关联次数,称(mij)nm为G的关联矩阵,记为M(G).mij的可能取值为:0,1,2,例如,6,关联矩阵的性质,7,无环有向图的关联矩阵,则称(mij)nm为D的关联矩阵,记为M(D).,设无环有向图D=,V=v1,v2,vn,E=e1,e2,em.令,8,实例,9,有向图的邻接矩阵,设有向图D=,V=v1,v2,vn,E=e1,e2,em,令 为顶点vi邻接到顶点vj边的条数，称()mn为D的邻接矩阵,记作A(D),简记作A.,10,实例,11,有向图中的通路数与回路数,定理14.11 设A为n阶有向图D的邻接矩阵,则Al(l1)中元素 等于D中vi到vj长度为 l 的通路(含回路)数,等于vi到自身长度为l 的回路数,等于D中长度为 l 的通路(含回路)总数,等于D中长度为 l 的回路总数.,12,实例(续),v1到v2长为3的通路有1条v1到v3长为3的通路有1条v1到自身长为3的回路有2条D中长为3的通路共有16条,其中回路4条,13,有向图的可达矩阵,性质:P(D)主对角线上的元素全为1.D强连通当且仅当P(D)的元素全为1.,设有向图D=,V=v1,v2,vn,令 称(pij)nn为D的可达矩阵,记作P(D),简记为P.,14,实例,例1(1)v1到v4,v4到v1长为3的通路各有多少条?(2)v1到自身长为1,2,3,4的回路各有多少条?(3)长为4的通路共有多少条?其中有多少条回路?(4)长度小于等于4的回路共有多少条?(5)写出D的可达矩阵,并问D是强连通的吗?解,15,实例(续),v1到v4长为3的通路有 条,3,v4到v1长为3的通路有 条,0,v1到自身长为1,2,3,4的回路各有 条,1,长为4的通路共有 条，其中有 条回路,16,3,长度小于等于4的回路共有 条,8,可达矩阵,非强连通,单连通,