ImageVerifierCode 换一换
格式:PPT , 页数:54 ,大小:840KB ,
资源ID:1586061      下载积分:15 文钱
快捷下载
登录下载
邮箱/手机:
温馨提示:
快捷下载时,用户名和密码都是您填写的邮箱或者手机号,方便查询和重复下载(系统自动生成)。 如填写123,账号就是123,密码也是123。
特别说明:
请自助下载,系统不会自动发送文件的哦; 如果您已付费,想二次下载,请登录后访问:我的下载记录
支付方式: 支付宝    微信支付   
验证码:   换一换

加入VIP,省得不是一点点
 

温馨提示:由于个人手机设置不同,如果发现不能下载,请复制以下地址【https://www.wenke99.com/d-1586061.html】到电脑端继续下载(重复下载不扣费)。

已注册用户请登录:
账号:
密码:
验证码:   换一换
  忘记密码?
三方登录: QQ登录   微博登录 

下载须知

1: 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。
2: 试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓。
3: 文件的所有权益归上传用户所有。
4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
5. 本站仅提供交流平台,并不能对任何下载内容负责。
6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

版权提示 | 免责声明

本文(离散数学-图论-Chapter03.ppt)为本站会员(99****p)主动上传,文客久久仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知文客久久(发送邮件至hr@wenke99.com或直接QQ联系客服),我们立即给予删除!

离散数学-图论-Chapter03.ppt

1、第三章 树3.1 树的有关定义o 给定一个图 G=(V,E), 如果它不含任何回路 , 我们就叫它是林 , 如果 G又是连通的 , 即这个林只有一个连通支 , 就称它是树 .o 无圈连通无向图称为 树 。 (*)o 定义 3.1.1一个不含任何回路的连通图称为树 , 用 T表示 . T中的边称为树枝 , 度为 1的节点称为树叶 .树的基本应用电线,水管,煤气有关度的若干术语o 孤立点 :度为 0的顶点o 悬点 :度为 1的顶点n 悬边 :与悬点关联的边o 奇点 :度为奇数的顶点o 偶点 :度为偶数的顶点o 正则图 :各顶点度相同n 若度为 k,称为 k-正则图 .n 例如 :Kn是 (n1)-

2、正则图树的有关定义o 树的每条边 , 都不会属于任何回路 . 这样的边叫割边 .o 定义 3.1.2设 e是 G的一条边 , 若 G=G-e比 G的连通支树连通支数增加 , 则称 e是 G的一条割边 .o 显然 , 图 G删去割边 e=(u,v)之后 , 结点 u, v分属于不同的分支 .树的有关定义o 定理 3.1.1e=(u, v)是割边 ,当且仅当 e不属于 G的任何回路 .证明 : 必要性。设 e=(u, v)是割边 , 此时若 e=(u, v)属于 G的某个回路 , 则 G=G-e中仍存在 u到 v的道路 , 故 结 点 u和 v属于同一 连 通支 , e不是割 边 .矛盾 .充分性

3、。 设 e不属于 G的任何回路 , 此 时 若 e不是割边 , 则 G=G-e与 G的 连 通支数一 样 . 于是 u和 v仍属于同一 连 通支 . 故 G中存在道路 P(u,v), P(u,v)+e就是 G的一个回路 .矛盾 .树的有关定义o 定理 3.1.2设 T是结点数为 n2的树 , 则下列性质等价 :1. T连通且无回路2. T连通且每条都是割边3. T连通且有 n-1条边4. T有 n-1条边且无回路5. T的任意两结点间有唯一道路6. T无回路 , 但在任两结点间加上一条边后恰有一个回路T连通且无回路 T连通且每条都是割边 T连通且有 n-1条边o 12: T无回路,即 T的任意

4、边 e都不属于回路,由定理 3.1.1, e是割边。o 23:对结点数 n进行归纳。令 n(T), m(T)分别表示树 T的结点数和边数。当 n=2时命题成立。设nk时, m(T)=n(T)-1成立。则 n=k+1时,由于任一边 e都是割边,故 G=G-e有两个连通支T1, T2。由于 n(Ti)k, i=1,2,故m(Ti)=n(Ti)-1。所以 m(T)=n(T)-1也成立。3. T连通且有 n-1条边4. T有 n-1条边且无回路o 34:反证,假定 T存在圈,去掉圈上一条边,还是联通的,但 m(T)=n-2,不能保证联通了。 4. T有 n-1条边且无回路5. T的任意两结点间有唯一道

5、路o 45:设 u,v是 T的任意两结点,先证道路 P(u,v)的存在性,即证明 T是连通的。反证法。如果 T不是连通的,则至少有两个连通分支 T1, T2.由已知 T中无回路可知, T1, T2也没有回路。根据 1 2 3的证明,再由 T1和 T2是连通的且无回路可得, m(T1)=n(T1)-1, m(T2)=n(T2)-1, 则有:m(T)=m(T1)+m(T2)=(n(T1)+n(T2)-2=n-2n-1与已知 m(T)=n-1矛盾 .再证唯一性。若存在两条不同的道路 P(u,v), P(u,v),则其对称差 P(u,v)P(u,v)至少含有一个回路。注: G1G2=(V,E),其中 V=V1V2,E=E1E2;5. T的任意两结点间有唯一道路6. T无回路 , 但在任两结点间加上一条边后恰有一个回路1. T连通且无回路o 56:显然成立o 61: 只要证明 T是连通的。反证法。假设 T不连通,设 T1,T2为 T中的两个连通分支。 v1为 T1中的一个顶点, v2为 T2中的一个顶点。在 T中加边 (v1,v2)不形成回路。矛盾。 v1v2 v3v4 v5 v6

Copyright © 2018-2021 Wenke99.com All rights reserved

工信部备案号浙ICP备20026746号-2  

公安局备案号:浙公网安备33038302330469号

本站为C2C交文档易平台,即用户上传的文档直接卖给下载用户,本站只是网络服务中间平台,所有原创文档下载所得归上传人所有,若您发现上传作品侵犯了您的权利,请立刻联系网站客服并提供证据,平台将在3个工作日内予以改正。