文档详情

《离散数学》课件:4-2-树

pu****.1
实名认证
店铺
PPT
203.50KB
约30页
文档ID:569593554
《离散数学》课件:4-2-树_第1页
1/30

§§4.2 树树(Trees) 1847年德国物理学家柯希霍夫(kirchhof)提出了树的概念.即所谓无圈连通图,他时在研究电路网络时考虑电路网的所谓”生成树”,即一个含有电路图上所有节点的树形子图.1857年英国数学家凯莱(caylay Arthur)研究碳氢化合物时,提出了树的概念与记数的理论.1889年凯莱给出了完全图Kn的概念.例如10个顶点的完全图竟有一亿棵生成树.1956年Kruskal设计了求最优树的有效算法. §4.2.1 树及其等价命题树及其等价命题 Ø定义定义4.2.1 设设G=( (P,,L)是图如果是图如果G是连通的,是连通的,并且无回路,则称并且无回路,则称G为树无回路的图为树无回路的图( (可能不可能不连通连通) )也称为森林也称为森林 Ø例:例: 引理引理1 1 Ø设设G是至少有一条边的有限图,且无回路,则是至少有一条边的有限图,且无回路,则G至少至少有一个点只相邻于另一个点,即有一个点只相邻于另一个点,即G至少有一个点度数为至少有一个点度数为1 Ø证证明明::因因为为G至至少少有有一一条条边边,,所所以以,,G有有一一点点v1,,且且v1有相邻点有相邻点v2。

若若v2即为所求,则引理得证即为所求,则引理得证否则,令否则,令v3为为v2的不同于的不同于v1相邻点,以此类推,即,对相邻点,以此类推,即,对k 2,,或者或者vk只与只与vk-1相邻,从而相邻,从而vk即为所求;或者即为所求;或者vk又又相邻于相邻于vk+1 vk-1于是得于是得v1,,v2,,……,,vk-1,,vk,,vk+1,,……,,因为因为G无回路,故这一串点不能有重复又因为无回路,故这一串点不能有重复又因为G有有限,故上述过程必在有限步内停止从而引理得证限,故上述过程必在有限步内停止从而引理得证 定理定理4.2.1 如果如果G是图,则下列诸命题等价:是图,则下列诸命题等价:1)G是树2)G连连通通并并且且删删去去G的的任任意意一一边边,,所所得得之之图图都都不连通3)对对G中中任任意意两两点点v,,v’(v v’),,恰恰有有一一条条从从v到到v’的简单路的简单路如如果果G还还是是有有限限图图,,设设P(G)元元数数为为n,,则则下下列列命命题也与上面命题等价:题也与上面命题等价:4)G不含回路,并且不含回路,并且G有有(n-1)条边5)G连通,并且连通,并且G有有(n-1)条边。

条边 证明:证明:Ø1) )2) );;若若G删去边删去边vv’后是连通的,则有后是连通的,则有从从v到到v’的路的路( (v, ,v1,…,,…,v’) ),,不妨设这是不妨设这是从从v到到v’的所有路中最短者,于是,这是的所有路中最短者,于是,这是一条简单路显然,此路长度不小于一条简单路显然,此路长度不小于2,,于是这条路再加上边于是这条路再加上边vv’就是就是G中一条回中一条回路,矛盾路,矛盾 证明:证明:Ø2) )3) );;因为因为G连通,所以对于连通,所以对于v, ,v’, ,有从有从v到到v’的路,取其最短者,得从的路,取其最短者,得从v到到v’的简的简单路若有两条这样的路,设为单路若有两条这样的路,设为 (v, ,v1,…,,…,vn, ,vn+1) ,,(v, ,v1’,…,,…,vm’, ,vm+1’),,其中其中vn+1=vm+1’=v’从左向右看可找到最从左向右看可找到最小的小的k,,使得使得vk vk’于是,从于是,从G删去边删去边vk-1vk,,从从vk-1到到vk还有路还有路 (vk-1, ,vk’,…,,…,vm+1’, ,vn, ,vn-1,…,,…,vk)。

