无向树及生成树PPT学习教案_第1页
无向树及生成树PPT学习教案_第2页
无向树及生成树PPT学习教案_第3页
无向树及生成树PPT学习教案_第4页
无向树及生成树PPT学习教案_第5页
已阅读5页，还剩23页未读， 继续免费阅读

下载本文档

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

文档简介

1、会计学1 无向树及生成树无向树及生成树 2 第1页/共28页 3 第2页/共28页 4 )(2)()1(2xnxvdn i 定理定理9.2 设设T 是是 n 阶非平凡的无向树，则阶非平凡的无向树，则T中至少中至少 有两片树叶有两片树叶. 证证 设设T有有x片树叶，由握手定理及定理片树叶，由握手定理及定理9.1可知，可知， 由上式解出由上式解出x 2. 第3页/共28页 5 第4页/共28页 6 第5页/共28页 7 T T 设设G为无向连通图为无向连通图 G的的生成树生成树: G的生成子图并且是树的生成子图并且是树 生成树生成树T的的树枝树枝: G在在T中的边中的边 生成树生成树T的的弦弦:

2、G不在不在T中的边中的边 生成树生成树T的的余树余树 : 所有弦的集合的导出子图所有弦的集合的导出子图 注意：注意： 不一定连通不一定连通, 也不一定不含回路也不一定不含回路. 右图黑边构成生成树右图黑边构成生成树 红边构成余树红边构成余树 第6页/共28页 8 推论推论3 设设 为为G的生成树的生成树 T 的余树，的余树，C 为为G 中任意一中任意一 个圈，则个圈，则C与与 一定有公共边一定有公共边. T T 第7页/共28页 9 第8页/共28页 10 第9页/共28页 11 第10页/共28页 12 第11页/共28页 13 W(T)=3 8 第12页/共28页 14 第13页/共28页

3、 15 第14页/共28页 16 第15页/共28页 17 第16页/共28页 18 第17页/共28页 19 )()( 1 i t i i vlwtW 定义定义 设设2元树元树T有有t片树叶片树叶v1, v2, , vt, 树叶的权分树叶的权分 别别 为为w1, w2, , wt, 称称 为为T的权的权, 记作记作 W(T), 其中其中l(vi)是是vi的层数的层数. 在所有有在所有有t片树叶片树叶, 带权带权 w1, w2, , wt 的的 2元树中元树中, 权最小的权最小的2元树称为元树称为最优最优 2元树元树. 第18页/共28页 20 第19页/共28页 21 第20页/共28页 22 第21页/共28页 23 第22页/共28页 24 第23页/共28页 25

人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

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

最新文档

评论

0/150

提交评论