第三章 树及其应用(新)

1、第三章 树及其应用第一节 树的基本概念,定义1 树是无圈连通无向图. 树中度数为1的结点称为树的叶.树中度数大于1的结点称为树的分枝点或内点. 不相交的若干树称为森林, 即森林的每个连通分枝是树. 定理1 T是树T中无环,且任何两结点间有且仅有一条路.,证:1.()必要性:因为T是树,故对T中任意不同的两个结点x,y之间至少存在一条路.若x,y之间存在T中两条不同的路P1和P2,则P1和P2中至少有一边不同,不妨设eP1,但eP2.设e=u,v,显然在P1和P2的并中删去e后的图仍然连通,故在P1P2-e中存在uv路P,所以P+e是圈,矛盾. 2.充分性:只需证明T中无圈即可.若T中有圈C,当

2、C只有一个结点时,则T中有环;若C中有两个结点,则T中有平行边;若V(C)3,则对C中的任意两个结点,均有两条不同的路,矛盾,因此,T是无圈连通图,即T是树.,定理2 T是树T连通对 有W(T-e)=2. 证明:1.必要性:若T是树,由定理1,T连通,且T中无环和无平行边,故T为简单连通图.设e=x,y,则W(T-e)2.又由定理1,xey是T中唯一xy路,故则W(T-e)2.所以W(T-e)=2 2.充分性:只需证明T中无圈即可.若T中有圈C,且e=x,yE(C),又W(T-e)=2,所以1=W(C-e) W(T-e)=2,矛盾.所以T连通无圈,从而T是树.,定理3 T是树T连通且 =|E|

3、=n-1,其中为T的边数,n为T的顶点数.,证明:必要性: 若T是树,由定理2,对T中的任意一条边e,有W(T-e)=2,故当在T中删去n-1条不同的边时,有W(T-e1-e2-en-1)=n,有树中无圈,此时n个连通分支即为n个孤立结点,从而有=n-1. 充分性: 若n=1,显然=0;若n=2,显然=1;此时结论显然成立.设任何n阶且边数=n-1的连通图不含圈.则对n+1阶且边数=n的连通图T,显然(T) 1.若(T) 2,则2 = 2n = 矛盾.故存在x V(T),使得Deg(x) =1.从而T-x是n阶图,且T-x只有n-1条边. 由归纳假设T-x不含圈, 从而T为不含圈的连通图,即T

4、为树.,推论 T是森林 =n-w,其中为T的边数, n为T的顶点数,w为T的连通分枝数.,定理4 设T是n阶非平凡树(平凡图称为平凡树),则T中至少有2片树叶. 证明:设T是n阶非平凡树,则(T) 1,并设T有 条边,k片树叶,则 又=n-1,故k 2.,定义2 设T是有向图,若T的基础图是树,称T是有向树. 定义3 仅一个结点的入度为0,其余所有结点的入度都为1的有向树称为根树.入度为0的结点称为根.出度为0的结点(度数为1的结点)仍称为叶;出度不为0的结点称为分枝点或内点.由根到某一顶点v的有向路的长度,称为v的层数.根树的高度就是顶点层数的最大值.,例1 用根树可以表示家庭之间的关系.（

5、p94）,定义4 如果在根树中规定了每一层上顶点的次序, 这样的根树称为有序树. 规定同一层次的定点的次序从左到右（即不能互换）也可以用边的次序代替顶点的次序.（p95） 定义5 每个结点的出度不大于m的有序根树称为m叉树,每个结点的出度恰好为m或0的m叉树称为完全m叉树.所有树叶层次相同的完全m叉树称为正则m叉树.,定理5 设T是完全m叉树,且T的树叶数为t,分枝点数为i,则(m-1)i=t-1.,证明:在完全m叉树中,每片叶子的度数为1,根的度数为m,其余每个分枝点的度数为m+1,并设T有条边,则 2=t+m+(i-1)(m+1),又=t+i-1, 故 (m-1)i=t-1.,定义6 图G

