单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,网,络,优,化,第,3,章 最小树与最小树形图,Network Optimization,1,最小树问题,的例子,例 公路连接问题,某一地区有,n,个主要城市，现准备修建高速公路把这些城市连接起来，,使得从其中任何一个城市都可以经高速公路直接或间接到达另一个城市,.,假定已经知道了任意两个城市,i,和,j,之间修建高速公路的成本（费用）,w,ij,(0),那么应任何决定在哪些城市间修建高速公路，使得总成本最小？,高速公路网正好构成这个完全图,G,的一个连通的支撑子图,T,.,为了使得总建设成本最小,该子图必须是无圈的,无圈连通图称为树，上面这样一类问题称为最小树问题,.,2,3,.1树的基本概念 定义,定义,3,.1 无圈连通图称为树（tree）.无圈图（即若干棵树的并）称为森林或者简称林（forest）.,如果一个图的支撑子图是一棵树，则称这棵树为该图的支撑树或者生成树(spanning tree)，并称支撑树中的弧为树弧（tree arc），而不属于支撑树中的弧为非树弧（nontree arc）.,树是一类既简单而又非常重要的图形，在计算机科学、有机化学、电网络分析、最短连接及渠道设计等领域都有广泛的应用,.,在本节及下一节中，我们假设所讨论的图与网络都是无向的,.,3,3,.1树的基本概念 例,例,3,.1 含6个顶点的树(非同构的)：,共有6种,弧的条数=节点数-1,任何两个顶点之间存在唯一的一条路,4,3,.1树的基本概念-树的等价定义,引理,3,.1,G,=（,N,，,E,）为一个图，|,N|=n,，则下列命题等价：,G,是一棵树；,G,连通，且|,E,|,=n,-1；,G,无圈，且,|E|=n,-1；,G,的任何两个顶点之间存在,唯一,的一条路；,G,连通，且将,G,的任何一条弧删去之后，该图成为非连通；,6)G,无圈，且在,G,的任何两个不相邻顶点之间加入一条弧之后，该图正好含有一个圈.,5,3,.1树的基本概念-,最小树的定义,定义,3,.2,G,=（,N,，,E,，,W,）为一个无向网络，,W,为权函数,即,W,:,E,R,（这里,R,表示实数集合）,.,G,中权最小（大）的弧称为最小（大）弧.,如果,H,=（,N,1,，,E,1,）为,G,的一个子图，子图,H,的权定义为,H,所包含的所有弧的权之和，记为,W,(,H,)，即,W,（,H,）=.,弧,e,=(,i,，,j,)上的权常记为,W,(,e,),W,e,或,w,(,e,)，,w,ij,等,如果,T*,是,G,的一棵生成树，且对,G,的任何一棵生成树,T,都有,W,（,T*,）,W,（,T,），则,T*,称为网络,G,的最小支撑树或者最小生成树（MST：minimum spanning tree），或者简称最小树.,图的最小树一般不唯一,6,3,.1树的基本概念-,最小树的应用一例,例,3,.2,二维矩阵,数据存贮问题,某些蛋白质的氨基酸序列差异不多，如果用二维矩阵的每一行记录一种蛋白质氨基酸序列，行与行之间的差异很小,.,其中一种方法是只存贮其中一行作为参照行，再存贮行与行之间的一部分差异信息，使得我们可以在需要时根据参照行生成所有其它行的元素,.,R1,R3,R2,R4,C,13,C,12,C,24,一般地，给定差异信息,c,ij,，如何确定存贮哪些行之间的差异元素,使得存贮空间尽可能少呢？这一问题可以用最小树问题来描述,:,我们把矩阵每行作为一个节点构成一个完全图,第,i,个节点对应于矩阵第,i,行，并令弧,(,i,j,),上的权为,c,ij,.,对于存贮问题,实际上只需要存贮一行的元素,以及由该完全图的一棵支撑树所对应的差异元素,.,最小树就对应于最优的存贮方案,.,7,3,.1树的基本概念-,定理,3,.1,生成树,T*,是最小树的充要条件是：对,T*,中的任何一条弧，将该弧从,T*,中删除后形成的割中，该弧为最小弧,.,最小树的“割最优条件”,T*,必要性：很容易用反证法证明。,e,e,设,w,(,e,),w,(,e,),令,T,=,T*-,e,+,e,，则,w,(,T*,),w,(,T,),8,T*,e,3,.1树的基本概念-,充分性,.,设,T*,是生成树并满足定理中的条件,但不是最小树，设最小树为,T,0,.,记,e,T*,T,0,将,e,从,T*,中删除后产生一个割.,将,e,加入,T,0,后必然产生一个圈，该圈必然包括割中一条与,e,不同的弧,e,，,由假设，,w,(,e,),w,(,e,).,最小树的“割最优条件”,重复这一过程，最后可以得到,T*,也是最小树,e,由,T,0,为最小树,，,w,(,e,),w,(,e,),则,w,(,e,),=,w,(,e,)，,因此，,T,1,=,T,0,-,e,+,e,也是最小树，与,T*,有更多的公共弧,9,3,.1树的基本概念-,T*,定理,3,.1,生成树,T*,是最小树的充要条件是：对属于,G,但不属于,T*,的任何一条弧，将该弧加入,T*,后形成的圈中，该弧为最大弧,.,必要性：很容易用反证法证明。,e,e,若,w,(,e,),w,(,T,)，矛盾。,最小树的“圈最优条件”,10,3,.1树的基本概念-,T*,充分性,.,设,T*,是生成树并满足定理,3,.2,中的条件，我们来证明它也满足定理,3,.1,中的条件。,最小树的“圈最优条件”,对,T*,中的任何一条弧,e,，将该弧从,T*,中删除后形成的割中，考虑任何一条与,e,不同的弧,e,.由定理,3,.2,中的条件假设,w,(,e,),w,(,e,)，,即弧,e,为最小弧,.,e,e,所以，满足定理,3,.1,中的条,件，所以T,*,是最小树,。,11,3,.2 最小树算法-,可以计算最小树,自然也可以计算连通图的生成树.,算法开始时假设某支撑子图,T,的弧集合为空集,;,算法运行过程中不断将一些弧加入到子图中,并且每次加入,T,中的弧就会成为最后找到的最小树的一员，而不会再从,T,中退出,.,贪婪算法的共性,理论基础-“割最优条件”和“圈最优条件”.,如果算法结束时无法得到支撑树,则说明图不连通,因为连通图一定有支撑树.,可以计算最小树,变形后可以计算最大树。,贪婪算法(Greedy Algorithm):,12,3,.2 最小树算法,基本思想：每次将一条权最小的弧加入子图,T,中，并保证不形成圈.（避圈法）,如果当前弧加入后不形成圈,则加入这条弧,如果当前弧加入后会形成圈,则不加入这条弧,并考虑下一条弧,.,STEP0.,令,i,=1,j,=0,T,=,.,把,G,的边按照权由小到大排列，即,;,3,.2.1 Kruskal,算法（1956）,STEP1.,判断,T,e,i,是否含圈,.,若含圈,转,STEP2,否则转,STEP3.,STEP2.,令,i,=,i,+1,.,若,i,m,转,STEP1;,否则结束,此时,G,不连通,所以没有最小树,.,STEP3.,令,T=T,e,i,j,=,j,+1.,若,j,=,n,-1,结束，,T,是最小树,;,否则转,STEP1.,正确性,：,圈最优条件,13,3,.2 最小树算法,例,3,.3 用Kruskal算法计算最小树：,3,.2.1 Kruskal,算法（1956）,1,1,3,2,5,4,6,3,8,5,2,4,7,1,1,3,2,5,4,3,5,2,14,Kruskal,算法的,计算复杂性,对,m,条弧进行排序,其复杂度为,判断加入一条弧到,T,中时是否形成圈,其复杂度依赖于算法的具体实现方法.,在算法的计算过程中,T,是一个森林,.,如果该森林的每一棵子树中的节点用一个单向链表表示，则可以方便地判断圈,.,当考虑弧(i,j)时，如果其端点属于同一单向链表，则加入,T,后会形成圈；如果其端点分属于两个不同的单向链表，则加入,T,后不会形成圈，因此将这两个链表合并成一个链表.,由于处理每一条弧所需要的时间为,O,（,n,），因此这种实现方法的复杂度为,O,（,nm,）,.,15,Kruskal,算法的,计算复杂性,改进,算法实现,改进：利用三个数组,size,-用来记录每个链表中所含节点的个数,(,链表规模,),；,last,-用来记录每个链表中最后的节点编号,first,-用来记录每个节点所在链表的第一个节点,.,如果链表,L,=1，2，4，5,，则,size,(,L,),=,|,L,|,=,4,last,(,L,)=5,first,(1),=first,(2),=first,(4)=,first,(5),=,1,.,考虑弧（i，j）时，只需判断,first,(,i,),与,first,(,j,),是否相等,相等则端点属于同一单向链表；否则合并链表,.,因此所有这些判断所需要的计算时间为,O,(,m,).,合并时,我们总是把节点数较多的链表,L,放在前面,而把节点数较少的链表,L,追加在后面,.,16,Kruskal,算法的,计算复杂性,合并后,对于,size,和,last,的修改非常容易,可以在常数时间内完成,;,但对,first,的修改必须对链表,L,中的每个元素,(,节点,),进行,复杂度为,O(h)，h=size(L),.,只需要证明获得一个规模为,n,的链表的计算时间（操作次数）不超过,p,2,n,log,n(,这里,p,2,p,1,为常数）.,这种合并最多进行(,n-,1)次,对,first,进行修改的总的复杂度为,记链表,L,追加在链表,L,（,),后面而合并成一个链表时的计算时间（操作次数）不超过,p,1,h,（这里,p,1,为常数）,数学归纳法:当,n,=1时不需要进行任何合并操作,因此结论成立.,当,n,1时,我们假设结论对规模小于,n,的链表均成立.,设规模为,n,的链表由,L,追加在,L,后面合并而成,则,h,n,/2,h=n-h,.,p,2,h,log,h,+,p,2,(,n-h,)log(,n,-,h,)+,p,1,h,p,2,h,log(,n/2,)+,p,2,(,n-h,)log,n,+,p,2,h,=p,2,n,log,n,.,排序,O（m,log,n）,；,这一实现方法的复杂度为,O,（,m,+,n,log,n,）,.,17,Kruskal,算法(改进的实现）-例,首先考虑弧（,1,，,2,），将,L,1,，,L,2,合并成一个链表（如,L,1,）：,L,1,=1，2，,size,（,L,1,）=2，,last,（,L,1,）=2，,first,（1）=,first,（2）=1.,1,1,3,2,5,4,6,3,8,5,2,4,7,L,1,=1,，,size,（,L,1,）,=1,，,last,（,L,1,）,=1,，,first,（,1,）,=1,；,L,2,=2,，,size,（,L,2,）,=1,，,last,（,L,2,）,=2,，,first,（,2,）,=2,；,L,3,=3,，,size,（,L,3,）,=1,，,last,（,L,3,）,=3,，,first,（,3,）,=3,；,L,4,=4,，,size,（,L,4,）,=1,，,last,（,L,4,）,=4,，,first,（,4,）,=4,；,L,5,=5，,size,（,L,5,）=1，,last,（,L,5,）=5，,first,（5）=5.,18,Kruskal,算法(改进的实现）-例,下一步考虑弧（,1,，,4,），将,L,1,，,L,4,合并成一个链表（如,L,1,）：,L,1,=1，2，4，5，,size,（,L,1,）=4，,last,（,L,1,）=5，,first,（1）=,first,（2）=,first,（4）=,first,（5）=1.,下一步考虑弧（,4,，,5,），将,L,4,，,L,5,合并成一个链表（如,L,4,）：,L,4,=4，5，,size,（,L,4,）=2，,last,（,L,4,）=5，,first,（4