《树与有序树》PPT课件.ppt

《《树与有序树》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《树与有序树》PPT课件.ppt（18页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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时，命题成立。考察时，命题成立。考察|V|=k+1时的情时

4、的情况。设况。设u,v E，我们擦去边，我们擦去边e,得得T的一个子图。的一个子图。令令 V1=vV子图中存在子图中存在u到到v的通路的通路，V2=vV子图中存在子图中存在v到到v的通路的通路。例例定理定理1的证明的证明(续续)l新图分为两个连通的子图新图分为两个连通的子图.因为对于任意的因为对于任意的v V，原图是连通，原图是连通的，所以在原图中存在的，所以在原图中存在 v到到u的通路，也存在的通路，也存在v到到v的通路，的通路，且都是初等通路。若这两条通路都经过边且都是初等通路。若这两条通路都经过边e，则原图中一定有，则原图中一定有圈，故圈，故V=V1 V2。如果存在。如果存在v V1V2

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

6、个顶点的树至少有两片树叶。任何一棵至少含有两个顶点的树至少有两片树叶。证明：设证明：设 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有1个度顶点，有s片树叶，还有(n-s-1)个不少于2度的顶点。由握手定理可知：2(n-1)2(n-s-1)+k+s 可以

7、解出 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连通连通,且且|V|1=|E|。T中无圈中无圈,且且|V|1=|E|。证明：由证明：由 推出推出，由，由 推出推出，再由，再由 推出推出 ，以完成整个定理的证明。，以

8、完成整个定理的证明。T是一棵树，即是一棵树，即T连通且无圈，连通且无圈，由定理由定理1知，有知，有|V|1=|E|。定理2的证明 已知已知T连通且连通且|V|1=|E|。若。若 T中有圈，拿去圈中的中有圈，拿去圈中的一条边，一条边，T仍连通。我们继续这样的工作，直到仍连通。我们继续这样的工作，直到 T中中无圈。由于顶点与边都是有限集，上面的工作一定可无圈。由于顶点与边都是有限集，上面的工作一定可以在有限步内终止。以在有限步内终止。设设T中共拿走中共拿走L条边，由于每次拿去的边都是圈中的边，条边，由于每次拿去的边都是圈中的边，不影响不影响 T的连通性，所以剩下的子图的连通性，所以剩下的子图T是连

9、通且无圈是连通且无圈的图，即的图，即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不连通，设不连通，设 T有有 k个连通分枝：个连通分枝：T1，T2，Tk，Ti=(Vi,Ei),1ik。对于每一个。对于每一个i(1ik),Ti是连通的且无圈，故是连通的且无圈，故Ti是树。

10、由定理是树。由定理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(n-1)/2 可以解出n=4，与已知条件矛盾。例例 画出具有画出具有7个顶点的所有非同构的树个顶点的所有非同构的树解：所画出的树有解：所画出的树有6条边，因而条边，因而7个顶点的度数之和应为个顶点的度数之和

11、应为12。由于每个顶点的度数均大于等于。由于每个顶点的度数均大于等于1，因而可以，因而可以产生一下产生一下7种度数序列：种度数序列：l 1 1 1 1 1 1 6,产生产生1棵非同构的树棵非同构的树T1 l 1 1 1 1 1 2 5,产生产生1棵非同构的树棵非同构的树T2l 1 1 1 1 1 3 4,产生产生1棵非同构的树棵非同构的树T3l 1 1 1 1 2 2 4,产生产生2棵非同构的树棵非同构的树T4、T5l 1 1 1 1 2 3 3,产生产生2棵非同构的树棵非同构的树T6、T7l 1 1 1 2 2 2 3,产生产生3棵非同构的树棵非同构的树T8、T9、T10l 1 1 2 2 2 2 2,产生产生1棵非同构的树棵非同构的树T11例 7阶无向图有3片树叶和1个3度顶点，其余3个顶点的度数均无1和3.试画出满足要求的所有非同构的无向树。解：顶点数为7，边数为6，于是 12=1+1+1+3+d(v4)+d(v5)+d(v6).可知d(vj)=2，j=4,5,6.于是度数列为 1，1，1，2，2，2，3。与3度顶点关联的三个顶点的度数列为：1，1，21，2，22，2，2例 7阶无向图有3片树叶和1个3度顶点，其余3个顶点的度数均无1和3.试画出满足要求的所有非同构的无向树。所求非同构的无向树有三个，见下图。