6、的一个顶点v的离径R(v)定义为: 图G的半径R(G)定义,所有满足R(v)=R(G)的顶点v都称为G的中心.显然一个 图的直径为: . 例2.求下图G的每个结点的离径及图G的直径,半径和中 心.,定理6 设P=u1u2ulul+1是树T的一条最长路,则 (1)T的直径为l; (2)若l为奇数,设l=2k-1,则T的半径为k,T有两个相邻的中心,即为ukuk+1.并且每一条长为l的路都通过这两个中心. (3)若l为偶数,设l=2k,则T的半径为k,T中只有一个中心,即为uk+1.并且每一条长为l的路都通过该中心.,定理6的证明,证:(1)由于P=u1u2ulul+1是T中的一条最长路,故d(u

7、1,ul+1) =l 即为T的直径. (2)设u是T中的任意一个结点,则 d(u,u1)+d(u,u2k)= d(u1,u)+d(u,u2k) d(u1,u2k)=2k-1, 因此 u的离径R(u) k.从而T的半径R(T) k. 对于T中任意一个结点u,若u在P上,显然有d(u,uk)k.若u不在P上,由T的连通性,P中必存在一个顶点ui(2 i 2k-1=l),T中有一条连接u与ui的路Q,使u1,.,ui-1,ui+1,u2k都不在Q上. 因为P是T中的最长路,故有:,d(u,ui) i-1; d(u,ui) l+1-i 若i k,因为d(ui,uk)=k-i,故 d(u,uk)=d(u

8、,ui)+d(ui,uk) i-1+k-ik,则d(u,uk)=d(u,ui)+d(ui,uk) l+1-i+i-k= l+1-k=2k-k=k(l=2k-1) 所以对T中的任意结点u有d(u,uk) k,故R(uk) k, 从而R(T) k.综合上述论证得R(T) =k, 且R(uk)=k, 即uk为T的一个中心.同 理可证uk+1为T的一个中心. 下证长为l的任意一条路P一定过中心uk与uk+1. 设P的两个端点分别是u和u,则u和u均不在P上.对P上的任意两个内部点ui和uj,由T的连通性,T中一定存在u-ui路Q1和u-uj路Q2,使得 (V(Q1)-ui)V(P)=; (V(Q2)-

9、uj)V(P)=. 不妨设i j.因为T是树,故P=Q1P(ui,uj) Q2. 若i j k,则 d(u,u) d(u,ui)+ d(ui,uj)+ d(uj,u) (i-1)+(j-i)+(j-1)=2(j-1) 2(k-1)2k-1=l 同理,若ki j,则d(u,u) l.与P为长是l的u-u路矛 盾.因此i kj,所以 结论正确. 同理可证(3).,例2.平面上有n(n 3)条线段,其中任意三条都有公共端点.证明 这n条线段有一个公共端点.,证明:将n条线段的端点视为一个图G的顶点,线段为G的边. 当n=3时,结论显然成立.若n=k时结论成立,即若k条线段中的任意三条线段有一个公共端

10、点,则这K条有一个公共端点v0.当n=k+1时,在k条边的基础上增加一条边ek+1,下证ek+1也过结点v0.反设ek+1不过结点v0.由题设,任意三条都有公共结点.故ek+1至少应与另外k条边中的一条有公共结点,不妨设ek+1与e1有公共端点v1.此时ek+1最多还能与其余的k-1条中的一条有公共结点,不妨设为e2,显然ek+1与e3无公共结点,故ek+1,e1,e3无公共结点,矛盾.故ek+1也过结点v0.综上所述,结论正确.,第二节 支撑树的计数,定义1 若T是G的一个生成子图且又是一棵树,则称T是图G的一棵生成树或支撑树.生成树T中的边称为T的树枝,不在生成树T中的G的边,称为树T的弦