故故G删去边删去边vk-1vk后,所得之图仍连通,矛盾后,所得之图仍连通,矛盾 证明:证明:Ø3) )1) );;由已知条件知,由已知条件知,G是连通的若是连通的若G有回路有回路( (v,v1,…,,…,vk,…,,…,v) ),,则从则从v到到v1将有两条简单路:将有两条简单路:( (v, v1) )和和( (v,…,,…,vk,…, ,…, v1) ),,矛盾故G中无回路,所以,中无回路,所以,G是树 证明:证明:1) )4) );;因为因为G是树,所以是树,所以G中无回路往证:中无回路往证:G有有(n-1)条边对n用归纳法用归纳法§n=1时,命题显然时,命题显然§假如对于假如对于(n-1),,命题成立命题成立§设设G有有n个点,由引理个点,由引理1知,知,G有点有点vn,,且且vn 恰有恰有一个相邻点一个相邻点vn-1,,删去删去vn和和vnvn-1得一图得一图G’因为因为G无回路,所以无回路,所以G’无回路因为因为G连通,所以连通,所以G中任意两点间有路连接中任意两点间有路连接 证明:证明:因为因为vn恰有一相邻点恰有一相邻点vn-1,,故点故点vn只能出现在只能出现在G中中任意一条路的两端,而不能出现在中间。

所以边任意一条路的两端,而不能出现在中间所以边vnvn-1只能出现在任何一条路的两端,所以删去只能出现在任何一条路的两端,所以删去点点vn和边和边vnvn-1,,剩下的图中任意两点间仍有路,剩下的图中任意两点间仍有路,故故G’连通因此,因此,G’是树由归纳假设,是树由归纳假设,G’有有 (n-1)-1=(n-2)条边故G有有(n-2)+1=(n-1)条边 证明证明4)1)采用归纳法当采用归纳法当G只有一个节点、两个节点时显然只有一个节点、两个节点时显然命题成立假设节点数命题成立假设节点数 k时成立,则节点数为时成立,则节点数为k+1时设时设G1,, G2 ,,…,, Gt是是G的的t个连通分支个连通分支(t 1)若若t>1,,则由则由G1,, G2 ,,…,, Gt是树,知是树,知 L(G) =  L(G1) +  L(G2) +…  L(Gt) =  P(G1) -1+  P(G2) -1+…+  L(Gt) -1=  P(G) -t,,矛盾矛盾 证明:证明:4)5);;已知已知G中无回路,有中无回路,有n个点,个点,(n-1)条边,条边,往证往证G连通。

对连通对n用归纳法用归纳法§n=2,,命题显然命题显然§假设假设n-1时时, 命题成立命题成立§设设G有有n个个点点由由引引理理1知知,,G中中有有点点vn,,vn恰恰有有一一相相邻邻点点vn-1,,删删去去点点vn和和边边vnvn-1 得得图图G’,,显显然然,,G’中中仍仍无无回回路路但但G’有有(n-1)个个点点,,由由归归纳纳假假设设,,G’连连通通因因此此,,将将点点vn和和边边vnvn-1添添入入G’得得G,,G仍连通 证明:证明:5)1);;设设G有有n个点,个点,(n-1)条边,并且连通,条边,并且连通,往证:往证:G是树显然,只需证是树显然,只需证G无回路即可无回路即可Ø若不然,设若不然,设G有一条回路,则删去回路中任一有一条回路,则删去回路中任一条边,所得之图仍连通对条边,所得之图仍连通对G中每一条回路,都中每一条回路,都用此方法删去一边,最后得一个无回路但仍然连用此方法删去一边,最后得一个无回路但仍然连通的图通的图G’所以所以G’是树而G’是由是由G删去删去k(k 0)条边所得,故条边所得,故G’仍有仍有n个点,所以由个点,所以由1) )4) )知,知,G’有有( (n-1) )条边,但是条边,但是G’有有(n-1-k)条条边,而边,而n-1 n-1-k( (因为因为k 0) ),,矛盾。

矛盾定理证毕定理证毕 推论推论1 任意有限连通图必有一支撑子图是树任意有限连通图必有一支撑子图是树今后,此支撑子图称为母图的支撑树今后,此支撑子图称为母图的支撑树推论推论2 若若G’是有限图是有限图G的支撑树,的支撑树,vv’为为G中一边,中一边,且且vv’不在不在G’中,则中,则G’添上边添上边vv’后必有回路后必有回路 §4.2.2 最优树最优树 Kruskal算法算法Ø例:铺设一个连接各个城市的光纤通信网络例:铺设一个连接各个城市的光纤通信网络bacd762fe81443472356321hg §4.2.2 最优树最优树 Kruskal算法算法Ø定义定义4.2.2 设设G是加权连通图,带有最小权是加权连通图,带有最小权(和和)的支撑树称为权图的支撑树称为权图G的最优树的最优树 bacd762fe81443472356321hg Kruskal算法算法设权图设权图G=(P, L)是连通的是连通的1)在在L(G)中中选选一一个个具具有有最最小小权权值值的的边边,,记记为为l1,,令令T={ l1 };;2)从从L(G)-T中取中取li,,使得使得T∪∪{li}不产生回路,并不产生回路,并且且w(li)最小。

