离散数学课件：7-2 树

复习思考题16设无向图G与K3,3同胚，至少从G中删除____条边才能使所得图为平面图。G的对偶图的对偶图不一定与G同构。()设G*是具有k(k2)个连通分支的平面图G的对偶图，已知G的边数m=10,面数r=3,则G*的面数r*=________。5个顶点的非同构无向树有________个。第7章树7.1无向树及生成树7.2根树及其应用无向树的性质

定理7.2

设T是n阶非平凡的无向树，则T中至少有两片树叶.证：

由定理7.1(树的定义)可知树T共有n-1条边，

由握手定理得：设T有k片树叶，则T中的分支点为n-k个，

每个分支点的度数

≥2，从而有下式成立：

由上式解出k2.例题已知无向树T有5片树叶,2度与3度顶点各1个,其余顶点的度数均为4.

求T的阶数n,并画出满足要求的所有非同构的无向树.

解：设4度顶点的个数为k个，则n=5+1+1+k=7+k

树的边数m=

(7+k)-1=6+k

由握手定理得

2m=2(6+k)=51+21+31+4k

解出k=1,

则n=7+k=8.T的度数列为1,1,1,1,1,2,3,4

有3棵非同构的无向树

生成树

设G为无向连通图G的生成树:G的生成子图并且是树。生成树T的树枝:G在T中的边。生成树T的弦:

G不在T中的边。生成树T的余树

:所有弦的集合的导出子图。注意:

不一定连通、不一定不含回路、不一定是树。T的余树G生成树T定理

任何无向连通图都有生成树。推论

设n阶无向连通图有m条边，

则mn1.可用避圈法构造基本回路与基本回路系统

基本回路设T是连通图G的一棵生成树,

对每一条弦e,存在惟一的由弦e和T的树枝构成的初级回路Ce,称Ce为对应于弦e的基本回路.基本回路系统——所有基本回路的集合。求基本回路的算法:设弦e=(u,v),先求T中u到v的路径uv,再并上弦e,即得对应e的基本回路.

基本回路与基本回路系统实例图中红边为一棵生成树,求对应它的基本回路系统。解：

弦e,f,g对应的基本回路分别为

加e

得基本回路Ce=e

b

c,

加f

得基本回路Cf=f

a

b

c,

加g得基本回路Cg=g

a

b

c

d,

则：C基={Ce,Cf,Cg}.

回路合并合并回路C1和C2(C1C2):

C1C2是C1和C2上的边的对称差构成的(一条或几条)回路.基本回路的性质连通图中的任一条回路都可以表成对应它所含弦的基本回路的合并.例如,Ce=bce

Cf=abcfCg=abcdg

CeCf=aefCeCg

=aedg

CfCg

=fdg

CeCfCg

=bcdgfe基本割集与基本割集系统基本割集设T是连通图G的一棵生成树,对T的每一条树枝a,存在惟一的由树枝a,其余的边都是弦的割集Sa,称Sa为对应树枝a的基本割集。基本割集系统——是所有基本割集的集合。基本割集的算法

设a为生成树T的树枝,Ta由两棵子树T1与T2组成,

Sa={e|eE(G)且e的两个端点分别属于T1与T2}.基本割集与基本割集系统实例例图中红边为一棵生成树,

求对应它的基本割集系统解：

树枝a,b,c,d对应的基本割集为

Sa={a,f,g},

Sb={b,e,f,g},

Sc={c,e,f

g},

Sd={d,g},

S基={Sa,Sb,Sc,Sd}.基本割集的性质连通图中的任一割集都可以表成对应它所含树枝的基本割集的对称差.例如：Sa={a,f,g},

Sb={b,e,f,g},

Sc={c,e,f

g},

Sd={d,g},

SaSb={a,b,e}

SaSc={a,e,c}

SbSd={b,e,f,d}无向图与最小生成树

定义

对无向图或有向图的每一条边e附加一个实数w(e),称作边e的权.

图连同附加在边上的权称作带权图,记作G=<V,E,W>.

设T是G的生成树,T所有边的权的和称作T的权,记作W(T).最小生成树:带权图中权最小的生成树。可用避圈法构造最小生成树的应用最小生成树聚类算法设有一组数据D={a1,a2,…an},D中的任意两个数据ai,aj的相似程度可以用一个相似度函数d(ai,aj)来度量，称为这两个数据的距离。给定一个正整数k(1<k<n)，D的一个k聚类是D的一个k划分

，使得同一子类中的数据间的距离尽可能地“近”，不同子类的数据间的距离尽可能地“远”。7.2根树及其应用有向树:基图为无向树的有向图.根树:有一个顶点入度为0,其余的入度均为1的非平凡的有向树.树根:

有向树中入度为0的顶点.树叶:

有向树中入度为1,出度为0的顶点.内点:

有向树中入度为1,出度大于0的顶点.分支点:树根与内点的总称.根树根树的画法:树根放上方,省去所有有向边上的箭头如右图所示

a是树根

b,e,f,h,i是树叶

c,d,g是内点

a,c,d,g是分支点

第0层：a

第1层：b，c

第2层：d，e,

f

第3层：g，h

第4层：i

树高：4