11、. 定理1 图G有生成树G为连通图. 定义2 设D是无环有向图,且D有n个结点条边.在D的关联矩阵Mn中划去任意结点x所对应的行,得到一个(n-1) 阶矩阵Mx,称Mx为D的一个基本关联矩阵.,定理2 已知两个矩阵A=(aij)mn,B= (bij)nm.若mn,则det(AB)=i(AiBi).,其中Ai和Bi都是m阶行列式, Ai是从A中取不同的m列所成的行列式,Bi是从B中取相应的m行所构成的行列式. 定理3 设Bk是弱有向图D的某个基本关联矩阵,则 D的不同支撑树的数目是det(BkBkT),其中BkT是Bk 的转置.,例1 图D如下图所示.解答下列问题:(1)求D的不同生成树的数目;

12、(2)求D的不含边e4的不同生成树的数目;(3)求D的必包含边e3的不同生成树的数目;,v1 e1 v2 e2 e3 e4 v4 e5 v3,说明:(1)记C=BkBkT=(Cij),ik,j k,则 (2)对于连通无向图G的支撑树计数,只需考虑G的定向图.（p102例） 定理4 有向弱连通图D中以vk为根的不同支撑树数目为 表示D的vk的基本关联矩阵 Bk中将全部1元素改为0元素之后的矩阵.,第三节 求连通简单图的生成树深度优先搜索和广度优先搜索,深度优先搜索:任意选择图G的一个顶点为根,通过不断地增加边来形成以顶点v0为起点的路,直到这条路经过图G的每个顶点,此时得到的这条路就是该图的生成

13、树.其中每条新边都与路上的一个顶点以及不在路上的一个顶点关联.如果这条路不经过图G的所有顶点,则返回倒数第二个顶点,继续重复上面过程,直到不能添加更多的边为止.又图G是有有限边数的连通图,故最后总能产生一棵生成树.,例1 用深度搜索来找出下图G的生成树,广度优先搜索,基本思想:从图的顶点中任意地选择一个根,然后添加与该顶点相关联的所有边,在这个阶段添加的新顶点成为生成树里1层上的顶点,任意地排序它们.下一步,按顺序访问1层上的每一个顶点,只要不产生回路,就添加与这个顶点相关联的每条边,这样就产生了树里2层上的顶点.遵循这样的原则继续下去,经有限步骤后(因为图中只有有限条边)就产生了生成树. 例

14、2. 用广度优先搜索找出例1中图G的生成树.P106,第四节 最小支撑树,定义1:连通加权图里权和最小的支撑树称为最小支撑树. 最小支撑树的实际应用背景:在某一国家或地区,需建造一铁路网/公路网把一些城市连接起来,需要总长度最短或造价最低. 寻找最小支撑树的贪心算法原理:通过添加还没使用过的具有规定性质且权最小的边来进行的,其实质就是在每步上进行最优选择,即“局部最优化”.,普林算法,算法的基本思想:首先选择带最小权的边,把它放进支撑树里.相继向树里添加带最小权的边,这些边与已在树里的顶点相关联,并且不与已在树里的边形成圈,直到添加了n-1条边止.算法描述如下:算法1 普林算法 Procedu

15、re prim(G:带n个顶点的连通无向图) T:=权最小的边 For i:=1 to n-2 begin e:=与T里顶点相关联的权最小的边,并且若添加到T 里则不形成圈. T:=添加e之后的T endT是G的最小支撑树,例1 用普林算法求下图所示的最小支撑树,定理1 普林算法是正确的,即在算法结束时,得到一棵最小支撑树.(证略),克鲁斯卡尔(Kruskal)算法,算法的基本思想: 选择图中最小的一条边,相继添加不与已经选择的边形成圈的权最小的边,直到挑选n-1(n为结点的个数)条边为止. 该算法的伪代码如下: Procedure Kruskal (G:n个顶点的连通加权无向图) T:=空图

16、. For i:=1 to n-1 begin E:=当添加到T里时不形成圈的G里权最小的边 T:=添加e之后的T EndT是G的最小支撑树,定理2 由Kruskal算法构作的任何生成树T=Ge1,e2,en-1都是G的最小生成树,n为G的结点数.,基于破圈法的最小生成树的生成方法,该方法是由管梅谷教授给出的,其基本思想为:设G是连通加权简单图,若G不是树,则G中必含有回路,删去G中含于某回路内权最大的一条边,所得的图记为G1,G1是G的连通生成子图.下一步,若G1不是树,又从G1某个回路内删去权最大的一条边,如此下去,最后不能按上述方式删边时,得到的图T便是G的一棵生成树. 定理3 由破圈法

