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

1、1网网 络络 优优 化化 第第2 2章章 最小树与最小树形图最小树与最小树形图 （第（第1 1讲）讲）Network Optimization清华大学数学科学系 谢金星办公室：理科楼2206# （电话Email: http:/ 公路连接问题公路连接问题某一地区有某一地区有n个主要城市，现准备修建高速公路把这些城市个主要城市，现准备修建高速公路把这些城市连接起来，连接起来， 使得从其中任何一个城市都可以经高速公路直接使得从其中任何一个城市都可以经高速公路直接或间接到达另一个城市或间接到达另一个城市. 假定已经知道了任意两个城市假定已经知道了任意两个城市i和和j之之间修

2、建高速公路的成本（费用）间修建高速公路的成本（费用）wij (0), 那么应任何决定在那么应任何决定在哪些城市间修建高速公路，使得总成本最小？哪些城市间修建高速公路，使得总成本最小？ 高速公路网正好构成这个完全图G的一个连通的支撑子图T. 为了使得总建设成本最小, 该子图必须是无圈的 无圈连通图称为树，上面这样一类问题称为最小树问题. 32.12.1树的基本概念树的基本概念 定定义义定义定义2.1 2.1 无圈连通图称为树（无圈连通图称为树（treetree）. . 无圈图（即无圈图（即若干棵树的并）称为森林或者简称林（若干棵树的并）称为森林或者简称林（forestforest）. . 如果一

3、个图的支撑子图是一棵树，则称这棵树为该图如果一个图的支撑子图是一棵树，则称这棵树为该图的支撑树或者生成树的支撑树或者生成树(spanning tree)(spanning tree)，并称支撑树，并称支撑树中的弧为树弧（中的弧为树弧（tree arctree arc），而不属于支撑树中的弧），而不属于支撑树中的弧为非树弧（为非树弧（nontree arcnontree arc）. . 树是一类既简单而又非常重要的图形，在计算机科学、树是一类既简单而又非常重要的图形，在计算机科学、有机化学、电网络分析、最短连接及渠道设计等领域有机化学、电网络分析、最短连接及渠道设计等领域都有广泛的应用都有广泛的

4、应用. . 在本节及下一节中，我们假设所讨论的图与网在本节及下一节中，我们假设所讨论的图与网络都是无向的络都是无向的. . 42.12.1树的基本概念树的基本概念 例例例例2.1 2.1 含含6 6个顶点的树个顶点的树 ( (非同构的非同构的) )：共有共有6 6种种 弧的条数弧的条数 = = 节点数节点数 - 1- 1 任何两个顶点之间存在唯一的一条路任何两个顶点之间存在唯一的一条路52.12.1树的基本概念树的基本概念 - - 树的等价定义树的等价定义引理引理2.1 G=(N, E)为一个图，为一个图，|N|=n，则下列命题等价，则下列命题等价:G是一棵树；是一棵树；G连通，且连通，且|E

5、|=n-1；G无圈，且无圈，且|E|=n-1；G的任何两个顶点之间存在的任何两个顶点之间存在唯一唯一的一条路；的一条路；1) G连通，且将连通，且将G的任何一条弧删去之后，该图成为非连通图；的任何一条弧删去之后，该图成为非连通图； 6) G无圈，且在无圈，且在G的任何两个不相邻顶点之间加入一条弧之后，的任何两个不相邻顶点之间加入一条弧之后，该图正好含有一个圈该图正好含有一个圈. 62.12.1树的基本概念树的基本概念 - - 最小树的定义最小树的定义定义定义2.2 G=（N，E，W）为一个无向网络，）为一个无向网络，W为权函数为权函数, 即即W: ER （这里（这里R表示实数集合）表示实数集合

6、）. 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：mi

7、nimum spanning tree），或者简称最小树），或者简称最小树.图的最小树一般不唯一图的最小树一般不唯一72.12.1树的基本概念树的基本概念 - - 最小树的应用一例最小树的应用一例例例2.2 2.2 二维矩阵二维矩阵数据存贮问题数据存贮问题某些蛋白质的氨基酸序列差异不多，如果用二维矩阵的每一行记录一种蛋白某些蛋白质的氨基酸序列差异不多，如果用二维矩阵的每一行记录一种蛋白质氨基酸序列，行与行之间的差异很小质氨基酸序列，行与行之间的差异很小. . 其中一种方法是只存贮其中一行作其中一种方法是只存贮其中一行作为参照行，再存贮行与行之间的一部分差异信息，使得我们可以在需要时根为参照行，

8、再存贮行与行之间的一部分差异信息，使得我们可以在需要时根据参照行生成所有其它行的元素据参照行生成所有其它行的元素. . R1R3R2R4C13C12C24一般地，给定差异信息一般地，给定差异信息c cijij，如何确定存贮哪些行之间的差异元素，如何确定存贮哪些行之间的差异元素, , 使得存使得存贮空间尽可能少呢？这一问题可以用最小树问题来描述贮空间尽可能少呢？这一问题可以用最小树问题来描述: : 我们把矩阵每行作我们把矩阵每行作为一个节点构成一个完全图为一个节点构成一个完全图, , 第第i i个节点对应于矩阵第个节点对应于矩阵第i i行，并令弧行，并令弧( (i i, ,j j) )上上的权为

