




已阅读5页,还剩20页未读, 继续免费阅读
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
7.3 图的矩阵表示 无向图的关联矩阵 有向图的关联矩阵 有向图的邻接矩阵 有向图的可达矩阵 1 无向图的关联矩阵 定义 设无向图G=, V=v1, v2, , vn, E=e1, e2, , em, 令mij为vi与ej的关联次数,称(mij)nm为G的关 联矩阵,记为M(G). 2 例:求下图G的关联矩阵 l上图G的关联矩阵: 3 无向图的关联矩阵 性质: (5) 当且仅当vi为孤立点。 4 有向图的关联矩阵 定义 设无环有向图D=, V=v1, v2, , vn, E=e1, e2, , em, 令 则称(mij)nm为D的关联矩阵,记为M(D). 5 n例: 求图G的关联矩阵。 l 上图G的关联矩阵: 6 有向图的关联矩阵(续) 性质 (4) 平行边对应的列相同 7 定义 设有向图D=, V=v1, v2, , vn, E=e1, e2, , em, 令 为顶点vi邻接到顶点vj边的条数,称( )mn为D的邻接矩阵, 记作A(D), 简记为A. 有向图的邻接矩阵 8 n求下图G的邻接矩阵。 l解 上图G的邻接矩阵。 给出了图G的邻接矩阵,就等于给出了图G的全部 信息。图的性质可以由矩阵 A通过运算而获得。 9 定义 设有向图D=, V=v1, v2, , vn, E=e1, e2, , em, 令 为顶点vi邻接到顶点vj边的条数,称( )mn为D的邻接矩阵, 记作A(D), 简记为A. 性质 有向图的邻接矩阵 10 D中的通路及回路数 定理 设A为n阶有向图D的邻接矩阵, 则Al(l1)中 元素 为D中vi到vj长度为 l 的通路数, 为vi到自身长度为 l 的回路数, 为D中长度为 l 的通路总数, 为D中长度为 l 的回路总数. 11 D中的通路及回路数(续) 例 有向图D如图所示, 求A, A2, A3, A4, 并回答诸问题: (1) D中长度为1, 2, 3, 4的通路各有多 少条?其中回路分别为多少条? (2) D中长度小于或等于4的通路为多 少条?其中有多少条回路? 推论 设Bl=A+A2+Al(l1), 则Bl中元素 为D中长度小于或等于l 的通路数, 为D中长度小于或等于l 的回路数. 12 例(续) 长度 通路 回路 合计 50 8 18 1 211 3 314 1 417 3 13 在下图中v1到v3长度为1、2、3、4的通路分别有 多少条,G中共有长度为4的通路多少条,其中回路 多少条,长度小于等于4的通路共有多少条,其中 回路多少条。 14 l解:因为 15 l 所以,由v1到v3长度为1、2、3、4的通 路分别有0、2、2、4条,G中共有长度为 4的通路43条,其中回路11条,长度小于 等于4的通路共有87条,其中回路22条。 l 注 无向图也有相应的邻接矩阵,一般只 考虑简单图,无向图的邻接矩阵是对称的 ,其性质基本与有向图邻接矩阵的性质相 同。 16 例如:下图邻接矩阵为: 17 有向图的可达矩阵 称(pij)nn为D的可达矩阵, 记作P(D), 简记为P. 性质: P(D)主对角线上的元素全为1. D强连通当且仅当P(D)的元素全为1. 定义 设D=为有向图, V=v1, v2, , vn, 令 18 有向图的可达矩阵(续) 例 右图所示的有向图D的可达矩阵为 19 设G=V,E是n阶简单有向图,V=v1,v2,vn, 由可达性矩阵的定义知,当ij时,如果vi到vj有路 ,则pij=1;如果vi到vj无通路,则pij=0;又如果vi到 vj有通路,则必存在长度小于等于n1的通路。又n 阶图中,任何回路的长度不大于n ,如下计算图G 的可达性矩阵P: B=E+A+A2+A n-1 =(b ij ) nn 其中 E 是单位矩阵。则 20 图9.24邻接矩阵A和A2,A3,A4如下: 21 22 则图G的可达性矩阵 B= A0AA2A3A4 = P= 23 可达性矩阵用来描述有向图的一个结点到另 一个结点是否有路,即是否可达。无向图也 可以用矩阵描述一个结点到另一个结点是否 有路。在无向图中,如果结点之间有路,称 这两个结点连通,不叫可达。所以把描述一 个结点到另一个结点是否有路的矩阵叫连通 矩阵,而不叫可达性矩阵。 24 定义 设G=V,E是简单无向图,V=v1,v2,vn P
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 人教版小学英语三年级上册教学资源开发计划
- 特殊教育班主任班务工作计划
- 2025年学校食堂废弃物处理计划
- 小学道法专项复习计划
- 消防设施监理工作报告范文
- 福建省龙岩市连城县2024-2025学年九上数学期末联考试题含解析
- 2025届湖南省邵阳市郊区数学九上期末达标检测试题含解析
- 烟师大地球科学基础教案06大气的热力状况
- 辽宁省辽河油田欢喜岭第二初级中学2024-2025学年物理九上期末学业水平测试模拟试题含解析
- 高三数学考试真题训练计划
- 辽宁省盘锦市兴隆台区2024-2025学年小升初考试数学试卷含解析
- 2025年初级人工智能训练师(五级)资格理论考试题(附答案)
- 交警心理知识讲座课件
- 综合性安全检查表
- 特色小吃开发策略-全面剖析
- 2025机关事业单位工人招聘《机动车驾驶员》技师 考试题库与参考答案
- 企业战略咨询服务简单合同
- 矿区第三方管理制度内容
- 中国心力衰竭诊断和治疗指南
- GB/T 19701.2-2024外科植入物超高分子量聚乙烯第2部分:模塑料
- 道路及市政管网改造工程现场组织管理机构及施工准备方案
评论
0/150
提交评论