第十章树与有序树.ppt
《第十章树与有序树.ppt》由会员分享,可在线阅读,更多相关《第十章树与有序树.ppt(18页珍藏版)》请在三一文库上搜索。
1、第十章 树与有序树,10.1 树的基本概念 10.2 连通图的生成树和带权连通图的最小生成树 10.3 有序树 10.4 前缀码和最优二分树,例,树的定义,一个无向图若连通且不含圈,则称它为一棵树,记为 T=(V,E)。 设T是一棵树, T中度数为1的顶点称为树叶,度数大于1的顶点称为分枝点。,例 是否为树?,例1 画出所有5个顶点的树,定理1 设 T=(V,E)是一棵树,则有 |E|=|V|-1。,分析:对顶点数|V|进行归纳法证明。 当|V|=1和|V|=2时,定理显然是成立的。 归纳假设当|V|k时,定理成立。 考察|V|=k+1时的情况。 因为树无圈,所以从T中去掉任何一条边,都会使T
2、变成具有两个连通分支的不连通图。这两个连通分支也必然是树,譬如说是T1=(V1,E1)和T2=(V2,E2)。 显然,|V1| k, |V2| k。根据归纳假设,有 |E1|=|V1|-1, |E2|=|V2|-1。而|V|=|V1|+|V2|, |E|=|E1|+|E2|+1, 所以|E|=|V|-1, 即定理得证。,定理1的证明,证明:用对顶点集V的元素个数归纳法来证。 当|V|=1时,T是一个仅有一个顶点且没有边的图。显然,|E|=0, 命题成立。 归纳假设若|V|k时,命题成立。考察|V|=k+1时的情况。设u,v E ,我们擦去边e, 得T的一个子图。令 V1=vV子图中存在u到v的
3、通路, V2=vV子图中存在v到v的通路。,定理1的证明(续),新图分为两个连通的子图. 因为对于任意的vV,原图是连通的,所以在原图中存在 v到u的通路,也存在v到v的通路,且都是初等通路。若这两条通路都经过边e,则原图中一定有圈,故V=V1V2 。如果存在v V1V2,则原图中存在 v到u、v到v的两条不经过边e的初等通路,加上边e后, 原图中一定有圈,故V1V2 =。,新图分为两棵不相交的树. 原图无圈,子图也不会有圈,即为两棵不相交的树(顶点的交集为空集)。 设T1=(V1,E1),T2=(V2,E2),由归纳假定有 |V1|-1=|E1|,|V2|-1=|E2|。 又|V|=|V1|
4、+|V2|,|E|=|E1|+|E2|+1。所以有定理得证。,定理1的推论,任何一棵至少含有两个顶点的树至少有两片树叶。,例 设T为树,最大度k,这里k1, 证明T至少有k片树叶。,证明:假设T有s片树叶,sk。 记T的顶点数为n,则 T有1个度顶点,有s片树叶, 还有(n-s-1)个不少于2度的顶点。 由握手定理可知: 2(n-1) 2(n-s-1)+k+s 可以解出 sk,这与假设sk矛盾。,例2,已知一棵树有5个4度顶点,3个3度顶点,3个2度顶点,问有几个一度顶点?,解:设有 x个1度顶点,则依题意有方程: 54+33+32+1x = d(v) =2|E| =2(|V|-1) =2(5
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第十 有序
链接地址:https://www.31doc.com/p-2597846.html