网络优化-第2章-最小树与最小树形图

2最小树问题的例子例公路连接问题某一地区有n个主要城市，现准备修建高速公路把这些城市连接起来，使得从其中任何一个城市都可以经高速公路直接或间接到达另一个城市.假定已经知道了任意两个城市i和j之间修建高速公路的成本（费用）wij(0),那么应任何决定在哪些城市间修建高速公路，使得总成本最小？高速公路网正好构成这个完全图G的一个连通的支撑子图T.为了使得总建设成本最小,该子图必须是无圈的无圈连通图称为树，上面这样一类问题称为最小树问题.32.1树的基本概念–定义定义2.1无圈连通图称为树（tree）.无圈图（即若干棵树的并）称为森林或者简称林（forest）.如果一个图的支撑子图是一棵树，则称这棵树为该图的支撑树或者生成树(spanningtree)，并称支撑树中的弧为树弧（treearc），而不属于支撑树中的弧为非树弧（nontreearc）.树是一类既简单而又非常重要的图形，在计算机科学、有机化学、电网络分析、最短连接及渠道设计等领域都有广泛的应用.在本节及下一节中，我们假设所讨论的图与网络都是无向的.42.1树的基本概念–例例2.1含6个顶点的树(非同构的)：共有6种弧的条数=节点数-1任何两个顶点之间存在唯一的一条路52.1树的基本概念-树的等价定义引理2.1G=(N,E)为一个图，|N|=n，则下列命题等价:1)G是一棵树；2)G连通，且|E|=n-1；3)G无圈，且|E|=n-1；4)G的任何两个顶点之间存在唯一的一条路；5)G连通，且将G的任何一条弧删去之后，该图成为非连通图；6)G无圈，且在G的任何两个不相邻顶点之间加入一条弧之后，该图正好含有一个圈.62.1树的基本概念-最小树的定义定义2.2G=（N，E，W）为一个无向网络，W为权函数,即W:E→R（这里R表示实数集合）.G中权最小（大）的弧称为最小（大）弧.如果H=（N1，E1）为G的一个子图，子图H的权定义为H所包含的所有弧的权之和，记为W(H)，即W（H）=.1)(EeeW弧e=(i，j)上的权常记为W(e),We或w(e)，wij等如果T*是G的一棵生成树，且对G的任何一棵生成树T都有W（T*）≤W（T），则T*称为网络G的最小支撑树或者最小生成树（MST：minimumspanningtree），或者简称最小树.图的最小树一般不唯一72.1树的基本概念-最小树的应用一例例2.2二维矩阵数据存贮问题某些蛋白质的氨基酸序列差异不多，如果用二维矩阵的每一行记录一种蛋白质氨基酸序列，行与行之间的差异很小.其中一种方法是只存贮其中一行作为参照行，再存贮行与行之间的一部分差异信息，使得我们可以在需要时根据参照行生成所有其它行的元素.R1R3R2R4C13C12C24一般地，给定差异信息cij，如何确定存贮哪些行之间的差异元素,使得存贮空间尽可能少呢？这一问题可以用最小树问题来描述:我们把矩阵每行作为一个节点构成一个完全图,第i个节点对应于矩阵第i行，并令弧(i,j)上的权为cij.对于存贮问题,实际上只需要存贮一行的元素,以及由该完全图的一棵支撑树所对应的差异元素.最小树就对应于最优的存贮方案.82.1树的基本概念-观察：支撑树删去一条树弧后形成两棵子树，图中两个端点分属于两棵子树的弧形成一个割.定理2.1生成树T*是最小树的充要条件是：对T*中的任何一条弧，将该弧从T*中删除后形成的割中，该弧为最小弧.最小树的“割最优条件”T*必要性：很容易用反证法证明。ee’设w(e)w(e’),令T’=T*-e+e’，则w(T*)w(T’)9T*e2.1树的基本概念-充分性.设T*是生成树并满足定理中的条件但不是最小树，设最小树为T0.记eT*\T0,将e从T*中删除后产生一个割.将e加入T0后必然产生一个圈，该圈必然包括割中一条与e不同的弧e’，由假设，w(e)w(e’).最小树的“割最优条件”重复这一过程，最后可以得到T*也是最小树e’由T0为最小树，w(e)w(e’),则w(e)=w(e’)，因此，T1=T0-e’+e也是最小树，与T*有更多的公共弧102.1树的基本概念-观察：支撑树加上一条非树弧后包含一个唯一的圈T*定理2.1生成树T*是最小树的充要条件是：对属于G但不属于T*的任何一条弧，将该弧加入T*后形成的圈中，该弧为最大弧.必要性：很容易用反证法证明。e’e若w(e)w(e’)，令T’=T*-e’+e,则w(T*)w(T’)，矛盾。最小树的“圈最优条件”112.1树的基本概念-T*充分性.设T*是生成树并满足定理2.2中的条件，我们来证明它也满足定理2.1中的条件。最小树的“圈最优条件”对T*中的任何一条弧e，将该弧从T*中删除后形成的割中，考虑任何一条与e不同的弧e’.由定理2.2中的条件假设w(e’)w(e)，即弧e为最小弧.ee’所以，满足定理2.1中的条件。证毕。122.2最小树算法-可以计算最小树,自然也可以计算连通图的生成树.算法开始时假设某支撑子图T的弧集合为空集;算法运行过程中不断将一些弧加入到子图中,并且每次加入T中的弧就会成为最后找到的最小树的一员，而不会再从T中退出.贪婪算法的共性最直接的算法:“破圈法”–复杂度高，实施不易理论基础-“割最优条件”和“圈最优条件”.如果算法结束时无法得到支撑树,则说明图不连通,因为连通图一定有支撑树.可以计算最小树,变形后可以计算最大树。贪婪算法(GreedyAlgorithm):132.2最小树算法基本思想：每次将一条权最小的弧加入子图T中，并保证不形成圈.（避圈法）如果当前弧加入后不形成圈,则加入这条弧,如果当前弧加入后会形成圈,则不加入这条弧,并考虑下一条弧.STEP0.令i=1,j=0,T=.把G的边按照权由小到大排列，即;2.2.1Kruskal算法(1956))()()(21mewewewSTEP1.判断T{ei}是否含圈.若含圈,转STEP2,否则转STEP3.STEP2.令i=i+1.若im,转STEP1;否则结束,此时G不连通,所以没有最小树.STEP3.令T=T{ei},j=j+1.若j=n-1,结束，T是最小树;否则转STEP1.正确性：圈最优条件142.2最小树算法例2.3用Kruskal算法计算最小树：2.2.1Kruskal算法(1956)113254638524711325435215Kruskal算法的计算复杂性对m条弧进行排序,其复杂度为判断加入一条弧到T中时是否形成圈,其复杂度依赖于算法的具体实现方法.在算法的计算过程中,T是一个森林.如果该森林的每一棵子树中的节点用一个单向链表表示，则可以方便地判断圈.当考虑弧(i,j)时，如果其端点属于同一单向链表，则加入T后会形成圈；如果其端点分属于两个不同的单向链表，则加入T后不会形成圈，因此将这两个链表合并成一个链表.)log()log(nmOmmO由于处理每一条弧所需要的时间为O（n），因此这种实现方法的复杂度为O（nm）.)()log(mnOmnnmO)(3nO16Kruskal算法的计算复杂性改进算法实现改进：利用三个数组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追加在后面.17Kruskal算法的计算复杂性合并后,对于size和last的修改非常容易,可以在常数时间内完成;但对first的修改必须对链表L中的每个元素(节点)进行,复杂度为O(h)，h=size(L).只需要证明获得一个规模为n的链表的计算时间（操作次数）不超过p2nlogn(这里p2p1为常数）.这种合并最多进行(n-1)次,对first进行修改的总的复杂度为记链表L追加在链表L’（,)后面而合并成一个链表时的计算时间（操作次数）不超过p1h（这里p1为常数）数学归纳法:当n=1时不需要进行任何合并操作,因此结论成立.当n1时,我们假设结论对规模小于n的链表均成立.)log(nnO'')(,)(hLsizehLsize'hh设规模为n的链表由L追加在L’后面合并而成,则hn/2,h'=n-h.p2hlogh+p2(n-h)log(n-h)+p1hp2hlog(n/2)+p2(n-h)logn+p2h=p2nlogn.算法最后复杂度：O(mlogn)排序O（mlogn）；其他O（m+nlogn）.18Kruskal算法(改进的实现）-例首先考虑弧（1，2），将L1，L2合并成一个链表（如L1）：L1={1，2}，size（L1）=2，last（L1）=2，first（1）=first（2）=1.1132546385247L1={1}，size（L1）=1，last（L1）=1，first（1）=1；L2={2}，size（L2）=1，last（L2）=2，first（2）=2；L3={3}，size（L3）=1，last（L3）=3，first（3）=3；L4={4}，size（L4）=1，last（L4）=4，first（4）=4；L5={5}，size（L5）=1，last（L5）=5，first（5）=5.19Kruskal算法(改进的实现）-例下一步考虑弧（1，4），将L1，L4合并成一个链表（如L1）：L1={1，2，4，5}，size（L1）=4，last（L1）=5，first（1）=first（2）=first（4）=first（5）=1.下一步考虑弧（4，5），将L4，L5合并成一个链表（如L4）：L4={4，5}，size（L4）=2，last（L4）=5，first（4）=first（5）=4.1132546385247下一步考虑弧（2，5），由于first(2)=first(5)，因此继续考虑下一条弧（3，5），将L1，L3合并成一个链表L1：L1={1，2，4，5，3}，size（L1）=5，last（L1）=3，first（1）=first（2）=first（4）=first（5）=first（3）=1.11325435220Kruskal算法的计算复杂性Kruskal算法目前有更有效的实现方法，除了对m条弧进行排序所需的时间外,其计算复杂性为O(m(n，m))，其中（n，m）是用Ackerman函数（一种随m，n快速增长的函数）定义的某种“反函数”，它随m，n的增长非常非常缓慢，实用中通常可以认为它小于6（如当n=65536时，(n,m)不超过3）.212.2.2Prim算法（1957）基本思想：不断扩展一棵子树T=（S，E0），直到S包括原网络的全部顶点，得到最小树T.（边割法）每次增加一条弧，使得这条弧是由当前子树节点集S及其补集所形成的边割的最小弧.STEP0.设v为N的任意一个顶点，令S={v}，E0=。STEP1.若S=N，结束，T=（S，E0）为最小树；否则转STEP2.STEP2.若=，则G不连通，结束；否则，设其中令转STEP1.正确性：割最优条件],[SS),(min)(],[*ewewSSeSvSvvve2,1),2,1(*},{00},2{*eEEvSS222.2最小树算法例2.4用Prim算法计算最小树：2.2.2Prim算法（1957）113254638524711325435223距离标号d（v），记录的是顶点v到集合S的“距离”(边割中以v为端点的最小弧的费用）;前趋标号p（v），记录的是边割中该最小弧的另一个端点.Prim算法的计算复杂性该算法的主要计算量在于STEP2（寻找边割中的最小弧）