离散数学第十六章课件

第十六章

树主要内容无向树及其性质生成树根树及其应用

116.1无向树及其性质定义16.1

(1)无向树——连通无回路的无向图(2)平凡树——平凡图(3)森林——至少由两个连通分支（每个都是树）组成的无向图(4)树叶——1度顶点(5)分支点——度数2的顶点

2无向树的等价定义定理16.1设G=<V,E>是n阶m条边的无向图，则下面各命题是等价的：(1)G是树(2)G中任意两个顶点之间存在惟一的路径.(3)G中无回路且m=n1.(4)G是连通的且m=n1.(5)G是连通的且G中任何边均为桥.(6)G中没有回路，但在任何两个不同的顶点之间加一条新边，在所得图中得到惟一的一个含新边的圈.3由上式解出x2.

定理16.2设T是n阶非平凡的无向树，则T中至少有两片树叶.无向树的性质证设T有x片树叶，由握手定理及定理16.1可知，4例题例1已知无向树T中有1个3度顶点，2个2度顶点，其余顶点全是树叶，试求树叶数.解解本题用树的性质m=n1，握手定理.设有x片树叶，于是n=1+2+x=3+x,2m=2(n1)=2(2+x)=13+22+x解出x=3，故T有3片树叶.5例2已知无向树T有5片树叶，2度与3度顶点各1个，其余顶点的度数均为4，求T的阶数n例题解设T的阶数为n,则边数为n1，4度顶点的个数为n7.由握手定理得2m=2(n1)=51+21+31+4(n7)解出n=8，4度顶点为1个.6子图定义14.8

G=<V,E>,G=<V,E>(1)GG——G为G的子图，G为G的母图(2)若GG且V=V，则称G为G的生成子图(3)若VV或EE，称G为G的真子图(4)V（VV且V）的导出子图，记作G[V](5)E（EE且E）的导出子图，记作G[E]在图中，设G为(1)中图所表示，取V1={a，b，c}，则V1的导出子图G[V1]为(2)中图所示。取E1={e1，e3}，则E1的导出子图G[E1]为(3)中图所示。7不一定连通，也不一定不含回路，如图所示定义16.2设G为无向图(1)G的树——T是G的子图并且T是树(2)G的生成树——T是G的生成子图并且T是树(3)生成树T的树枝——G的在T中的边(4)生成树T的弦——G的不在T中的边(5)生成树T的余树——T的所有弦的导出子图16.2生成树8推论2

的边数为mn+1.推论3

为G的生成树T的余树，C为G中任意一个圈，则C与一定有公共边.证否则，C中的边全在T中，这与T为树矛盾.定理16.3无向图G具有生成树当且仅当G连通.生成树存在条件推论1

G为n阶m条边的无向连通图，则mn1.证必要性显然.充分性用破圈法（注意：在圈上删除任何一条边，不破坏连通性）由定理16.3和树的边数等于顶点数减1可立即得到下述推论。9基本回路系统定理16.4设T为G的生成树，e为T的任意一条弦，则Te中含一个只有一条弦其余边均为T的树枝的圈.不同的弦对应的圈也不同.证设e=(u,v)，在T中u到v有惟一路径，则e为所求的圈.定义16.3设T是n阶m条边的无向连通图G的一棵生成树，设e1,e2,…,emn+1为T的弦.设Cr为T添加弦er产生的只含弦er、其余边均为树枝的圈.称Cr为G的对应树T的弦er的基本回路或基本圈，r=1,2,…,mn+1.并称{C1,C2,…,Cmn+1}为G对应T的基本回路系统，称mn+1为G的圈秩，记作

(G).求基本回路的算法：设弦e=(u,v)，先求T中u到v的路径uv，再并上弦e，即得对应e的基本回路.10Ca=aefCb=bdeCc=cdf此图的圈秩为3，基本回路系统为：{Ca,Cb,Cc}基本回路系统在下图中，对应生成树的弦a，b，c的基本回路为：11基本割集的存在定理16.5设T是连通图G的一棵生成树，e为T的树枝，则G中存在只含树枝e，其余边都是弦的割集，且不同的树枝对应的割集也不同.证由定理16.1可知，e是T的桥，因而Te有两个连通分支T1和T2，令

Se={e|eE(G)且e的两个端点分别属于V(T1)和V(T2)}，由构造显然可知Se为G的割集，eSe且Se中除e外都是弦，所以Se为所求.显然不同的树枝对应的割集不同.12定义16.4设T是n阶连通图G的一棵生成树，e1,e2,…,en1为T的树枝，Si是G的只含树枝ei的割集，则称Si为G的对应于生成树T由树枝ei生成的基本割集，i=1,2,…,n1.并称{S1,S2,…,Sn1}为G对应T的基本割集系统，称n1为G的割集秩，记作(G).基本割集与基本割集系统求基本割集的算法设e为生成树T的树枝，Te为两棵小树T1与T2，令Se={e|eE(G)且e的两个端点分别属于T1与T2}则Se为e对应的基本割集.13Sa={a,f,g}Sb={b,g,h}Sd={d,h,i}Sc={c,f,h}Se={e,f,i}基本割集系统为：{Sa,Sb,Sc,Sd,Se}割集秩为5.基本割集与基本割集系统在下图中，对应树枝a，b，c，d，e的基本割集分别为：14解弦e,f,g对应的基本回路分别为