9、的权为c cijij. . 对于存贮问题对于存贮问题, , 实际上只需要存贮一行的元素实际上只需要存贮一行的元素, , 以及由该完全以及由该完全图的一棵支撑树所对应的差异元素图的一棵支撑树所对应的差异元素. . 最小树就对应于最优的存贮方案最小树就对应于最优的存贮方案. .82.12.1树的基本概念树的基本概念 - -观察：支撑树删去一条树弧后形成两棵子树，图中两个端点分观察：支撑树删去一条树弧后形成两棵子树，图中两个端点分属于两棵子树的弧形成一个割属于两棵子树的弧形成一个割. . 定理定理2.1 2.1 生成树生成树T*是最小树的充要条件是：对是最小树的充要条件是：对T*中的任何一条中的任何

10、一条弧，将该弧从弧，将该弧从T*中删除后形成的割中，该弧为最小弧中删除后形成的割中，该弧为最小弧. .最小树的最小树的“割最优条件割最优条件”T* 必要性：很容易用反证法证明。必要性：很容易用反证法证明。ee设设w(e) w( (e),令令T = = T* - e + e，则w(T* ) w( (T)9T*e2.12.1树的基本概念树的基本概念 - - 充分性充分性.设设T*是生成树并满足定理中的条件但不是最小树，是生成树并满足定理中的条件但不是最小树，设最小树为设最小树为T0. 记记e T* T0, 将将e从从T*中删除后产生一个割中删除后产生一个割. . 将将e加入加入T0后必然产生一个圈

11、，该圈必然包括割中一条与后必然产生一个圈，该圈必然包括割中一条与e不同不同的弧的弧e，由假设，由假设，w(e) w( (e).最小树的最小树的“割最优条件割最优条件”重复这一过程，最后可以得到T*也是最小树 e由由T0为最小树为最小树，w(e) w( (e), 则w(e) = w( (e) ，因此， T1 = = T0 - e + e也是最小树，与 T*有更多的公共弧 102.12.1树的基本概念树的基本概念 - -观察：支撑树加上一条非树弧后包含一个唯一的圈观察：支撑树加上一条非树弧后包含一个唯一的圈 T*定理定理2.1 2.1 生成树生成树T*是最小树的充要条件是：对属于是最小树的充要条件

12、是：对属于G但不属于但不属于T*的任何一条弧，将该弧加入的任何一条弧，将该弧加入T*后形成的圈中，该弧为最大弧后形成的圈中，该弧为最大弧. . 必要性：很容易用反证法证明。必要性：很容易用反证法证明。ee若若w(e) w( (T)，矛盾。最小树的最小树的“圈最优条件圈最优条件”112.12.1树的基本概念树的基本概念 - -T* 充分性充分性. . 设设T*是生成树并满足定理是生成树并满足定理2.22.2中的条件，我们中的条件，我们来证明它也满足定理来证明它也满足定理2.12.1中的条件。中的条件。最小树的最小树的“圈最优条件圈最优条件” ” 对对T*中的任何一条弧中的任何一条弧e，将该弧从，

13、将该弧从T*中删除后形成的割中，考中删除后形成的割中，考虑任何一条与虑任何一条与e不同的弧不同的弧e. .由定理由定理2.22.2中的条件假设中的条件假设w(e) w( (e)，即弧即弧e为最小弧为最小弧. .ee所以，满足定理所以，满足定理2.12.1中的条件。证毕。中的条件。证毕。122.2 2.2 最小树算法最小树算法 - -可以计算最小树可以计算最小树, , 自然也可以计算连通图的生成树自然也可以计算连通图的生成树. . 算法开始时假设某支撑子图算法开始时假设某支撑子图T T 的弧集合为空集的弧集合为空集; ; 算法运行过程中不断将一些弧加入到子图中算法运行过程中不断将一些弧加入到子图

14、中, , 并并且每次加入且每次加入T T 中的弧就会成为最后找到的最小树的一中的弧就会成为最后找到的最小树的一员，而不会再从员，而不会再从T T 中退出中退出. . 贪婪算法的共性贪婪算法的共性最直接的算法最直接的算法: “: “破圈法破圈法” ” 复杂度高，实施不复杂度高，实施不易易 理论基础理论基础 - “- “割最优条件割最优条件”和和“圈最优条件圈最优条件”. . 如果算法结束时无法得到支撑树如果算法结束时无法得到支撑树, , 则说明图不连通则说明图不连通, , 因为连通图一定有支撑树因为连通图一定有支撑树. . 可以计算最小树可以计算最小树, , 变形后可以计算最大树。变形后可以计算

15、最大树。贪婪算法贪婪算法(Greedy Algorithm): (Greedy Algorithm): 132.2 2.2 最小树算法最小树算法基本思想：每次将一条权最小的弧加入子图基本思想：每次将一条权最小的弧加入子图T T 中，并中，并保证不形成圈保证不形成圈. . （避圈法）（避圈法）如果当前弧加入后不形成圈如果当前弧加入后不形成圈, , 则加入这条弧则加入这条弧, , 如果当如果当前弧加入后会形成圈前弧加入后会形成圈, , 则不加入这条弧则不加入这条弧, , 并考虑下一并考虑下一条弧条弧. . STEP0.STEP0. 令令i=1, j=0, T= =. .把把G的边按照权由小到大排列

16、，即的边按照权由小到大排列，即 ; ;2.2.1 Kruskal 算法(1956) )()()(21mewewewSTEP1.STEP1. 判断判断T T ei 是否含圈是否含圈. . 若含圈若含圈, , 转转STEP2, STEP2, 否则转否则转STEP3. STEP3. STEP2.STEP2. 令令i=i+1. . 若若i m, ,转转STEP1;STEP1;否则结束否则结束, ,此时此时G不连通不连通, ,所以没有最小树所以没有最小树. . STEP3.STEP3. 令令T=T T=T ei , j , j = =j j+1.+1.若若 j=n-1, , 结束，结束，T T是最小树是

17、最小树; ; 否则转否则转STEP1. STEP1. 正确性正确性：圈最优条件圈最优条件142.2 2.2 最小树算法最小树算法例例2.3 2.3 用用KruskalKruskal算法计算最小树：算法计算最小树：2.2.1 Kruskal 算法(1956) 113254638524711325435215Kruskal 算法的算法的计算复杂性计算复杂性对对m条弧进行排序条弧进行排序, , 其复杂度为其复杂度为 判断加入一条弧到判断加入一条弧到T T中时是否形成圈中时是否形成圈, , 其复杂度依赖于算法其复杂度依赖于算法的具体实现方法的具体实现方法. . 在算法的计算过程中, T是一个森林. 如

18、果该森林的每一棵子树中的节点用一个单向链表表示，则可以方便地判断圈. 当考虑弧(i,j)时，如果其端点属于同一单向链表，则加入T后会形成圈；如果其端点分属于两个不同的单向链表，则加入T后不会形成圈，因此将这两个链表合并成一个链表. )log()log(nmOmmO由于处理每一条弧所需要的时间为O（n） ，因此这种实现方法的复杂度为O（nm）. )()log(mnOmnnmO)(3nO16Kruskal 算法的算法的计算复杂性计算复杂性改进改进算法实现算法实现改进：利用三个数组改进：利用三个数组 size - 用来记录每个链表中所含节点的个数(链表规模)；last - 用来记录每个链表中最后的节

19、点编号first - 用来记录每个节点所在链表的第一个节点.如果链表L=1，2，4，5 ，则size(L)=|L|=4, last(L)=5, first(1)= first(2)= first(4) = first(5)=1. 考虑弧（考虑弧（i i，j j）时，只需判断）时，只需判断first(i)与与 first(j)是否相是否相等等,相等则端点属于同一单向链表；否则合并链表相等则端点属于同一单向链表；否则合并链表. 因此所有这些判断所需要的计算时间为因此所有这些判断所需要的计算时间为O(m). 合并时合并时, 我们总是把节点数较多的链表我们总是把节点数较多的链表L 放在前面放在前面,

20、而把节点而把节点数较少的链表数较少的链表L追加在后面追加在后面. 17Kruskal 算法的算法的计算复杂性计算复杂性合并后合并后, 对于对于size和和last的修改非常容易的修改非常容易,可以在常数时间内完成可以在常数时间内完成; 但对但对 first的的修改必须对链表修改必须对链表L中的每个元素中的每个元素(节点节点)进行进行, 复杂度为复杂度为 O(h)，h=size(L) . 只需要证明获得一个规模为n的链表的计算时间（操作次数）不超过 p2nlogn (这里p2p1为常数）. 这种合并最多进行这种合并最多进行( (n-1)1)次次, , 对对 first 进行修改的总的复杂度为进行

21、修改的总的复杂度为 记链表L追加在链表L（ , ) 后面而合并成一个链表时的计算时间（操作次数）不超过 p1h（这里p1为常数） 数学归纳法: 当n=1时不需要进行任何合并操作, 因此结论成立. 当当n n11时时, , 我们假设结论对规模小于我们假设结论对规模小于n n 的链表均成立的链表均成立. . )log(nnO)(,)(hLsizehLsizehh 设规模为设规模为n 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 = p2nl

22、ogn. 算法最后复杂度：算法最后复杂度： O(mlogn) 排序排序 O（mlogn）；其他其他O（m+nlogn）.18Kruskal 算法算法( (改进的实现）改进的实现） - - 例例首先考虑弧（首先考虑弧（1 1，2 2），将），将L L1 1，L L2 2合并成一个链表（如合并成一个链表（如L L1 1）：）：L L1 1=1=1，22，sizesize（L L1 1）=2=2， lastlast（L L1 1）=2=2，firstfirst（1 1）= = firstfirst（2 2）=1. =1. 1132546385247L L1 1=1=1，sizesize（L L1 1

23、）=1=1， lastlast（L L1 1）=1=1，firstfirst（1 1）=1=1；L L2 2=2=2，sizesize（L L2 2）=1=1， lastlast（L L2 2）=2=2，firstfirst（2 2）=2=2；L L3 3=3=3，sizesize（L L3 3）=1=1， lastlast（L L3 3）=3=3，firstfirst（3 3）=3=3；L L4 4=4=4，sizesize（L L4 4）=1=1， lastlast（L L4 4）=4=4，firstfirst（4 4）=4=4；L L5 5=5=5，sizesize（L L5 5）=1=

24、1， lastlast（L L5 5）=5=5，firstfirst（5 5）=5.=5. 19Kruskal 算法算法( (改进的实现）改进的实现） - - 例例下一步考虑弧（下一步考虑弧（1 1，4 4），将），将L L1 1，L L4 4合并成一个链表（如合并成一个链表（如L L1 1）：）：L L1 1=1=1，2 2，4 4，55，sizesize（L L1 1）=4=4， lastlast（L L1 1）=5=5，firstfirst（1 1）= = firstfirst（2 2）= = first first（4 4）= = firstfirst（5 5）=1. =1. 下一步考

25、虑弧（下一步考虑弧（4 4，5 5），将），将L L4 4，L L5 5合并成一个链表（如合并成一个链表（如L L4 4）：）：L L4 4=4=4，55，sizesize（L L4 4）=2=2， lastlast（L L4 4）=5=5，firstfirst（4 4）= = firstfirst（5 5）=4. =4. 1132546385247下一步考虑弧（下一步考虑弧（2 2，5 5），由于），由于firstfirst(2)(2)=first=first(5)(5)，因此继续考虑下一条弧，因此继续考虑下一条弧（3 3，5 5），将），将L L1 1，L L3 3合并成一个链表合并成一个

26、链表L L1 1 ：L L1 1=1=1，2 2，4 4，5 5，33，sizesize（L L1 1）=5=5， lastlast（L L1 1）=3=3，firstfirst（1 1）= = firstfirst（2 2）= = first first（4 4）= = firstfirst（5 5）= = firstfirst（3 3）=1. =1. 11325435220KruskalKruskal算法的计算复杂性算法的计算复杂性Kruskal算法目前有更有效的实现方法，除了对算法目前有更有效的实现方法，除了对m条弧进行排条弧进行排序所需的时间外序所需的时间外, 其计算复杂性为其计算复杂

27、性为 O(m (n，m)，其中其中 （n，m）是用）是用Ackerman函数（一种随函数（一种随m，n快速增长的快速增长的函数）定义的某种函数）定义的某种“反函数反函数”，它随，它随m，n的增长非常非常缓的增长非常非常缓慢，实用中通常可以认为它小于慢，实用中通常可以认为它小于6（如当（如当n=65536时，时， (n, m)不超过不超过3 ）.212.2.2 Prim 2.2.2 Prim 算法（算法（19571957）基本思想：不断扩展一棵子树基本思想：不断扩展一棵子树T=（S，E0），直到），直到S包包括原网络的全部顶点，得到最小树括原网络的全部顶点，得到最小树 T. （边割法）（边割法）

28、每次增加一条弧，使得这条弧是由当前子树节点集每次增加一条弧，使得这条弧是由当前子树节点集S S及及其补集所形成的边割的最小弧其补集所形成的边割的最小弧. . STEP0.STEP0. 设设v为为N的任意一个顶点，令的任意一个顶点，令S=v，E0= 。STEP1.STEP1. 若若S=NS=N，结束，结束，T T= =（S S，E E0 0）为最小树；否则转）为最小树；否则转STEP2. STEP2. STEP2.STEP2. 若若 = = ，则，则G不连通，结束；否则不连通，结束；否则 ，设，设其中其中 令令 转转STEP1.STEP1.正确性正确性：割最优条件割最优条件,SS),(min)(

29、,*ewewSSeSvSvvve2,1),2, 1(*,00,2*eEEvSS222.2 2.2 最小树算法最小树算法例例2.4 2.4 用用PrimPrim算法计算最小树：算法计算最小树：2.2.2 Prim 算法（1957） 113254638524711325435223距离标号距离标号d d（v v），记录的是顶点），记录的是顶点v v到集合到集合S S的的“距离距离”( (边割边割 中以中以v v为端点的最小弧的费用）为端点的最小弧的费用）; ;前趋标号前趋标号p p（v v），记录的是边割中该最小弧的另一个端点），记录的是边割中该最小弧的另一个端点. . Prim算法的算法的计算复

30、杂性计算复杂性该算法的主要计算量在于该算法的主要计算量在于STEP2STEP2（寻找边割中的最小弧）（寻找边割中的最小弧）. . 如果通过对每条弧进行检查寻找边割中的最小弧，则该步的计算复杂度为O（m）. 因为STEP2最多执行n-1步，所以该算法的复杂度为O（mn）. 特殊形式的PRIM算法 - DIJKSTRA算法（1959年） ,SS24利用各种形式的堆（利用各种形式的堆（HeapHeap），可以得到），可以得到PRIMPRIM或或DIJKSTRADIJKSTRA算法更有效的实现方法。复杂度为算法更有效的实现方法。复杂度为 或或DIJKSTRA算法（1959年）STEP0STEP0 设设

31、N N=1=1，2 2，,n,n. . 令令S S=1=1，E E0=0=， dj= =w1j ， pj=1.=1.STEP1选取 若找不到这样的节点使最小值有限，则G不连通，结束；否则令 STEP2 若S=N，结束，T=（S，E0）为最小树；否则令 ，并修改相应的pj ,转STEP1. 复杂度：复杂度：STEP1STEP1： (n-2)+(n-3)+1 = O(n(n-2)+(n-3)+1 = O(n2 2) (STEP2) (STEP2同理）同理） )(2nO)log(),log(nnmOnmO)loglog(CmOSjjdMinj: )(arg*),(00,*jpEEjSSjSjwdMi

32、ndjjjj,*25基本思想：基本思想：前面介绍的两种算法的综合。前面介绍的两种算法的综合。每次迭代同每次迭代同时扩展多棵子树，直到得到最小树时扩展多棵子树，直到得到最小树 T. STEP0.STEP0. 对对N中任意一个顶点中任意一个顶点i，定义，定义Ni=i. 令令T= 。STEP1.STEP1. 如果如果T 中已有中已有n-1条弧，则条弧，则T为为G的最小树；否则，对的最小树；否则，对T 中的所有子树中的所有子树节点集合节点集合Nk，计算边割，计算边割 中的最小弧，即计算中的最小弧，即计算其中其中 . 然后继续然后继续STEP2. STEP2. STEP2STEP2对对T T中的所有子树

33、节点集合中的所有子树节点集合Nk及最小弧及最小弧 ，将该子树与，将该子树与jk所在的子树合并成一棵子树，并将该最小弧纳入所在的子树合并成一棵子树，并将该最小弧纳入T 中中. . 然后转然后转STEP1. STEP1. 正确性正确性：割最优条件割最优条件2.2.3 SOLLIN 算法 （1961）,kkNN),(min)(,*ewewkkNNekkkkkkkkNjNijie,),(*),(*kkkjie 该算法的主要计算量在于以下循环交替迭代：该算法的主要计算量在于以下循环交替迭代：STEP1STEP1（寻找边割中的最小弧）（寻找边割中的最小弧）STEP2STEP2（子树合并）（子树合并）26S

34、OLLIN 算法算法 - - 例例下一步：下一步：合并合并N1， N2，即，即N1 =N2 =1，2； 合并合并N3， N5，即，即N3 =N5 =3，5； 合并合并N4， N5，即，即N3 =N4 =N5 =3，4，5开始时开始时Ni=i. 检查知：对于检查知：对于N1， N2，最小弧都是（，最小弧都是（1，2）；）； 对于对于N3， 最小弧是（最小弧是（3，5）；）； 对于对于N4， N5，最小弧都是（，最小弧都是（4，5）；）；1132546385247检查知：对于检查知：对于N1， N3，最小弧都是（，最小弧都是（1，4）；）；113254352下一步：下一步：合并合并N1， N3，即

35、，即N3 =N4 =N5 =1，2，3，4，5 结束结束27STEP1:STEP1:SollinSollin算法的算法的计算复杂性计算复杂性该算法的主要计算量在于该算法的主要计算量在于STEP1STEP1和和STEP2STEP2的循环交替迭代的循环交替迭代. . 对网络中的每个节点赋予一个标号，使得当且仅当两个节点属于同一棵子树时，它们的标号相同（开始时节点i赋予标号i），此时可以方便地判断两个节点是否属于同一子树. 由于每次循环迭代时，每棵树都会合并成一棵较大的子树，因此每次循环迭代都会使子树的数量至少减少一半. 所以，循环迭代的总次数为O（logn） .每次循环迭代所需要的计算时间： Nk

36、A( (i) )kNiiA| )(| kNimiAk2| )(|28STEP1:STEP1:把每一棵子树中的所有节点存贮为一个双向循环链表，此时从把每一棵子树中的所有节点存贮为一个双向循环链表，此时从该子树的任何一个节点开始，可以方便地访问它的所有节点该子树的任何一个节点开始，可以方便地访问它的所有节点. . 因此，因此，STEP1STEP1最多对每条弧进行两次检查最多对每条弧进行两次检查，复杂度为，复杂度为O（m）. SollinSollin算法的算法的计算复杂性计算复杂性该算法的主要计算量在于该算法的主要计算量在于STEP1STEP1和和STEP2STEP2的循环交替迭代的循环交替迭代.

37、. STEP2:在STEP2中，只需要根据STEP1找到的最小弧进行链表合并，并修改节点的标号，复杂度为O（n）. 所以，算法总的复杂度为O(n+m) logn) = O(m logn ). 29布 置 作 业目的掌握树与最小树的基本概念掌握最小树的几种常用算法及其复杂性分析方法内容网络优化网络优化第第77-78页页 6; 7; 10; 11改错：改错： 5、“最小树最小树”指指“包含指定弧的权最小的支撑包含指定弧的权最小的支撑树树”30网网 络络 优优 化化 Network Optimization清华大学数学科学系 谢金星办公室：理科楼2206# （电话Emai

38、l: http:/ 2章章 最小树与最小树形图最小树与最小树形图 （第（第2 2讲）讲）（最小树形图、最大分枝）31“直接方式直接方式”：总经理直接传达；：总经理直接传达；“接力方式接力方式”：总经理只给某些部门经理打电话，而让这：总经理只给某些部门经理打电话，而让这些得到信息的部门经理打电话将信息进一步传达给其他某些些得到信息的部门经理打电话将信息进一步传达给其他某些部门经理，依此类推，最后将信息传达到所有部门经理部门经理，依此类推，最后将信息传达到所有部门经理. 如何决定传达信息的途径？如何决定传达信息的途径？ 信息传播是有向的，有一个信息传播是有向的，有一个“根根”。 信息传播途径（忽略

39、方向时）是一棵树。信息传播途径（忽略方向时）是一棵树。以上结构称为树形图，上面这样一类问题称为最小树形图问题. 例例2.6 信息传播信息传播2.3 最小树形图 例32定义定义2.3 有向图有向图G=（V，A）若满足：）若满足：（1）不包含有向圈；）不包含有向圈；（2）存在一个顶点）存在一个顶点i使得使得d - (i)=0（即顶点（即顶点i没有入弧），而对其没有入弧），而对其余顶点余顶点j有有d - (j)=1（即顶点（即顶点j有且只有一条入弧）；有且只有一条入弧）；则称则称G为以为以i为根（为根（Root）的树形图（）的树形图（Arborescence），也称有），也称有根树（根树（Roote

40、d Tree）或外向树（）或外向树（Out-Tree）. 定义定义2.4 如果一个有向图的支撑子图是一个树形图，则称该树如果一个有向图的支撑子图是一个树形图，则称该树形图为该有向图的支撑树形图形图为该有向图的支撑树形图( (或生成树形图或生成树形图). ). 有向网络中权有向网络中权最小的支撑树形图称为该网络的最小树形图最小的支撑树形图称为该网络的最小树形图. . 2.32.3最小树形图最小树形图 定定义义33定义定义2.5 设设v是网络是网络N的任意一个节点，在所有指向的任意一个节点，在所有指向v的入弧中，的入弧中，权最小的弧称为权最小的弧称为v的最小入弧的最小入弧. 由最小入弧组成的有向圈

41、称为由最小入弧组成的有向圈称为最小入弧圈最小入弧圈. 若网络若网络N的每个节点取最小入弧组成的子图是支撑树的每个节点取最小入弧组成的子图是支撑树形图，则它就是最小树形图形图，则它就是最小树形图. (书上说法有误书上说法有误)如果在网络如果在网络N中，从每个节点取一条最小入弧，组成中，从每个节点取一条最小入弧，组成的子图是否就是最小树形图？的子图是否就是最小树形图？ 2.32.3最小树形图最小树形图 v 从树形图的根到每一个节点有且仅有一条有向路，这条路的从树形图的根到每一个节点有且仅有一条有向路，这条路的长度称为该节点的代（即该节点关于根节点的层数）长度称为该节点的代（即该节点关于根节点的层数

42、）. . v 树形图在去掉每条弧的方向后，得到的无向基本图是一棵树，树形图在去掉每条弧的方向后，得到的无向基本图是一棵树，因此具有因此具有n个节点的树形图包含个节点的树形图包含n-1 1条弧条弧. . 34引理引理2.2 网络网络N每个节点取一最小入弧，组成的图记为每个节点取一最小入弧，组成的图记为H，则，则（1）若）若|H|n-1，（2）若）若|H|=n-1 ，（3）若若|H|=n ，2.32.3最小树形图最小树形图 引引理理证明证明(略略)Ha最小树形图是否一定是最小树形图是否一定是，或或去掉一条弧？去掉一条弧？则则N没有支撑树形图；没有支撑树形图；且且H不含有向圈，则不含有向圈，则H是是

43、N的最小树形图的最小树形图;设设a是是H中权最大的弧，且中权最大的弧，且Ha不含有向圈，不含有向圈，则则Ha是是N的最小树形图的最小树形图.35),(kkkvva 定理定理2.3 设设C是网络是网络N的最小入弧圈，如果的最小入弧圈，如果N存在支撑树形图，则存在支撑树形图，则存在存在N的最小树形图的最小树形图T满足满足| C T |=1. 证明证明 假设定理不成立，在假设定理不成立，在N的最小树形图中找一棵的最小树形图中找一棵T使得使得| C T | 最小最小. . 2.32.3最小树形图最小树形图 定理定理由于树形图不含有向圈，由于树形图不含有向圈，因此因此| C T |= .记记C中不在中不

44、在T上的弧依次为上的弧依次为, , 则则C中余下的弧组成的有向路中余下的弧组成的有向路, , 都属于都属于T. ),(111vva ),(222vva ),(kkkvva ),(21vvP),(32vvP),(1vvPk不妨设不妨设 v1是所有是所有k个节点个节点 v1 , ,v2 , , ,vk 在在T T 中代数最小的节点，则中代数最小的节点，则 v1在在T T 中不会是中不会是 v2的后代的后代),(111vva ),(222vva ),(21vvP),(32vvP),(1vvPk但由于但由于v2在在T T 中是中是v1的后代，所以的后代，所以 v2在在T T 中不会是中不会是 v2的后

45、代的后代. . C36v2在在T T 中一定有入弧中一定有入弧( (记为记为 a1 ) )，则，则 T = = T+ +a2 - -a1 也是也是N N 的支撑树形图的支撑树形图. . 2.32.3最小树形图最小树形图 定理定理 因为因为 W(W(a2 ) ) W(W( a1 ) ) 所以所以因此因此T 也是也是N N 的最小树形图，的最小树形图，且且|CT |=|CT|-1这与这与T 的取法矛盾的取法矛盾. . 故定理得证故定理得证. . ),(111vva ),(222vva ),(kkkvva ),(21vvP),(32vvP),(1vvPka1)()()()()(12TWaWaWTWT

46、W即即: :最小入弧圈中除一条弧外最小入弧圈中除一条弧外, ,包含在某个最小树形图中包含在某个最小树形图中. .37关键关键: : 如果最小树形图的根节点在圈上，只需去掉圈上的一条如果最小树形图的根节点在圈上，只需去掉圈上的一条弧弧( (根节点的入弧根节点的入弧) )即可：即可：记记C C中的最大弧为中的最大弧为a* *，则权和为，则权和为W(W(C )-W()-W(a* * ) )2.32.3最小树形图最小树形图 定理的意义定理的意义如果根节点在圈外呢如果根节点在圈外呢? ?必须找一条从圈外指向圈上某节点的弧必须找一条从圈外指向圈上某节点的弧a来代替圈上指向该节点的弧来代替圈上指向该节点的弧

47、a1： 替代后的权和为替代后的权和为 W(W(C )+ W()+ W(a )- W()- W( a1 ) )自然希望在上述两种可能性中使总权和增加的量尽可能小自然希望在上述两种可能性中使总权和增加的量尽可能小! ! 即要比较即要比较W(W(C )-W()-W(a* * ) )和和W(W(C )+ W()+ W(a )- W()- W( a1 ) )引入引入“收缩收缩”的概念的概念 - 弧弧a: “: “收缩收缩”前的权前的权: W(: W(a ) ) “ “收缩收缩”后的权后的权: W(: W(a )- W()- W( a1 ) + W() + W(a* * ) )a1aCa*38定义定义2.

48、6 设设C是有向网络是有向网络N=(V，A，W)的一个有向圈，的一个有向圈，W为权为权函数函数. 记记C的节点集为的节点集为V(C)，弧集为，弧集为A（C）. 定义定义N收缩收缩C后得后得到的新网络到的新网络N*=（V*，A*，W*）为）为:V*= V V(C) y ，（节点，（节点y称为收缩称为收缩C后的人工节点）后的人工节点） A*= A A(C) ，其中其中a1 1是是C中与中与a有相同末端的弧，有相同末端的弧， a* *是是C中权最大的弧中权最大的弧. 这一这一过程称为过程称为网络的收缩（网络的收缩（Condensation），），N*称为称为N的收缩网络的收缩网络（Condensed

49、 Network），可简记为），可简记为N*=N/C. 收缩网络的最小树形图与原网络的最小树形图有何关系收缩网络的最小树形图与原网络的最小树形图有何关系? ?收缩网络收缩网络 定定义义,),()()(,),()(*1*yNaaWaWaWyNaaWaW中的末端是在当中的末端不是在当39定理定理2.4 设设C是网络是网络N=（V,A,W）的最小入弧圈，）的最小入弧圈，N*=N/C=（V*,A*,W*）是）是N收缩收缩C后得到的新网络后得到的新网络. 如果如果T*是是N*的最小树的最小树形图，则形图，则T* C包含了包含了N的一棵最小树形图的一棵最小树形图. 证明证明 记记a*是是C C中权最大的弧

50、中权最大的弧. . 首先证明首先证明T* C中包含中包含N N中的一棵中的一棵权为权为W*(T*)+ W(C)- W( ( a*) )的支撑树形图的支撑树形图. .下面分两种情况讨论下面分两种情况讨论 收缩网络收缩网络 定理定理40收缩网络收缩网络 定理定理(2)(2) 设人工节点设人工节点y是是T*的根节点：此时的根节点：此时T2= =T* Ca*为为T* C包含包含的的N中的一棵支撑树形图中的一棵支撑树形图, ,且且 ).()()()(*2aWCWTWTW(1)(1)人工节点人工节点y在在T*中有入弧中有入弧( (记为记为a0) )：设：设C C中与中与a0有相同末端的有相同末端的弧为弧为

51、a1，则，则T1= =T* Ca1为为T* C包含的包含的N中的唯一支撑树形图中的唯一支撑树形图. . )()()()()()()()()()()()(*0*1010*0*aWCWTWaWCWaWaWaWCWaWaWTWaTaaTaa0a1a*a*41收缩网络收缩网络 定理定理所以所以类似于上面两种情况的讨论类似于上面两种情况的讨论, ,可以进一步得到可以进一步得到 W(T 0) = W*(T 0*) +W（C）-W（a*）根据定理根据定理2.3, 存在存在N的最小树形图的最小树形图T0使得使得|CT0 |=1. 在收在收缩缩C后后, T0变成变成N*中的支撑树形图中的支撑树形图T 0*, 因

52、此因此 W*(T 0*) W*(T*)于是只能有于是只能有W*(T 0*) = W*(T*), ,也就是说也就是说T 0*也也是是N*中的最小中的最小树形图树形图. .因为否则的话因为否则的话, ,T0不会是不会是N中的最小树形图中的最小树形图 ( (T1或或T2才才是是N中的最小树形图中的最小树形图).).T1和和T2是是T* C中包含的中包含的N中的最小树形图，权为中的最小树形图，权为W*(T*)+ W(C)- W( ( a*) )()()()()()(21*0TWTWaWCWTWTW证毕证毕42基本思想：收缩基本思想：收缩 展开展开 （EdmonsEdmons算法，算法，19681968

53、）STEP0.STEP0. 令令m=1 1， N1( (V1, ,A1, ,W1)=)=N( (V, ,A, ,W) )朱朱( (永津永津)-)-刘刘( (振宏振宏) )算法（算法（19651965）STEP1.STEP1. 在在Nm中对每个节点取一条最小入弧，组成的弧集记为中对每个节点取一条最小入弧，组成的弧集记为Hm. . 若若| |Hm|Vm|-1|-1，则原网络没有支撑树形图；否则若，则原网络没有支撑树形图；否则若| |Hm|=|=|Vm| | ，则去掉，则去掉Hm中的权最大的一条弧（仍记为中的权最大的一条弧（仍记为Hm），继续下一步；否则直接继续下一步），继续下一步；否则直接继续下一

54、步. . STEP2.STEP2.若若Hm不包含圈不包含圈, ,则令则令Hm= =Hm，转，转STEP4STEP4；否则取；否则取Hm包含的一个圈包含的一个圈Cm，继续下一步继续下一步. . STEP3.(STEP3.(收缩收缩) )对对Nm收缩收缩Cm得到新的网络得到新的网络Nm+1( (Vm+1, ,Am+1, ,Wm+1) )，记人工节点，记人工节点为为ym. . 令令m=m+1，转，转STEP1. STEP1. STEP5:STEP5:( (展开展开) )令令Hm-1 = = Hm ( (Cm-1 am-1) )，其中，其中am-1是是Cm-1中的一条弧：如中的一条弧：如果果ym-1在

55、在Hm中有入弧，则取中有入弧，则取am-1为与该入弧有相同末端的弧；为与该入弧有相同末端的弧； 否则否则am-1取取Cm-1中的权最大的一条弧中的权最大的一条弧. . 令令m=m-1-1，转，转STEP4.STEP4. STEP4STEP4：若：若m=1=1，则，则H1就是就是N N中的最小树形图，结束；否则继续下一步中的最小树形图，结束；否则继续下一步. . 43朱朱- -刘算法刘算法 复杂性分析复杂性分析上述算法实际上包括两大过程：上述算法实际上包括两大过程：收缩（收缩（STEP1STEP3STEP1STEP3）和展开（）和展开（STEP4STEP5STEP4STEP5）. . 每一个过程

56、最多循环（每一个过程最多循环（n-1 1）次）次. . 容易容易看出看出STEP1的复杂度为的复杂度为O（m），），STEP2的复杂度为的复杂度为O(n)，STEP3的复杂度为的复杂度为O（m），），STEP4的复杂度为的复杂度为O（1），），STEP5的复杂度为的复杂度为O（m）。）。因此朱因此朱- -刘算法的总复杂度为刘算法的总复杂度为O（mn）. 该算法同样可以用于计算最大树形图（只需将权反号即可）该算法同样可以用于计算最大树形图（只需将权反号即可）. . 对算法作一些小的改动，容易设计求具有固定根的最小树形对算法作一些小的改动，容易设计求具有固定根的最小树形图或最大树形图（留作练习）图或最大树形图（留作练习）. . 44N=NN=N1 1H H1