第十章树与有序树.ppt

第十章 树与有序树,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变成具有两个连通分支的不连通图。这两个连通分支也必然是树，譬如说是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的通路， 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|+|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+3+3+ x1) x=15,定理2,T=(V,E)是一个简单图，以下三条等价。 T是一棵树。 T连通, 且 |V| 1=|E|。 T中无圈, 且 |V| 1=|E|。,证明：由 推出，由 推出 ，再由 推出 ，以完成整个定理的证明。 T是一棵树，即T连通且无圈， 由定理1知，有 |V|1 = |E| 。,定理2的证明,已知T连通且 |V|1=|E| 。若 T中有圈，拿去圈中的一条边， T仍连通。我们继续这样的工作，直到 T中无圈。由于顶点与边都是有限集，上面的工作一定可以在有限步内终止。 设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不连通，设 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是连通图。,例 设G为n阶无向简单连通图，n5， 证明G或G的补图不是树。,证明： 若G或G的补图都是树，则 它们的边数都是 n-1。 于是 (n-1)+(n-1)=n(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棵非同构的树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，2 1，2，2 2，2，2,例 7阶无向图有3片树叶和1个3度顶点，其余3个顶点的度数均无1和3.试画出满足要求的所有非同构的无向树。,所求非同构的无向树有三个，见下图。,