离散数学课件-无向树.ppt_第1页
离散数学课件-无向树.ppt_第2页
离散数学课件-无向树.ppt_第3页
离散数学课件-无向树.ppt_第4页
离散数学课件-无向树.ppt_第5页
已阅读5页,还剩24页未读 继续免费阅读

下载本文档

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

文档简介

1,离散数学,李书杰 合肥工业大学 ,离散数学,2,学习内容,10.1 无向树 10.2 根树,3,4,如果将上图看作一个图的话,这个图就是一棵树,如下图。,5,定义10.2.1 无向树从无向图出发定义的树,无向树(树): 连通而无回路的无向图,一般用T表示 叶: 树中度数为1的顶点 分支点/内部结点: 树中度数1的顶点 森林: 一个非连通图,如果其每个连通分支都是树,则称为森林 平凡树: 平凡图,只有一个点且无边的图 右图为一棵12阶树. 声明:本章中所讨论的回路均 指简单回路或初级回路,6,无向树的性质,定理10.2.1 设G=是n阶m条边的无向图,则下面各命题是等价的: (1)G是树(连通无回路); (2)G中无回路且m=n1; (3)G是连通的且m=n1; (4)G中没有回路, 但在任何两个不同的顶点之间加一条新边,就会得到一条唯一的基本回路. (5)G是连通的且G中任何边均为桥; (6) G中任意两个顶点之间存在惟一的 一条基本通路。,7,(1)(2)的证明,如果G是无回路的连通图,则G中无回路且m=n1,其中m是边数,n是结点数 证明 归纳法。 当n=2时,因为G连通无回路, 所以只有m=1,故m=n-1成立。 假设n=k-1时命题成立,当n=k时, 因G是无回路且连通,则至少有一个度为1的结点u, 设与其关联的边为(u,w),删去u,得到一个k-1个结点 的连通无向图G,,8,(1)(2)的证明(续),由归纳假设可知, G的边数m=n-1=(k-1)-1=k-2。 再将结点u及(u,w)放入原位,恢复到图G, 那么G的边数 m=m+1=(k-2)+1=k-1, 结点数n=n+1=k, 故m=n-1成立。,9,(2)(3)的证明,如果G中无回路且m=n1,其中m是边数,n是结点数,则连通且m=n1; 只须证明G是连通的。 证明 设G有k个连通分枝G1,Gk(k1),Gi有ni个结 点,mi条边,因为Gi连通无回路,所以有 mi =ni-1,n=n1+n2+nk m=m1+m2+mk=(n1-1)+(n2-1)+(nk-1)=n-k 因为m=n-1,所以k=1,故G是连通的。,10,(3)(4)的证明,如果G连通且m=n1,则G中无回路, 但增加一条新边,得到一个且仅有一个包含新边的回路。 证明 归纳法。 当n=2时,m=n-1=1,必无回路,如果增加一边得到且仅得到一个回路。 设n=k-1时命题成立。考察n=k时的情况。 因为G是连通的,所以每个结点u有deg(u)1, 下面证明至少有一个结点u0使deg(u0)=1。 若不存在,则每个结点的度至少为2,所以2n2m,即n m,这与m=n-1矛盾。,11,(3)(4)的证明,首先证明G中也无回路 删去u0及其关联的边,得到含有k-1个结点的图G, G连通且m=n1。由归纳假设知G无回路。 在G中加入u0及其关联的边恢复到G,则G无回路。 再证明在G中任意两结点之间增加一条边,得到一条且仅有一条回路。 若在G中增加一条边(ui,uj), 因为G连通,则在G中存在一条从ui到uj的路, 那么这条路与新加入的边(ui,uj)构成回路, 而且这个回路是唯一的。 若不唯一,删掉边(ui,uj)边,G中必有回路,矛盾。,12,(4) (5)的证明,如果G中无回路, 但增加一条新边,得到一个且仅有一个包含新边的回路,则G连通且每条边均为桥。 证明 反证法。 假设G不连通, 则存在结点ui与uj,在ui和uj之间没有路, 所以增加边(ui,uj)不会产生回路,与已知矛盾。 由于G无回路,故删掉任意条边e都使G-e为非连通, 所以G中每条边都是桥。,13,(5) (6)的证明,如果G连通且每条边均为桥,则G中任意两个结点之间存在惟一的路径。 证明 由G是连通的可知,任意两个结点间有一条路, 若存在两点它们之间有多于一条的路, 则G中必有回路, 删去该回路上任一边, 图仍是连通的, 与G中每条边都是桥矛盾。,14,(6) (1)的证明,如果G中任意两个结点之间存在惟一的路径,则G是无回路的连通图。 证明 因为任意两结点间有唯一条路,则图G必连通。 若G有回路, 则在回路上任意两结点间有两条路, 与已知矛盾。,15,定理10.2.2 设T 是n阶非平凡的无向树,则T中至少有两片树叶. 证 设T有x片树叶,m条边。由握手定理及定理10.2.1可知, 由上式解出x2.,无向树的性质(续),16,例题,例1 已知无向树T中, 有1个3度顶点, 2个2度顶点, 其余顶点全是树叶. 试求树叶数, 并画出满足要求的非同构的无向树. 解 用树的性质m=n1和握手定理. 设有x片树叶,于是 n=1+2+x=3+x, 2m=2(n1)=2(2+x)=13+22+x 解出x=3,故T有3片树叶. T的度数列为1, 1, 1, 2, 2, 3 有2棵非同构的无向树, 如图所示,17,例题,例2 已知无向树T有5片树叶, 2度与3度顶点各1个, 其余顶点的度数均为4. 求T的阶数n. 解 设T的阶数为n, 则边数为n1, 4度顶点的个数为n7. 由握手定理得 2m=2(n1)=51+21+31+4(n7) 解出n=8, 4度顶点为1个. T的度数列为1,1,1,1,1,2,3,4,18,生成树 设G为无向连通图,若G的生成子图(v=v)是一棵树,则称这棵树为G的生成树; 设G的一棵生成树为T,则T中的边称为T的树枝,在G中而不在T中的边称为T的弦, 所有弦的集合称为生成树T的补 注意:生成树T的补不一定连通, 也不一定不含回路. 右图黑边构成生成树 红边构成补,定义10.2.2,19,生成树,定义10.2.2 若图G的生成子图是一棵树,则该树称为G的生成树。 生成树T的树枝: G在T中的边 生成树T的弦: G不在T中的边,生成树T的补 (或余树): 所有弦的集合的导出子图,注意: 不一定连通, 也不一定不含回路.,20,举例,例 如下图,T=e1,e6,e7,e4,e3,,黑线表示生成树,红线构成树的补。,=e2,e5,e8,余树是非连通的,无回路,余树是非连通的,有回路,21,举例,例 设T是6阶无向简单图G的一棵生成树,讨论下面的问题: (1) 当G的边数e=9时,T的补是G的生成树吗? (2) 当G的边数e=12时,T的补是G的生成树吗? (3) 当G的边数e=10时,T的补可能有哪几种情况? 解 对于树T,e=v-1,而任何ev或ev-1的图都不是树 (1)T的补的边数为9-5=4,所以不可能是树。 (2) T的补的边数为12-5=7,也不可能是树。 (3)有两种情况:T的补是生成树; T的补不连通且含圈。,22,生成树的存在性,定理10.2.3 无向图G具有生成树当且仅当G连通。 证明 必要性,显然。 充分性(破圈法)。 若G中无回路,G为自己的生成树。 若G中含回路,任取一回路,随意地删除回路上的一条边, 若再有回路再删除回路上的一条边,直到最后无回路为止。 易知所得图无回路、连通且为G的生成子图, 所以为G的生成树。,23,求连通图G=的生成树的算法,1 破圈法 2 避圈法 3 广度优先搜索算法,24,举例(破圈法),生成树不是唯一的!,25,最小生成树,对无向图或有向图的每一条边e附加一个实数w(e), 称作边e 的权. 图连同附加在边上的权称作赋权图, 记作G=. 设G是G的子图, G所有边的权的和称作G的权, 记作W(G). 最小生成树: 赋权图的权最小的生成树 求最小生成树的算法避圈法 (克鲁斯卡尔/Kruskal算法) 设G=, 将非环边按权从小到大排序:e1, e2, , em. (1) 把e1加入T中 (2) 检查e2, 若e2与e1不构成回路, 则将e2加入T中, 否则弃去e2. (3) 检查e3, 重复进行直至得到生成树为止.,26,实例,例 求图的一棵最小生成树,W(T)=38,27,1,2,3,4,4,5,6,7,7,8,28,普里姆(Prim)算法,普里姆算法的基本思想: 从连通图 G = V, E 中的某一顶点 u0 出 发,选择与它关联的具有最小权值的边(u0, v), 将其顶点加入到生成树的顶点集合U中。以后每 一步从一个顶点在U中,而另一个顶点不在U中 的各条边中选择权值最小的边(u, v),把它的顶点 加入到集合U中。如此继续下

温馨提示

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

评论

0/150

提交评论