Ce=e

b

c,Cf=f

a

b

c,Cg=g

a

b

c

d,C基={Ce,Cf,Cg}.树枝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}.

例下图实线边所示为生成树，求基本回路系统与基本割集系统实例15最小生成树定义16.5

T是无向连通带权图G=<V,E,W>的生成树(1)T的权W(T)——T的各边权之和(2)G的最小生成树——G的所有生成树中权最小的生成树求最小生成树的一个算法避圈法（Kruskal）设G=<V,E,W>，将G中非环边按权从小到大排序：e1,e2,…,em.(1)取e1在T中(2)查e2，若e2与e1不构成回路，取e2也在T中，否则弃去e2.(3)再查e3,…,直到得到生成树为止.16例4求图的一棵最小生成树.所求最小生成树如图所示，W(T)=38.实例1716.3

根树及其应用定义16.6有向树T——基图为无向树的有向图。(1)T为根树——T中一个顶点入度为0，其余顶点入度均为1的有向树.(2)树根——入度为0的顶点(3)树叶——入度为1，出度为0的顶点(4)内点——入度为1，出度不为0的顶点(5)分支点——树根与内点的总称(6)顶点v的层数——从树根到任意顶点v的路径的长度（即路径中的边数）(7)树高——T中所有顶点的最大层数(8)平凡根树——平凡图18根树的画法:树根放上方,省去所有有向边上的箭头如右图所示a是树根b,e,f,h,i是树叶c,d,g是内点a,c,d,g是分支点a为0层;1层有b,c;2层有d,e,f;3层有g,h;4层有i.树高为4根树实例19家族树与根子树定义16.7设T为一颗非平凡的根树(1)祖先与后代——vi

，vj

∈V(T)，vi

≠vj，若vi

可达vj

，则称vi

为vj的祖先

，vj为vi的后代

。(2)父亲与儿子——vi

，vj

∈V(T)，vi

≠vj，若vi

邻接到vj（即<vi

，vj

>∈E(T)）

，则称vi

为vj的父亲

，vj为vi的儿子

。(3)兄弟——vj

，vk∈V(T)，vj

≠vk，若vj

，vk的父亲相同

，则称vj与vk是兄弟

。定义16.8设v为根树T中的任意一个顶点，称v及其后代的导出子图Tv为T的以v为根的根子树.常将根树看成家族树，家族中成员之间的关系由下面的定义给出：20根树的分类(1)T为有序根树——同层上的顶点都标定次序的根树(2)根据根树T中的每个分支点儿子数以及是否有序，可以将根树分为下列各类：①r叉树——每个分支点至多有r个儿子②r叉有序树——r叉树是有序的③r叉正则树——每个分支点恰有r个儿子④r叉正则有序树——又若r叉正则树是有序的⑤r叉完全正则树——树叶层数相同的r叉正则树⑥r叉完全正则有序树——又若r叉完全正则树是有序的

2叉正则有序树的每个分支点的两个儿子导出的根子树分别称为该分支点的左子树和右子树。在所有的r叉树中，最常用的是2叉树。下面介绍2叉树的应用。21定义16.9

设2叉树T有t片树叶v1,v2,…,vt，权分别为w1,w2,…,wt，称为T的权，其中l(vi)是vi的层数.在所有有t片树叶，带权w1,w2,…,wt的2叉树中，权最小的2叉树称为最优2叉树.最优二叉树求最优2叉树的算法——Huffman算法给定实数w1,w2,…,wt，且w1w2…wt.（1）作t片树叶,分别以w1,w2,…,wt为权.（2）在所有入度为0的顶点(不一定是树叶)中选出两个权最小的顶点,添加一个新分支点,以这2个顶点为儿子,其权等于这2个儿子的权之和.（3）重复（2）,直到只有1个入度为0的顶点为止.W(T)等于所有分支点的权之和22例5求带权为1,1,2,3,4,5的最优树.解题过程由下图给出，W(T)=38最优二叉树的算法——Huffman算法23最佳前缀码定义16.10设12…n-1n是长度为n的符号串(1)前缀——该符号串的子串1,12,…,12…n1

