第十章树与有序树.pptVIP

例 设T为树，最大度△≥k，这里k≥1，证明T至少有k片树叶。 证明：假设T有s片树叶，sk。 记T的顶点数为n，则 T有1个△度顶点，有s片树叶， 还有(n-s-1)个不少于2度的顶点。 由握手定理可知： 2(n-1) ≥2(n-s-1)+k+s 可以解出 s≥k，这与假设sk矛盾。 例 设G为n阶无向简单连通图，n≥5， 证明G或G的补图不是树。 证明： 若G或G的补图都是树，则 它们的边数都是 n-1。 于是 (n-1)+(n-1)=n(n-1)/2 可以解出n=4，与已知条件矛盾。 例 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.试画出满足要求的所有非同构的无向树。 所求非同构的无向树有三个，见下图。 第十章 树与有序树 10.1 树的基本概念 10.2 连通图的生成树和带权连通图的最小生成树 10.3 有序树 10.4 前缀码和最优二分树 例 Peter Godfried Betty Albert Mary Marivin Doris Judy Hal Denise Gregory 树的定义 一个无向图若连通且不含圈，则称它为一棵树，记为 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={v?V│子图中存在u’到v的通路}， V2={v?V│子图中存在v’到v的通路}。 例 定理1的证明(续) 新图分为两个连通的子图. 因为对于任意的v?V，原图是连通的，所以在原图中存在 v到u’的通路，也存在v到v’的通路，且都是初等通路。若这两条通路都经过边e，则原图中一定有圈，故V=V1∪V2 。如果存在v ? V1∩V2，则原图中存在 v到u’、v到v’的两条不经过边e的初等通路，加上边e后, 原图中一定有圈，故V1∩V2 =?。 新图分为两棵不相交的树. 原图无圈，子图也不会有圈，即为两棵不相交的树(顶点的交集为空集)。 设T1=(V1,E1)，T2=(V2,E2)，由归纳假定有 |V1|-1=|E1|，|V2|-1=|E2|。 又|V|=|V1|+|V2|，|E|=|E1|+|E2|+1。所以有定理得证。 定理1的推论 任何一棵至少含有两个顶点的树至少有两片树叶。 证明：设 T=(V,E)是一棵树，若T中最多只有一片树叶，则有 ∑d(v) ≥1+2(|V|-1)=2|E|+1, 这与结论 ∑ d(v) =2|E| 矛盾! 矛盾说明 T 不止一片树叶。 v?V v?V 例2