- 1、本文档共56页,可阅读全部内容。
- 2、原创力文档(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
13.1图的概念;13.1.1定义
定义13.1一个无向图G由一个非空点集V(G)和其中元素的无序关系集合E(G)构成,记为G=(V(G),E(G)),简记为G=(V,E).
称为无向图G的顶点集,每一个元素
称为图G的一个顶点;称为无向图G的边集,每一个元素
(即V中两个元素vkvl的无序对)记为称为无向图G的一条边.;定义13.2给一个图的每一条边(弧)赋予一个数字,则得到一个赋权图.这些数字可以表示距离、花费、时间等,统称为权重.
定义13.3在无向图中,与顶点v关联的边数称为v的度,记为d(v).;例13.1如图13-1所示,图是一个无向图,其中;定义13.4在一个无向图中,若从顶点vi到顶点vj有路径相连,则称vi,vj是连通的.若图中任意两点都是连通的,则称该图是连通图,否则就称为非连通图.
例如,图13-1中v1与v3连通(v1e1v2e4v3),v2与v4连通(v2e4v3e5v4).并且任意两个点都连通,所以图13-1是连通图.
定义13.5连通的无圈图称为树,记为T.度为1的点称为叶子节点.;定义13.6若图及树T之间满足,则称T是G的生成.
一个连通图的生成树个数有很多,图13-1的部分生成树如图13-2所示.从图13-2可以看出树具有性质:1)连通;2)点数=边数+1;3)不存在任何的圈.;13.1.2图的邻接矩阵;例13.2将图13-3所示的图用邻接矩阵和赋权邻接矩阵表示.
解图13-3所示的图用邻接矩阵和赋权邻接矩阵分别表示为矩阵A和B.
由此可见无向图的邻接矩阵是一个对角线全为0的0-1对称阵.;13.2最小生成树的算法;求解最小生成树有Kruskal算法和Prim算法.
1Kruskal算法描述如下:
对于一个连通的赋权图G,按照如下步骤构造其最小生成树T:
1)找出G所有边中的权重最小的边e1作为T的第一条边;
2)选择,使得e2的权重最小;
3)选择,使得e3的权重最小,且不能和前面所选的边构成圈;
4)重复步骤3),直到找出n-1条边,??得到G的最小生成树.
此算法可以称为“加边法”,初始最小生成树边数为0,每迭代一次就选择一条满足条件的最小代价边,加入到最小生成树的边集合里.;例13.3用Kruskal算法求图13-3所示的最小生成树.
解(1)边v3v4的权重为所有边中最小的,选取v3v4∈E作为第一条边,即e1=v3v4;
(2)边v1v4的权重为剩下的边中最小的,选取v1v4∈E-{e1}作为第二条边,即e2=v1v4;
(3)边v1v2的权重为剩下的边中最小的,但是加进来后会构成圈,故在E-{e1,e2,v1v2}中选取权重最小的边v1v3作为第三条边,即e3=v1v3;
(4)找到了3条边,停止.
利用Kruskal算法得到最小生成树见图13-4,得到的最小生成树的权重是15.;2Prim算法
对于连通的赋权图,设置两个集合P和Q,其中P用于存放G的最小生成树中的顶点,集合Q存放G的最小生成树的边.
1)初始化顶点集P={v1},v1∈V,边集Q=?;
2)选择v2∈V-P使得边v1v2的赋权最小,P={v1,v2},Q={v1v2};
3)重复步骤2),知道P=V,停止.
此算法可以称为“加点法”,每次迭代选择代价最小的边对应的点,加入到最小生成树中.算法从某一个顶点s开始,逐渐长大覆盖整个连通网的所有顶点.;例13.4用Prim算法求图13-3所示的最小生成树.
解(1)初始化顶点集P={v1},v1∈V,边集Q=?;
(2)与v1相连的边v1v2,v1v3,v1v4中
您可能关注的文档
- 数学实验 课件 第1、2章 MATLAB简介、MATLAB数值运算.pptx
- 数学实验 课件 第3、4章 MATLAB符号运算、MATLAB图形功能.pptx
- 数学实验 课件 第5、6章 MATLAB程序设计、 线性代数实验.pptx
- 数学实验 课件 第7、8章 微积分实验、概率论与数理统计实验.pptx
- 数学实验 课件 第9、10章 常微分方程实验、优化方法实验.pptx
- 数学实验 课件 第11、12章 插值与拟合实验、 Hill密码与解密.pptx
- (三篇)双减背景下分层设计初中语文作业研究结题报告(详细版) .docx
- GBT 44429-2024:大科学装置风险管理的核心原则 .pdf
- 2024年二年级语文上册第一~五单元知识要点及检测(含答案) .pdf
- 【《宜宾五粮液公司管理会计的应用及其优化案例报告》8500字论文】 .pdf
- 全国青少年(毒品预防教育)知识考试题库与答案 .pdf
- 2023年山东胶州市领军计划自主招生历史试题真题(含答案详解) .pdf
- 【人教版八年级生物】第六单元 第二章 认识生物的多样性 .pdf
- 冀人版-第三单元 电(提升卷)-四年级科学上册单元培优进阶练.docx
- 新郑市事业单位统考真题 .pdf
- 冀人版-第三单元动物的生长与繁殖(单元测试)四年级下册科学.docx
- CLCN4基因变异相关癫痫的临床表型及基因变异特点 .pdf
- 【《“双减”背景下小学中年级语文自主阅读策略探究》6500字】 .pdf
- 高一语文开学第一课+课件+2024-2025学年统编版高中语文必修上册 .pdf
- 密山市事业单位统考真题 .pdf
文档评论(0)