如果存在这样的最小如果存在这样的li,,则令则令T= T∪∪ {li},,重复步骤重复步骤2);;3)如果不存在这样的如果不存在这样的li,,则算法停止则算法停止 定理定理4.2.2设设G=(P,,L)是连通权图于是是连通权图于是Kruskal算法得到算法得到的的 T={ l1, l2, …, ln}是是G的最优树的最优树 证明:证明:显然显然T={ l1, l2, …, ln}是是G的子图记的子图记T=(P1, L1)1) 先证明先证明T是支撑子图,即证明是支撑子图,即证明P(T)=P(G)容易看出容易看出P(T) P(G),,只需证只需证P(G) P(T)用反证法,设用反证法,设x P(G),,但但x P(T),,任取任取T中点中点y,,因因G是连通的,所以在是连通的,所以在G中有中有x到到y的路设为的路设为l=(x,v1,…,vr,y),,则则x v1不是不是T中的边,把边中的边,把边x v1加加入入T中不会产生回路,与算法停于中不会产生回路,与算法停于T矛盾故必矛盾故必有有P(G)  P1(T) ,所以,,所以,P(G)=P(T) 定理定理4.2.22))证明证明T是一个树,只须证明是一个树,只须证明T是连通的是连通的(无回无回路由算法保证路由算法保证)。

若若T不连通,不妨假设不连通,不妨假设T1和和T2 是是T的其中两个分的其中两个分支支 ,,令令x T1,,y T2,,因因G是连通的,所以有是连通的,所以有G中的路中的路 (x, v1, …, vr, vr+1),,其中其中x= v1,,y= vr+1,,因此,必有边因此,必有边 vi vi+1,,使使 vi   T1,,vi+1  T1,,那么,那么,把把 vivi+1加到加到T中,不会产生回路,与算法停于中,不会产生回路,与算法停于T矛盾,所以矛盾,所以T是连通的是连通的 定理定理4.2.23))由算法及由算法及1)、)、2)知,)知,T是是G的支撑树设的支撑树设G有有r个点,于是个点,于是T也有也有r个点由定理个点由定理4.2.1知,知,T有(有(r-1))条边故n=r-1 4))证明证明T是最优支撑树,我们证明是最优支撑树,我们证明,可以通过以可以通过以下不断交换边的办法,使下不断交换边的办法,使T的所有边全在某一最的所有边全在某一最优支撑树优支撑树T’中,则中,则T=T’(均有均有r-1条边条边)设设T*是一棵最优支撑树,是一棵最优支撑树,T*={l1’,,……,,lr-1’},,T={ l1,,……,,lr-1},, 定理定理4.2.2若若l1 T*,,在在T*中加入中加入l1,,则形成一含有则形成一含有l1的回路,的回路,在此回路中删去一条非在此回路中删去一条非l1的边,不妨设为的边,不妨设为l1’,,得得一图一图T’,,令令T’={ l1,,l2’,,…,,lr-1’},,则则T’是支撑是支撑树。

树对任意对任意l L(G),,因为因为w(l1) w(l) ,,所以所以w(l1) w(l1’)而而w(T’)=W(T*)-w(l1’)+w(l1),,所以所以w(T’) W(T*),,即即T’也是最优树也是最优树 定理定理4.2.2一般地,设一般地,设l1, …, lk T*,,lk+1 T*,,T={ l1, …,lk,,lk+1, …, lr-1},,T*={ l1, …, lk, lk+1’, …, lr-1’}因为因为T*是支撑树,是支撑树,T* {lk+1}必然有回路必然有回路C,,不不妨设妨设lk+1’是回路中一条边,是回路中一条边,lk+1’ T,,令令T’={ l1,…,lk,lk+1,lk+2’,…,lr-1’},,则则T’是支撑树,是支撑树,由由Kruskal算法步骤算法步骤2),,在算法实行中选了在算法实行中选了lk+1而而没选没选lk+1’,,说明说明w(lk+1) w (lk+1’) 所以所以w(T’)=w(T*)-w(lk+1’)+w(lk+1),,即即w(T’) w(T*) 定理定理4.2.2因为因为T*是最优树,所以是最优树,所以T’也是最优树,但也是最优树,但T’包包括括l1,,……,,lk+1,,反复执行上述过程,最后可得一反复执行上述过程,最后可得一最优树包括了最优树包括了T的所有边,即的所有边,即T’=T,,所以所以T是最是最优树。

