2022年《树与最小树》教案_第1页
2022年《树与最小树》教案_第2页
2022年《树与最小树》教案_第3页
2022年《树与最小树》教案_第4页
2022年《树与最小树》教案_第5页
已阅读5页，还剩1页未读， 继续免费阅读

付费下载

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

1、 12 树与最小树 教学目的： 1、懂得树的相关概念 2、懂得最小树问题 3、把握求最小树的方法 教学重点：避圈法、破圈法 教学难点：树的概念的懂得教学过程：一、 树与图的部分树1、定义：一个无圈的连通图称为树 例 1 12 级会计一班班级结构如图：（日常生活中仍有许多树形图的运用,例如黄石冶钢集团组织结构,家族族谱等等,大家可以想想平常仍看到过哪些树形图）从最简洁的树开头观看起,大家能发觉有什么规律吗？2、树的性质：设 T 是一棵有 p 个顶点的树,就树 T 的边数是（ p-1）条图有部分图,树有部分树,什么是部分树呢？3、定义：假如G 的一个部分图T 是棵树,就称T 为 G 的一棵部分树注

2、：部分树第一得是部分图,必需包含图 二、最小树G 的全部顶点；1、定义：假如图 G 中的每一条边 v , iv j ,相应地有一个数 w ,称为边 v , iv j 的权；图 G 连同在它边上的权称为赋权图 . 2、定义：在赋权图 G 中,部分树 T 的各边上权的总和称为部分树 T的权. 3、最小树问题：求赋权图 三、最小树算法 1、避圈法G 中权最小的部分树 . 步骤：（1）.画出赋权图 G 的各个顶点；（2）.在 G 中画一条权最小的边；（3）.在 G 中余下的边中,选一条权最小的边加在图上,并 要使它与已选入的边不形成圈（避圈）. （4）.重复步骤（ 3）,直至各顶点都连通为止（此时的边

3、数 应等于顶点数减 1）例 2 本学院要沿如下列图的道路架设电话线,将六个部门连成网. .已知每条道路的长度,求使电话线总长最小的架设方案留意：在避圈法中,如遇到两条或几条边的权相等且最小时,可以 从中任取一条,但不行与已选的边成圈2、破圈法 步骤：（1）在赋权图 G 中任取一个圈,在该圈中去掉权最大的边（破圈） . （2）在余下的部分图中,重复步骤1,直至无圈为止,所得的部分图即为最小树 . 例 3 用破圈法求例 2 的图的最小树课中练习拟在黄石四个县镇之间建设高速大路,请确定建造告知大路时的最小树,县镇之间的距离（km）如下图 . 学问点总结： 1、树的基本概念2、树的重要性质 3、部分树的

人人文库> 全部分类> 教育资料 > 中学教育

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论