第十章树与有序树ppt课件

1、第十章 树与有序树10.1 树的根本概念树的根本概念10.2 连通图的生成树和带权连通图的连通图的生成树和带权连通图的最小生成树最小生成树 10.3 有序树有序树10.4 前缀码和最优二分树前缀码和最优二分树 例例 PeterGodfriedBettyAlbertMaryMarivinDorisJudyHalDeniseGregory树的定义树的定义 一个无向图假设连通且不含圈，那么称它为一棵树一个无向图假设连通且不含圈，那么称它为一棵树，记为，记为 T=(V,E)。 设设T是一棵树，是一棵树， T中度数为中度数为1的顶点称为树叶，度数的顶点称为树叶，度数大于大于1的顶点称为分枝点。的顶点称为

2、分枝点。例例 能否为树能否为树?例例1 画出一切画出一切5个顶点的树个顶点的树定理定理1 设设 T=(V,E)是一棵树，那么有是一棵树，那么有 |E|=|V|-1。分析：对顶点数分析：对顶点数|V|进展归纳法证明。进展归纳法证明。当当|V|=1和和|V|=2时，定理显然是成立的。时，定理显然是成立的。归纳假设当归纳假设当|V|k时，定理成立。时，定理成立。 调查调查|V|=k+1时的情况。时的情况。 由于树无圈，所以从由于树无圈，所以从T中去掉任何一条边，中去掉任何一条边，都会使都会使T变成具有两个连通分支的不连通图。变成具有两个连通分支的不连通图。这两个连通分支也必然是树，譬如说是这两个连通

3、分支也必然是树，譬如说是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时，命题成

4、立。调查时，命题成立。调查|V|=k+1时的时的情况。设情况。设u,v E ，我们擦去边，我们擦去边e, 得得T的一个子图。的一个子图。令令 V1=v V子图中存在子图中存在u到到v的通路的通路， V2=v V子图中存在子图中存在v到到v的通路的通路。 例例定理定理1的证明的证明(续续)l 新图分为两个连通的子图新图分为两个连通的子图. 由于对于恣意的由于对于恣意的v V，原图是连，原图是连通的，所以在原图中存在通的，所以在原图中存在 v到到u的通路，也存在的通路，也存在v到到v的通路的通路，且都是初等通路。假设这两条通路都经过边，且都是初等通路。假设这两条通路都经过边e，那么原图，那么原图中

5、一定有圈，故中一定有圈，故V=V1V2 。假设存在。假设存在v V1V2，那么原图，那么原图中存在中存在 v到到u、v到到v的两条不经过边的两条不经过边e的初等通路，加上边的初等通路，加上边e后后, 原图中一定有圈，故原图中一定有圈，故V1V2 =。l 新图分为两棵不相交的树新图分为两棵不相交的树. 原图无圈，子图也不会有圈，即原图无圈，子图也不会有圈，即为两棵不相交的树为两棵不相交的树(顶点的交集为空集顶点的交集为空集)。l 设设T1=(V1,E1)，T2=(V2,E2)，由归纳假定有，由归纳假定有l |V1|-1=|E1|，|V2|-1=|E2|。l 又又|V|=|V1|+|V2|，|E|

6、=|E1|+|E2|+1。所以有定理得证。所以有定理得证。定理定理1的推论的推论任何一棵至少含有两个顶点的树至少有两片树叶。任何一棵至少含有两个顶点的树至少有两片树叶。证明：设证明：设 T=(V,E)是一棵树，假设是一棵树，假设T中最多只需一片树中最多只需一片树叶，那么有叶，那么有d(v) 1+2(|V|-1)=2|E|+1, 这与结论这与结论 d(v) =2|E| 矛盾矛盾! 矛盾阐明矛盾阐明 T 不止一片树叶。不止一片树叶。v Vv V例例 设设T为树，最大度为树，最大度k，这里，这里k1，证明证明T至少有至少有k片树叶。片树叶。 证明：假设T有s片树叶，sk。 记T的顶点数为n，那么 T