(2)前缀码——符号串集合A={1,2,…,m}中的任意两个符号串都互不为前缀(3)二元前缀码——i(i=1,2,…,m)中只出现两个符号，如0与1.如何产生二元前缀码？定理16.6一棵2叉树产生一个二元前缀码.推论一棵正则2叉树产生惟一的一个二元前缀码（按左子树标0，右子树标1）24一棵2元树产生一个二元前缀码:对每个分支点,若关联2条边,则给左边标0,右边标1;若只关联1条边,则可以给它标0(看作左边),也可以标1(看作右边).将从树根到每一片树叶的通路上标的数字组成的字符串记在树叶处,所得的字符串构成一个前缀码，如右图所示：树的编码：最优2进制编码：使信息传递的2进制数最短由最优2叉树产生的前缀码为最佳前缀码。用最佳前缀码传输的二进制位数最省。最佳前缀码25图所示二叉树产生的前缀码为{00,10,11,011,0100,0101}二叉树产生的前缀码26用Huffman算法产生最佳前缀码例16.7在通信中，八进制数字出现的频率如下：0：25%1：20%2：15%3：10%4：10%5：10%6：5%7：5%求传输它们的最佳前缀码，并求传输10n（n2）个按上述比例出现的八进制数字需要多少个二进制数字？若用等长的（长为3）的码字传输需要多少个二进制数字？27解用100个八进制数字中各数字出现的个数，即以100乘各频率为权，并将各权由小到大排列，得w1=5,w2=5,w3=10,w4=10,w5=10,w6=15,w7=20,w8=25。用Huffman算法求以频率(乘以100)为权的最优2叉树。用此权产生的最优2叉树如下图所示：求最佳前缀码传100个按比例出现的八进制数字所需二进制数字的个数为W(T)=285，传10n(n2)个按比例出现的八进制数字需要2.8510n个二进制数字，用等长码(长为3)传输需310n个二进制数字.01-----011-----1001-----2100-----3101-----40001-----500000-----600001-----7它产生的最优前缀码28波兰符号法与逆波兰符号法行遍或周游根树T——对根树T的每个顶点访问且仅访问一次.对于2叉有序正则树有以下三种周游方式：①中序行遍法——访问的次序为：左子树、根、右子树②前序行遍法——访问的次序为：根、左子树、右子树③后序行遍法——访问的次序为：左子树、右子树、根对如右图所示的根树T（2叉有序正则树）按中序、前序、后序行遍的周游结果分别为：

b

a(f

d

g)c

e，

a

b(c(d

f

g)e)，

b((f

g

d)e

c)a29用2叉有序正则树存放算式存放规则最高层次运算放在树根然后依次将运算符放在根子树的根上数放在树叶上规定：被除数、被减数放在左子树树叶上

算式((b+(c+d))a)((ef)(g+h)(ij))存放在如上图所示的2叉有序正则树上.30波兰符号法波兰符号法按前序行遍法访问存放算式的2叉有序正则树，其结果不加括号，规定从右到左每个运算符对它后面紧邻的两个数进行运算。在这种算法中，由于运算符在它的两个运算对象之前，所以称此种算法为前缀符号法或波兰符号法.对下图的访问结果为

b+c

d

a

e

f

+g

h

i

j

逆波兰符号法按后序行遍法访问存放算式的2叉有序正则树，其结果不加括号，规定从左到右每个运算符对它前面紧邻的两个数进行运算。在这种算法中，由于运算符在它的两个运算对象之后，所以称此种算法为后缀符号法或逆波兰符号法.对上图的访问结果为b

c

d++a

e

f

g

h+i

j

31重点主要内容无向树及其性质生成树、最小生成树、基本回路系统、基本割集系统根树及其分类、最优树、二叉树产生的前缀码、最佳前缀码、波兰符号法、逆波兰符号法基本要求深刻理解无向树的定义及性质熟练地求解无向树准确地求出给定带权连通图的最小生成树深刻理解基本回路、基本割集的概念，并会计算理解根树及其分类等概念熟练掌握求最优树及最佳前缀码的方法掌握波兰符号法与逆波兰符号法32第十六章习题课主要内容无向树及其性质生成树、最小生成树、基本回路系统、基本割集系统根树及其分类、最优树、最佳前缀码、波兰符号法、逆波兰符号法基本要求深刻理解无向树的定义及性质熟练地求解无向树准确地求出给定带权连通图的最小生成树深刻理解基本回路、基本割集的概念，并会计算理解根树及其分类等概念会画n阶（n较小）非同构的无向树及根树（1n6）熟练掌握求最优树及最佳前缀码的方法掌握波兰符号法与逆波兰符号法33（2）（3）从而解出练习11.无向树T有ni个i度顶点，i=2,3,…,k，其余顶点全是树叶，求T的树叶数.解用树的性质：边数m=n1（n为阶数），及握手定理.(1)342．设n阶非平凡的无向树T中，(T)

k，k1.证明T至少有k片树叶.证反证法.否则，T至多有s片树叶，s<k，下面利用握手定理及树的性质m=n1推出矛盾.由于(T)

k，故存在v0，d(v0)

k.于是，由此解出s

k，这与s<k矛盾.证本题的方法有多种，请用分支点都是割点来证明.练习2353．设G为n阶无向简单图，n5，证明G或中必含圈.本题的方法很多