优树 例:例:Ø铺设一个连接各个城市的光纤通信网络铺设一个连接各个城市的光纤通信网络单位:万元)(单位:万元)febacd546036388404820452815383062251210hg §4.2.3 求最优树的其它算法求最优树的其它算法 Ø由定理由定理4.2.1、定理、定理4.2.2及其证明知道:及其证明知道:1)支撑树加上一条非树中的边后包含一个唯一支撑树加上一条非树中的边后包含一个唯一的回路;的回路;2)支撑树删去一条树中的边后形成两个子树,支撑树删去一条树中的边后形成两个子树,图中两个端点分属于两个子树的边称为割图中两个端点分属于两个子树的边称为割 §4.2.3 求最优树的其它算法求最优树的其它算法 Ø定定理理4.2.3 支支撑撑树树T*是是最最优优树树的的充充要要条条件件是是::对对T*中中的的任任意意一一条条边边,,将将该该边边从从T*中中删删除除后后形形成的割中,该边的权最小成的割中,该边的权最小Ø定定理理4.2.4 支支撑撑树树T*是是最最优优树树的的充充要要条条件件是是::对对属属于于G但但不不属属于于T*的的任任意意一一条条边边,,将将该该边边加加入入到到T*中后形成的回路中,该边的权最大。

中后形成的回路中,该边的权最大Ø通常称定理通常称定理4.2.3为割最优条件,定理为割最优条件,定理4.2.4为圈为圈(回路)最优条件回路)最优条件 定理定理4.2.3和和 4.2.4的证明的证明首首先先证证明明定定理理4.2.3必必要要性性,,假假设设被被删删掉掉的的边边在在形形成成的的割割集集中中权权不不是是最最小小的的,,这这与与求求最最优优树树T*的的Kruskal算算法法矛矛盾,因此假设不成立,该边在形成的割集中权是最小的盾,因此假设不成立,该边在形成的割集中权是最小的充充分分性性,,由由求求T*的的Kruskal算算法法及及定定理理4.2.2的的证证明明过过程程知知T*是最优树是最优树现现在在来来证证明明定定理理4.2.4必必要要性性,,假假设设该该边边的的权权在在此此回回路路中中不不是是最最大大的的,,边边l的的权权最最大大,,那那么么在在求求T*的的Kruskal算算法法进进行行过过程程应应该该选选择择该该边边加加入入集集合合{l1, l2, …,li}中中,,而而不不是是l,,这这与与l是是T*中中的的边边矛矛盾盾,,即即假假设设不不成成立立,,该该边边的的权权在在此此回路中权最大。

回路中权最大充分性,由求充分性,由求T*的的Kruskal算法及定理算法及定理4.2.2的证明过程知的证明过程知T*是最优树是最优树 Prim算法算法 1)任取任取v0  P(G),,取取l1 L(G),,满足满足l1以以v0为端为端点,且点,且w(l1)最小记l1的另一个端点为的另一个端点为v1,,令令T={ l1},,S={v0, v1}2)如果如果T={ l1,l2,…,li}已经取到,已经取到,S={ v0, v1 ,…, vi},,设设w(li+1)= {w(l)},,其中其中S’=P-S,,l i+1=(vj, vi+1),,0 j   i,,vi+1 S’,,即即li+1为为S与与S’的割边中带的割边中带有最小权者则令有最小权者则令T={ l1,,l2,,…,,li,,li+1},,S={ v0, v1 ,…, vi,,vi+1}如果不存在这样的如果不存在这样的li+1,,则算则算法停止 Sollin算法算法Ø将将Kruskal算法与算法与Prim算法综合起来,就得到算法综合起来,就得到了了1961年年Sollin提出的算法该算法在迭代过程提出的算法。

该算法在迭代过程中与中与Kruskal算法一样维持多个不相交的子树,算法一样维持多个不相交的子树,并与并与Prim算法类似地在每次迭代中尝试向每个算法类似地在每次迭代中尝试向每个子树增加一条边子树增加一条边 破圈法破圈法Ø上述各算法都是贪婪地增加不构成回路的边,上述各算法都是贪婪地增加不构成回路的边,以求得最优树,所以通常称为以求得最优树,所以通常称为““避圈法避圈法””;;Ø我们还可以从另一个角度来考虑最优树问题,我们还可以从另一个角度来考虑最优树问题,由定理由定理4.2.4的圈(回路)最优条件,我们也可以的圈(回路)最优条件,我们也可以在原连通权图在原连通权图G中逐步删除构成回路中权最大的中逐步删除构成回路中权最大的边,最后剩下的无回路的支撑子图为最优树我边,最后剩下的无回路的支撑子图为最优树我们把这种方法称为们把这种方法称为““破圈法破圈法”” 例例 ““破圈法破圈法””求其最优树的过程求其最优树的过程 214356787864 。

下载提示
相似文档
正为您匹配相似的精品文档
相关文档