《《图的矩阵表示》ppt课件》由会员分享，可在线阅读，更多相关《《图的矩阵表示》ppt课件（15页珍藏版）》请在金锄头文库上搜索。
1、1,计算机科学领域有许多算法涉及图。计算机存储图的一种最简单有效的方法就是矩阵。矩阵是由数字组成的矩阵表格，一般用大写字母表示。（元素、行、列）。图论有效地利用了矩阵，将其作为表达图及其性质的有效工具和手段。,图在计算机中怎么表示? 图跟矩阵是否一一对应? 2007-11-10 18:27 提问者： Nimitz | 浏览次数：1408次 课本上有讲关于图的矩阵表示,但并没有提到这个问题. 图(有向图或者无向图)跟矩阵是否一一对应呢? 即一个矩阵是否能够唯一确定一个图,一个图是否能唯一确定一个矩阵? 如果是这样的话,图在计算机中就好表示了. 我一直在思考这个问题. 谢谢了! 图一般可以用邻结矩
2、阵来表示，是双射得。比如跳马问题等就是这么处理得！,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的关
3、联矩阵, 记为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 的回路总
4、数.,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,可达矩阵,非强连通,单连通,
