东北师范大学《离散数学》课件-第八讲.pdfVIP

东北师范大学《离散数学》课件-第八讲.pdf

  1. 1、本文档共207页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
  5. 5、该文档为VIP文档,如果想要下载,成为VIP会员后,下载免费。
  6. 6、成为VIP后,下载本文档将扣除1次下载权益。下载后,不支持退款、换文档。如有疑问请联系我们
  7. 7、成为VIP后,您将拥有八大权益,权益包括:VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
  8. 8、VIP文档为合作方或网友上传,每下载1次, 网站将根据用户上传文档的质量评分、类型等,对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档
查看更多
离散数学 第八讲 无向树 Undirected Trees 无向树  连通且不含任何简单回路的无向图称为无向 树(undirected tree),简称树(tree)。树 中度数为1的顶点称为叶子(leaf),度数大 于1的顶点称为分枝点(branch point)  根据这个定义,一阶简单图K1 也是树,称作平凡 树(trivial tree ),它是一个既无叶子又无分枝点 的特殊树  由定义可知,树必定是不含重边和自环的,即树 一定是简单图。  不含任何简单回路的图称为森林(forest)  显然,森林的每个连通分支都是树 2 无向树 a b c d e f h i j 3 无向树  定理1  设n(n2) 阶无向连通图G 的边数满足m=n1, 则图G 中至少存在两个度数为1的顶点  证明  因为图G 是连通的,从而各顶点的度数均大于0  设图G 有t 个顶点度数为1,其余顶点度数 n 都至少是2 ,则 2m deg(v )  t  2(n t) i i 1 由m=n1,可得2(n1)=2mt+2n2t ,即t2 4 无向树  定理2 设T 是(n, m)-无向图,则下述命题相互等价  T 是树,即T 连通且不存在简单回路  T 的每一对相异顶点之间存在唯一的简单道路  T 不存在简单回路,但在任何两个不相邻的顶点 之间加一条新边后得到的图中存在简单回路。 (也称作“极大无圈”)  T 连通,但是删去任何一边后便不再连通,即T 中每一条边都是桥。(也称作“极小连通”) 5 无向树 6 无向树 连通 无圈 在任何两个不相邻 删去任何一边后便 的顶点之间加一条 不再连通 新边后得到的图中 存在简单回路 7 无向树  定理2 设T 是(n, m)-无向图,则下述命题 相互等价  T 是树,即T 连通且不存在简单回路  T 连通且m = n1  T 不存在简单回路且m = n1 8 无向树 连通 无圈 m = n1 9 无向树  推论  任何非平凡树至少有2个叶子顶点。  推论  对于任何无向(n, m)-图,若图中不存在简单回路,则 m  n1  证明  若无向(n, m)-图G 中m(n1),则删去任意m(n1) 条边得到图G’。  图G’ 中仍然不存在任何简单回路,由定理2 ,图G’ 是树  再将删去的边重新添加到图G’ 中,由定理2 ,G 中存

文档评论(0)

逍遥子 + 关注
实名认证
文档贡献者

互联网搬运工

1亿VIP精品文档

相关文档