第三章 树及其应用(新)

第三章树及其应用第一节树的基本概念定义1树是无圈连通无向图.树中度数为1的结点称为树的叶.树中度数大于1的结点称为树的分枝点或内点.不相交的若干树称为森林,即森林的每个连通分枝是树.定理1T是树T中无环,且任何两结点间有且仅有一条路.证:1.(→)必要性:因为T是树,故对T中任意不同的两个结点x,y之间至少存在一条路.若x,y之间存在T中两条不同的路P1和P2,则P1和P2中至少有一边不同,不妨设eP1,但eP2.设e={u,v},显然在P1和P2的并中删去e后的图仍然连通,故在P1P2-e中存在uv路P,所以P+e是圈,矛盾.2.充分性:只需证明T中无圈即可.若T中有圈C,当C只有一个结点时,则T中有环;若C中有两个结点,则T中有平行边;若V(C)3,则对C中的任意两个结点,均有两条不同的路,矛盾,因此,T是无圈连通图,即T是树.定理2T是树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)=22.充分性:只需证明T中无圈即可.若T中有圈C,且e={x,y}E(C),又W(T-e)=2,所以1=W(C-e)W(T-e)=2,矛盾.所以T连通无圈,从而T是树.),(TEe定理3T是树T连通且=|E|=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为树.)1(2)deg()(nxTVx推论T是森林=n-w,其中为T的边数,n为T的顶点数,w为T的连通分枝数.定理4设T是n阶非平凡树(平凡图称为平凡树),则T中至少有2片树叶.证明:设T是n阶非平凡树,则(T)1,并设T有条边,k片树叶,则又=n-1,故k2.,2)(2)deg(21knknkvnii定义2设T是有向图,若T的基础图是树,称T是有向树.定义3仅一个结点的入度为0,其余所有结点的入度都为1的有向树称为根树.入度为0的结点称为根.出度为0的结点(度数为1的结点)仍称为叶;出度不为0的结点称为分枝点或内点.由根到某一顶点v的有向路的长度,称为v的层数.根树的高度就是顶点层数的最大值.例1用根树可以表示家庭之间的关系.（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的一个顶点v的离径R(v)定义为:图G的半径R(G)定义所有满足R(v)=R(G)的顶点v都称为G的中心.显然一个图的直径为:.例2.求下图G的每个结点的离径及图G的直径,半径和中心.)},({max)()(uvdvRGVu()()min{()}vVGRGRv()max{()}vVGRvu1u3u6u2u5u4定理6设P=u1u2…ulul+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=u1u2…ulul+1是T中的一条最长路,故d(u1,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,ui)+d(ui,uk)i-1+k-ik若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)-{uj})V(P)=.不妨设ij.因为T是树,故P’=Q1P(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条线段中的任意三条线段有一个公共端点,则这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的弦.定理1图G有生成树G为连通图.定义2设D是无环有向图,且D有n个结点条边.在D的关联矩阵Mn中划去任意结点x所对应的行,得到一个(n-1)阶矩阵Mx,称Mx为D的一个基本关联矩阵.定理2已知两个矩阵A=(aij)mn,B=(bij)nm.若mn,则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的不同生成树的数目;(2)求D的不含边e4的不同生成树的数目;(3)求D的必包含边e3的不同生成树的数目;v1e1v2e2e3e4v4e5v3说明:(1)记C=BkBkT=(Cij),ik,jk,则(2)对于连通无向图G的支撑树计数,只需考虑G的定向图.（p102例）定理4有向弱连通图D中以vk为根的不同支撑树数目为表示D的vk的基本关联矩阵Bk中将全部1元素改为0元素之后的矩阵.(),,ijDiijijdvijCvv关联与的边数kTkkBBB),det(第三节求连通简单图的生成树深度优先搜索和广度优先搜索深度优先搜索:任意选择图G的一个顶点为根,通过不断地增加边来形成以顶点v0为起点的路,直到这条路经过图G的每个顶点,此时得到的这条路就是该图的生成树.其中每条新边都与路上的一个顶点以及不在路上的一个顶点关联.如果这条路不经过图G的所有顶点,则返回倒数第二个顶点,继续重复上面过程,直到不能添加更多的边为止.又图G是有有限边数的连通图,故最后总能产生一棵生成树.例1用深度搜索来找出下图G的生成树abcdefghijk广度优先搜索基本思想:从图的顶点中任意地选择一个根,然后添加与该顶点相关联的所有边,在这个阶段添加的新顶点成为生成树里1层上的顶点,任意地排序它们.下一步,按顺序访问1层上的每一个顶点,只要不产生回路,就添加与这个顶点相关联的每条边,这样就产生了树里2层上的顶点.遵循这样的原则继续下去,经有限步骤后(因为图中只有有限条边)就产生了生成树.例2.用广度优先搜索找出例1中图G的生成树.P106第四节最小支撑树定义1:连通加权图里权和最小的支撑树称为最小支撑树.最小支撑树的实际应用背景:在某一国家或地区,需建造一铁路网/公路网把一些城市连接起来,需要总长度最短或造价最低.寻找最小支撑树的贪心算法原理:通过添加还没使用过的具有规定性质且权最小的边来进行的,其实质就是在每步上进行最优选择,即“局部最优化”.普林算法算法的基本思想:首先选择带最小权的边,把它放进支撑树里.相继向树里添加带最小权的边,这些边与已在树里的顶点相关联,并且不与已在树里的边形成圈,直到添加了n-1条边止.算法描述如下:算法1普林算法Procedureprim(G:带n个顶点的连通无向图)T:=权最小的边Fori:=1ton-2begine:=与T里顶点相关联的权最小的边,并且若添加到T里则不形成圈.T:=添加e之后的Tend{T是G的最小支撑树}例1用普林算法求下图所示的最小支撑树定理1普林算法是正确的,即在算法结束时,得到一棵最小支撑树.(证略)1745102616158abcgfde39克鲁斯卡尔(Kruskal)算法算法的基本思想:选择图中最小的一条边,相继添加不与已经选择的边形成圈的权最小的边,直到挑选n-1(n为结点的个数)条边为止.该算法的伪代码如下:ProcedureKruskal(G:n个顶点的连通加权无向图)T:=空图.Fori:=1ton-1beginE:=当添加到T里时不形成圈的G里权最小的边T:=添加e之后的TEnd{T是G的最小支撑树}定理2由Kruskal算法构作的任何生成树T=G[e1,e2,…,en-1]都是G的最小生成树,n为G的结点数.基于破圈法的最小生成树的生成方法该方法是由管梅谷教授给出的,其基本思想为:设G是连通加权简单图,若G不是树,则G中必含有回路,删去G中含于某回路内权最大的一条边,所得的图记为G1,G1是G的连通生成子图.下一步,若G1不是树,又从G1某个回路内删去权最大的一条边,如此下去,最后不能按上述方式删边时,得到的图T便是G的一棵生成树.定理3由破圈法最后得到的图T为G的一棵最小生成树.（证略）第五节前缀码定义1设T是有t片叶子的二叉树,其中t片叶子分别带有权1,2,…,t,称T为加权二叉树,称为二叉树T的权,其中li为带权i的树叶vi