根树顶点v的层数在根树中，从树根到任意顶点v只能有唯一的一条路，这条路的长度称为v的级(层)数。树高:有向树中顶点的最大层数。家族树把根树看作一棵家族树:(1)若顶点a邻接到顶点b,则称b是a的儿子,a是b的父亲;(2)若b和c为同一个顶点的儿子,则称b和c是兄弟;(3)若ad且a可达d,则称a是d的祖先,d是a的后代.根子树设v为根树的一个顶点且不是树根,称v及其所有后代的导出子图为以v为根的根子树.

根树的分类k叉树:根树的每个分支点至多有k

个儿子k叉正则树:根树的每个分支点恰有k

个儿子k叉完全正则树:树叶层数相同的k

叉正则树二叉树二叉正则树二叉完全正则树根树的分类有序树:将根树同层上的顶点规定次序.k

叉有序树:有序的k叉树.k

叉正则有序树:有序的k叉正则树.k

叉完全正则有序树:有序的k叉完全正则树.二叉有序树二叉正则有序树二叉完全正则有序树12123412121234123456781212312最优2叉树

定义设2叉树T有t片树叶v1,v2,…,vt,树叶的权分别为w1,w2,…,wt,称为T的权,其中l(vi)是vi的层数.

在所有t片树叶、带权w1,w2,…,wt

的2叉树中,权最小的2叉树称为最优2叉树。赋权二叉树权值的计算T1、T2和T3都是带权2,2,3,3,5的二叉树，

W(T1)=(2＋2

＋3)×2＋(3＋5)×3=38W(T2)=(3＋5)×4＋3×3＋2×2＋2×1=47W(T3)=(3＋3)×3＋(5＋2＋2)×2=36注意：T1、T2和T3都不是最优二叉树!

求最优树的算法--Huffman算法给定t片树叶的权为w1,w2,…,wt且w1≤w2≤…≤wt。连接权为w1，w2的两片树叶，得一分枝点，其权为w1＋w2

在w1＋w2，w3，…，wt中选出两个最小的权，连接它们对应的结点(不一定是树叶)，得新分枝点及所带的权。重复②，直到形成t–1个分枝点，t片树叶为止。W(T)等于所有分支点的权之和求带权为2,2,3,3,5的最优二叉树.

W(T)=342243365915m叉正则树中

m与树叶数t、分支节点数s的关系在m叉正则树中，其树叶数为t，分支点数为s，则(m-1)s=t-1。证明：由所给条件知，该树有s＋t个结点，由树的性质知，该树边数为s＋t-1。另一方面，由m叉正则树定义知：该树出度之和为=ms=该树的边数于是有ms=s＋t-1。整理后有(m-1)s=t-1。二叉正则树Huffman算法的推广算法求一棵带权为1，2，3，4，5，6，7的最优3叉树W(T)=(1+2+3+4+5+6)×2+7×1=491234567这是三叉正则树61521求一棵带权为1，2，3，4，5，6，7，8的最优3叉树W(T)=(1+2+3)×3+(7+8+4+5+6)×2=7812345678这不是三叉正则树Huffman算法的推广算法6152136是最优3叉树?求一棵带权为1，2，3，4，5，6，7，8的最优3叉树W(T)=(1+2)×3+(3+4)×2+(5+6+7)×2+8×1=673456712这不是三叉正则树8Huffman算法的推广算法3101836Huffman算法的推广算法34567128m叉正则树的分支点数s与树叶t之间满足(m-1)s=t-1求m叉最优树时应分两种情况讨论

为整数时，说明所求树T为m叉正则树，可仿Huffman算法求最优m叉树。

余数为k时(1km-2)，说明所求树T为非正则树，此时将

k+1个较小的权对应的

树叶作为兄弟放在最高层次上，

然后仿Huffman算法即可。

二叉树的应用1在英文中有些字母使用频率较高，另一些字母使用频率较低。为了减少通信中传递的信息量，人们希望用位数较少的二进制数表示频繁使用的字符，用位数较多的二进制数表示不常使用的字符。这样就会大大缩短信息串的总长度。但是也产生了一个问题。接收者如何将0、1组成的长串，准确无误地分割成字母对应的0、1序列呢？如：”00”—e，”01”—t，”0001”—q。则接收到”0001”时，是et，还是q?为了解决这个问题，引入前缀码的概念。二叉树的应用1——前缀码

设

=12…n-1n是长度为n的符号串的前缀:12…k

,k=1,2,…,n-1

前缀码:{1,2,…,m},

其中1,2,…,m为非空字符串,且任何两个互不为前缀。2元前缀码:只出现两个符号(如0与1)的前缀码。如{0,10,110,1111},{10,01,001,110}是2元前缀码。{0,10,010,1010}不是前缀码。1011111000110前缀码一棵2叉树产生一个二元前缀码:对每个分支点,若关联2条边,则给左边标0,右边标1;若只关联1条边,则可以给它标0(看作左边),也可以标1(看作右边).将从树根到每一片树叶的通路上标的数字组成的字符串记在树叶处,所得的字符串构成一个前缀码.右图的树叶都互为前缀码0001001101101001100最佳前缀码设要传输的电文中含有t个字符,

字符ai出现的频率为pi,它的编码的长度为li,

则100个字符的电文的编码的期望长度是100最佳2元前缀码——编码期望长度最小的2元前缀码在用2叉树产生2元前缀码时,每个二进制串的长度等于它所在树叶的深度,则权为100p1,100p2,,100pt的最优2叉树产生的2元前缀码是最佳2元前缀码.于是,给定字符出现的频率,可用Huffman算法产生最佳2元前缀码.最佳前缀码的