17、最后得到的图T为G的一棵最小生成树.（证略）,第五节 前缀码,定义1 设T是有t片叶子的二叉树,其中t片叶子分别带有权1, 2, t,称T为加权二叉树,称 为二叉树T的权,其中li为带权i的树叶vi的层数.在所有带权1, 2, t的二叉树中,带权最小的二叉树称为最优二叉树. 1952年,哈夫曼给出了求最优二叉树的算法,该算法的核心思想为:从带权1+ 2, 3, t的最优二叉树可得到带权1, 2, t的最优二叉树.,哈夫曼算法的步骤,给定实数1, 2, t且12 t (1)连接1, 2 为权的两片叶子,得一分枝点,其权为1+ 2. (2)在1+ 2, 3, t中选出两个最小的权,连接它们对应的顶

18、点(不一定都是树叶)得分枝点及所带的权. (3)重复(2),直到形成t-1个分枝点,t片叶子为止.,引理1 存在一棵带权12 t的最优二叉树T,使在T中,一定能使带权1,2 的顶点为兄弟,且它们的层数相同,均为树高.(p117) 定理1 设T为带权12 t的最优二叉树,若将以带权1,2 的树叶为儿子的分枝点改为带权为1+2 的树叶,得到一棵新树T,则T也是最优二叉树. 例1 求带权为1,3,5,7,8,11,13的最优二叉树. (p118),定义2 有一个序列的集合, 如果在该集合中, 任何序列都不是另一个序列的前缀,则称该集合为前缀码. 例如：001是001011的前缀，不是010011的前

19、缀。00,10,011,111,0100,0101和000,001,01,10,11是前缀码。 由一棵二叉树产生前缀码的方法:将该棵二叉树的每个分枝点与它左儿子之间的边记为0,和它右儿子之间的边记为1,把从根到每个叶子所经过边的记号序列作为叶子的记号,这些叶子标记的集合就是一个前缀码. (p119例),将任何一棵有序树改写为一棵对应的二叉树的步骤: (1)从根结点开始,保留根结点同其最左边儿子的连线,删去与其它儿子的连线; (2)兄弟间从左至右加线连接; (3)用如下方法选定二叉树的左儿子和右儿子: 直接处于给定结点下面的结点作为左儿子;对于同一水平线上与给定结点右邻的结点作为右儿子,依次类推

20、.（见p120例2）,将一个森林转换为二叉树的步骤: (1)先把森林中每一棵树表示成一棵二叉树; (2)除了第一棵二叉树外,依次将每棵二叉树作为左边二叉树的根的右子树,直到所有的二叉树都连成一棵二叉树为止. （见p120例3）,第六节 二叉查找树与决策树,定义1 一棵二叉查找树是一棵二叉树,其数据与结点有关,数据被用以下方式组织起来,对树中的某个结点v而言,其左子树中每个结点的数据都小于v中的数据;其右子树中每个结点的数据都大于v中的数据. 基于递规思想的二叉树形成方法: 从只包含一个顶点(根)的树开始.指定列表中的第一项作为该根的关键字.为添加新的项,首先比较它与已经在树里的顶点的关键字,从根开始,若该项小于所比较顶点的关键字而且该顶点有左儿子,则向左移动,或者该项大于所比较顶点的关键字而且该顶点有右儿子,则向右移动.,当该项小于所比较顶点的关键字且该顶点没有左儿子时,就插入以该项作为关键字的一个新顶点来作为该顶点的左儿子.同理,当该项大于所比较顶点的关键字而且该顶点没有右儿子时,就插入以该项作为关键字的一个新顶点来作为该顶点的右儿子. 例1.用字母顺序建立下面这些单词的二叉查找树(p122) oenology phrenology o