7、有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+3+3+ x1) x=15定理2T=(V,E)是一个简单图，以下三条等价。是一个简单图，以下三条等价。 T是一棵树。是一棵树。 T连通连通, 且且 |

8、V| 1=|E|。 T中无圈中无圈, 且且 |V| 1=|E|。证明：由证明：由 推出，由推出，由 推出推出 ，再由，再由 推出推出 ，以完成整个定理的证明。以完成整个定理的证明。 T是一棵树，即是一棵树，即T连通且无圈，连通且无圈， 由定理由定理1知，有知，有 |V|1 = |E| 。定理2的证明 知知T连通且连通且 |V|1=|E| 。假设。假设 T中有圈，拿去圈中的中有圈，拿去圈中的一条边，一条边， T仍连通。我们继续这样的任务，直到仍连通。我们继续这样的任务，直到 T中中无圈。由于顶点与边都是有限集，上面的任务一定可无圈。由于顶点与边都是有限集，上面的任务一定可以在有限步内终止。以在有

9、限步内终止。设设T中共拿走中共拿走L条边，由于每次拿去的边都是圈中的边条边，由于每次拿去的边都是圈中的边，不影响，不影响 T的连通性，所以剩下的子图的连通性，所以剩下的子图T是连通且无是连通且无圈的图，即圈的图，即T是一棵树。由定理是一棵树。由定理1知，知， |V|1=|E|，其中其中V，E分别是分别是T的顶点和边集。由的顶点和边集。由T的产生方法，的产生方法，有有|V|=|V|，|E|=|E| L。所以。所以|V|1 =|E|L。由。由于于|V|1=|E|，所以，所以 |E|=|E|L，即，即L=0，原图无圈。，原图无圈。定理2的证明 知知T中无圈且中无圈且|V|1=|E|。假设假设T不连通

10、，设不连通，设 T有有 k个连通分枝：个连通分枝： T1，T2，Tk，Ti=(Vi, Ei ), 1ik。对于每一个。对于每一个i (1ik), Ti是连通的且无圈，故是连通的且无圈，故Ti是树。由定理是树。由定理1知，知， |Vi|1=|Ei|，1ik。又又 所以所以|V|k=|E|，而知，而知|V|1=|E|，即有即有|V|k=|V|1，故，故 k=1，即，即T是连通图。是连通图。|Vi|=|V|， |Ei|=|E|i=1ni=1n例 设G为n阶无向简单连通图，n5， 证明G或G的补图不是树。 证明： 假设G或G的补图都是树，那么 它们的边数都是 n-1。 于是 (n-1)+(n-1)=n

11、(n-1)/2 可以解出n=4，与知条件矛盾。 例例 画出具有画出具有7个顶点的一切非同构的树个顶点的一切非同构的树解：所画出的树有解：所画出的树有6条边，因此条边，因此7个顶点的度数之和应为个顶点的度数之和应为12。由于每个顶点的度数均大于等于。由于每个顶点的度数均大于等于1，因此可以，因此可以产生一下产生一下7种度数序列：种度数序列： 1 1 1 1 1 1 6, 产生产生1棵非同构的树棵非同构的树T1 1 1 1 1 1 2 5, 产生产生1棵非同构的树棵非同构的树T2 1 1 1 1 1 3 4, 产生产生1棵非同构的树棵非同构的树T3 1 1 1 1 2 2 4, 产生产生2棵非同构的树棵非同构的树T4、T5 1 1 1 1 2 3 3, 产生产生2棵非同构的树棵非同构的树T6、T7 1 1 1 2 2 2 3, 产生产生3棵非同构的树棵非同构的树T8、T9、T10 1 1 2 2 2 2 2, 产生产生1棵非同构的树棵非同构的树T11T1 T2 T3 T4 T5 T6 T7 T8 T9 T10 T11 例 7阶无向图有3片树叶和1个3度顶点，其他3个顶点的度数均无1和3.试画出满足要求的一切非同构的无向树。解： 顶点数为7