（应用数学专业论文）度约束最小生成树算法.pdf

摘要我们生活在一个网络社会中。从某种意义上说，现代社会是一个由计算机信息网络、电话通信网络、运输服务网络、能源和物质分派网路等各种网络所组成的复杂的网络系统。网络优化就是研究如何有效的计划、管理和控制这个网络系统。使之发挥最大的社会效益和经济效益。其中，度约束最小生成树问题是网络优化中一个常见的问题。现实世界中，有着许多这样的例子。例如：电路设计、管道铺设、计算机网络、通信系统等等。如何求解网络的度约束最小生成树问题已成为一个好的研究课题。本文的主要工作概述如下：在第二章，我们对单点度约束最小生成树问题进行了研究。首先给出了单点最大度约束最小树算法并分析了该算法的复杂度，该算法的复杂度为o ( n 2 ) 。为了便于在计算机上操作，我们给出了相应的权矩阵法。其次，经过分析我们发现：在网络g ( v ，e ，g ) 的所有生成树中，顶点v n 的最小度刚好等于网络g ( v ，e ，g ) 关于的分裂数，在此基础上提出了单点最小度约束最小树算法，该算法的复杂度为o ( n 2 ) 。在以上两个算法的基础上，我们推导得出了网络单点度约束最小树存在的充要条件，最后给出了单点度约束最小树算法，对已有的g l o v e - - k l i n g m a n 算法进行了改进，大量仿真实验表明改进后的算法是非常有效的。在第三章，主要研究了度约束最小生成树问题，针对度约束最小树问题我们给出了一种新的快速近似算法，实验结果表明算法的性能良好。在此基础上，我们又提出了解决旅行商问题的两步法，大量的仿真实验表明这一算法取得了良好的效果。关键词：网络最小树最小树算法旅行商问题a b s t r a c tw el i v ei nan e t w o r ks o c i e t y i nas e n s e ，m o d e r ns o c i e t yi sac o m p u t e ri n f o r m a t i o nn e t w o r k ，t e l e p h o n ec o m m t m i c a t i o n sn e t w o r k ，t r a n s p o r tn e t w o r k ，e n e r g ya n dm a t e r i a ld i s t r i b u t i o nn e t w o r ka n do t h e rn e t w o r kc o m p o n e n t so ft h ec o m p l e xn e t w o r ks y s t e m n e t w o r ko p t i m i z a t i o ni st h es t u d yo fh o we f f e c t i v ep l a n n i n g ，m a n a g e m e n ta n dc o n t r o lo ft h en e t w o r ks y s t e m m a k ei tt om a x i m i z et h es o c i a la n de c o n o m i cb e n e f i t s t h ed e g r e e - c o n s t r a i n e dm i n i m u ms p a n n i n gt r e ep r o b l e mi sac o m m o nn e t w o r ko p t i m i z a t o np r o b l e mi nt h er e a lw o r l d ，h a v em a n ye x a m p l e so f t h i s s u c ha s ：c i r c u i td e s i g n , p i p e l i n el a y i n g ，c o m p u t e rn e t w o r k s ，c o m m u n i c a t i o n ss y s t e m s ，a n ds o0 1 1 h o wt os o l v et h ec o n s t r a i n tn e t w o r km i n i m u ms p a n n i n gt r e ep r o b l e mh a sb e c o m eag o o dr e s e a r c ht o p i c 1 1 l em a i n w o r ks u m m a r i z e da sf c i l l o w s ：i nc h a p t e rt w o ，w eh a v eas i n g l ep o i n to ft h ec o n s t r a i n e dm i n i m u ms p a n n i n gt r e ep r o b l e mw a ss t u d i e d f i r s t , w ep r o p o s e dt h el a r g e s ts i n g l ep o i n to fm i n i m u ms p a n n i n gt r e ea l g o r i t h ma n da n a l y s i so ft h ec o m p l e x i t yo ft h ea l g o r i t h m c o m p l e x i t yo ft h ea l g o r i t h mi so ( n 2 ) i no r d e rt of a c i l i t a t et h eo p e r a t i o no nt h ec o m p u t e r ，w ea r eg i v e nt h er i g h to ft h ec o r r e s p o n d i n gm a t r i xm e t h o d s e c o n d l y ，w ef o u n dt h a tt h r o u g ha n a l y s i s ：a l lt h es p a n n i n gt r e ei nt h en e t w o r k , t h es m a l l e s td e g r e eo fv o o ne x a c t l ye q u i v a l e n tt ot h en u m b e ro fi t ss p l i t o nt h eb a s i s ，w ep r o p o s e dt h es m a l l e s ts i n g l ep o i n to f m i n i m u ms p a n n i n gt r e ea l g o r i t h m c o m p l e x i t yo f t h ea l g o r i t h mi so ( n 2 ) i nt h ea b o v ea l g o r i t h mo nt h e b a s i so ft w o ，w ed e d u c e dt h es u f f i c i e n ta n dn e c e s s a r yc o n d i t i o n so fk - g r e e c o n s t r a i n tm i n i m u ms p a n n i n gt r e ee x i s t , a n dg i v eas i n g l ep o i mo fk - d e g r e e c o n s t r a i n tm i n i m u ms p a n n i n gt r e ea l g o r i t h m t h eg l o v e k l i n g r n a na l g o r i t h mh a sb e e ni m p r o v e d ，al a r g en u m b e rs i m u l a t i o ne x p e r i m e n t ss h o wt h a tt h ei m p r o v e da l g o r i t h mi sv e r ye f f e c t i v e i nc h a p t e rt h r e e ，o u rm a i nc o n s t r a i n to nt h ed e g r e e - c o n s t r a i n tm i n i m u ms p a n n i n gt r e ep r o b l e m ，v i e wo ft h eb i n d i n gp r o b l e m ，w eg i v ean e wf a s ta l g o r i t h ms i m i l a rt ot h ep o b l e m e x p e r i m e n t a lr e s u l t ss h o wt h a tt h ea l g o r i t h mp e r f o r m a n c e o nt h i sb a s i s ，w ep r o p o s e dat w o - s t e ps o l u t i o no ft h et r a v e l i n gs a l e s m a np r o b l e m ，al a r g en u m b e ro fs i m u l a t i o ne x p e r i m e n t ss h o wt h a tt h ea l g o r i t h mh a sp r o d u c e dg o o dr e s u l t s k e y w o r d s ：n e t w o r km i n i m u mt r e em i n i m u mt r e ea l g o r i t h mt r a v e l i n gs a l e s m a np r o b l e m创新性声明本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中做了明确的说明并表示了谢意。申请学位论文与资料若有不实之处，本人承担切相关责任。本人签名：堡巡日期丝二丝上! !关于论文使用授权的说明本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕业离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。( 保密的论文在解密后遵守此规定)本人签名：堡鱼：丛导师签名：日期型笪：! 第一章绪论第一章绪论本章首先介绍了网络优化问题的研究背景和研究现状；然后介绍了一些网络优化问题的典型实例以及图与网络的数据结构表示；最后掘安的介绍了本文的主要研究内容。1 1 研究背景我们生活在一个网络社会中。从某种意义上说，现代社会是一个由计算机信息网络、电话通信网络、运输服务网络、能源和物质分派网路等各种网络所组成的复杂的网络系统。网络优化就是研究如何有效的计划、管理和控制这个网络系统。使之发挥最大的社会效益和经济效益。网络优化问题是人们在工程技术、科学研究和经济管理的诸多领域中经常遇到的问题。结构设计要在满足强度要求等条件下使得所用材料的总重量最轻；资源分配要使各用户利用有限的资源产生的总效益最大；安排运输方案要在满足物资需求和装载条件下使得运输总费用最低；编制生产计划要按照产品工艺流程和顾客需求，尽量降低人力、设备、原材料等成本使得总利润最高。可以预料，随着科学技术尤其是计算机技术的不断发展，以及数学理论与方法向各门学科和各个应用领域的更广泛、更深入的渗透，网络优化理论和技术必将在社会的诸多方面起着越来越大的作用。网络优化的理论与方法已经广泛的渗透于运筹学、信息论、控制论、管理科学和计算机科学等领域，并在工程技术、经济，军事等诸多方面都有着极为重要的应用。整个社会形成了一个巨大的复杂系统。网络优化能为人们控制和管理这个系统提供一种有效的方法。由于大规模网络优化问题的需要，研究各种有效的算法直是网络优化研究的一个主旋律。但是人们发现，网络优化中的许多问题很难找到有效的算法，这使得计算复杂度和近似算法的研究越来越收到普遍的重视。这两者的结合正是当前网络优化研究的热潮。1 2 网络优化问题的实例经典的组合数学主要研究的问题是关于有限的离散对象的安排和选择。习惯上，组合学家关心的是安排和选择的存在性和计数，即，这样的安排或选择存在吗? 有多少这样的安排或选择? 而组合最优化是研究在所有可能的安排或选择中如何挑选“最好”的。与图和网络有关的组合最优化问题称为刚络优化问题。具体度约束最小生成树问题的研究的说，大多数网络优化问题就是在网络上找一个某种特定的子网络，使它满足特定的条件。网络优化的内容非常丰富，下面我们给出一些经典的实例。1 公路连接问题( h i g h w a yl i n kp r o b l e m )某一地区有若干个主要城市，现在准备修建高速公路把这些城市连接起来，使得从任何一个城市都可以经高速公路直接或间接地到达另一个城市。假定已经知道任意两个城市之间修建高速公路的成本，那么应如何决定在那些城市间修建高速公路，使得总成本最低?2 最短路问题( s h o r t e s t p a t h p r o b l e m )一名货车司机奉命在最短的时间内将一车货物从甲地运往乙地。从甲地到乙地的公路网纵横交错，因此有多种行车路线，这名司机应选择那条线路呢? 假设货柜车的运行速度是恒定的，那么这一问题相当于需要找到一条从甲地到乙地的最短路。3 运输问题( t r a n s p o r t a t i o np r o b l e m )某种原材料有m 个产地，现在需要将原材料从产地运往n 个使用这些原材料的工厂。假定m 个产地的产量和n 个工厂的需求量已知，单位产品从任一产地到任一工厂的费用已知，那么如何安排运输方案可以使得总运输成本最低?4 指派问题( a s s i g n m e n tp r o b l e m )一家公司经理准备安排n 名员工去完成n 项任务，每人一项。由于各个员工的特点不同，不同的员工去完成同一项任务时所获得的回报是不同的，如何分配工作方案可以使得总回报最大?5 中国邮递员问题( c h i n e s e p o s t m a n p r o b l e m )一名邮递员负责投递某个街区的邮件。如何为他设计一条最短的投递路线( 即，从邮局出发，经过投递区内的每条街道至少一次，最后返回邮局) ? 由于这一问题是由我国管梅谷教授1 9 6 0 年首先提出的，所以国际上称之为中国邮递员问题。6 旅行商问题( t r a v e l i n gs a l e s m a np r o b l e m )一名推销员准备前往若干城市推销产品。如何为他设计一条最短的旅行路线( 即，从驻地出发，经过每个城市恰好一次，最后返回驻地) ? 这一问题的研究历史十分悠久，通常称之为旅行商问题。除此以外，比较经典的还有最大流问题，最小费用流问题和最小费用循环流问题，在此我们就不一一介绍了，有兴趣的读者见参考文献【1 一l o 】。我们不难发现上述问题有两个共同的特点：一是它们的目的都是从若干可能的安排或方案中寻求某种意义下的最优安排或方案，数学中把这种问题称为优化问题( o p t i m i z a t i o n p r o b l e m ) ，二是它们都易于用图形的形式直观的描述和表达，第一章绪论数学中把这种与图相关的结构称为网络( n e t w o r k ) 。与图和网络相关的最优化问题就是网络最优化或称网络优化( n e t w o r ko p i t i m i z a t i o n ) 问题。1 3 图与网络的数据结构网络优化研究的是网路上的各种优化模型与算法。为了在计算机上实现网络优化的各种算法，首先我们必须用一种方法来在计算机上描述图与网络。一般来说，算法的好坏与网络的具体表示方法有很大的关系。这里我们将给出计算机上用来描述网络的5 种常用表示方法。在下面的讨论中，我们首先假设g = ( y ，彳) 是一个简单的有向图，l 矿| - 万，i a l _ m ，并假设v 中的顶点用自然数1 ，2 ，栉表示，4 中的弧用自然数l ，2 ，m 表示。值得注意的是，在此我们只讨论简单有向图的表示方法。1 邻接矩阵表示法邻接矩阵表示法是将图以邻接矩阵( a d j a c e n e ym a t r i x ) 的形式储存在计算机中。图g = ( 矿，彳) 的邻接矩阵c 的定义如下：c 是一个疗聆的0 - 1 矩阵，即c = ( ) 。 o ，1 ) ”f 0 ，( f ，力萑a9【l ，( f ，- ，) a也就是说，如果两节点之间有一条弧，则邻接矩阵中对应的元素为l ；否则为0 。每行元素之和正好是对应顶点的出度，每列元素之和正好是对应顶点的入度。可以看出，这种表示法非常简单、直接。但是，在邻接矩阵的所有玎2 个元素中，只有m 个非零元素。如果网络比较稀疏，这种表示法就会浪费大量的储存空间，从而增加了在网络中查找弧的时间。图1 1 有向简单图图1 1 所示的有向简单图用邻接矩阵可表示为度约束最小生成树问题的研究oloo01oooooolo0oo1lo2 关联矩阵表示法关联矩阵表示法是将图以关联矩阵( i n c i d e n c em a t r i x ) 的形式储存在计算机中。图g = ( 矿，爿) 的关联矩阵是如下定义的：b 是一个”聊的矩阵，即b = ( ) 。 - i ，0 ，l r “i i ，j ，v ，_ j = ( f ，) 彳屯= 一1 ，j _ ，v ，七= u ，0 彳1 0 ，其它在关联矩阵中，每行对应于图的一个节点，每列对应于图的一条弧。如果一个节点是一条弧的起点，则关联矩阵中对应的元素是l ；如果一个节点是一条弧的终点，则关联矩阵中对应的元素为一1 ；如果一个节点与一条弧不关联，则关联矩阵中对应的元素为0 。对于简单图，关联矩阵每列只含有两个非零元素( 一个是i ，另一个是一1 ) 。在关联矩阵中，每行元素i 的个数正好是对应顶点的出度，每行元素一i 的个数正好是对应顶点的入度。可以看出，这种表示法也是非常的简单，直接。但是，在关联矩阵的所有r i m 个元素中，只有2 m 个为非零元素。如果网络比较稀疏，这种表示法就会浪费大量的储存空间，从而增加了在网络中查找弧的时间。但是由于关联矩阵有许多特别重要的理论性质，因此它在网络优化的理论分析中经常用到。以图1 1 所示的有向简单图为例，如果关联矩阵中每列对应弧的顺序为( 1 ，2 ) ，( 1 ，3 ) ，( 2 ，4 ) ，( 3 ，2 ) ，( 4 ，3 ) ，( 4 ，5 ) ，( 5 ，3 ) ，( 5 ，4 ) 则关联矩阵可表示为：1l一10o一1ooooooo1一looll一1olooooooo0oo一1o101一l1l3 弧表表示法弧表表示法将图以弧表( a r cl i s t ) 的形式储存在计算机中。所谓图的弧表，也就是图的弧集合中的所有有序对。弧表表示法直接列出所有弧的起点和终点，共需2 m 个储存单元，因此当网络比较稀疏时比较方便。此外，对于网络图中每第一章绪论条弧上的权，也要对应的用额外的储存单元表示。图1 1 所示的有向简单图中，我们假设弧( 1 ，2 ) ，( 1 ，3 ) ，( 2 ，4 ) ，( 3 ，2 ) ，( 4 ，3 ) ，( 4 ，5 ) ，( 5 ，3 ) ，( 5 ，4 ) 上的权分别为8 ，9 ，6 ，4 ，0 ，3 ，6 ，7 ，则图1 1 的弧表表示见表1 1表1 1图的弧表表示起点ll234455终点23423534权896403674 邻接表表示法邻接表表示法将图以邻接表c a a j a c e n c yl i s t s ) 的形式储存在计算机中。所谓图的邻接表，也就是图的所有节点的邻接表的集合；而对于每个节点，它的邻接表就是它的所有出弧。邻接表表示法就是对图中的每个节点，用一个单向链表列出从该节点出发的所有弧，链表中每个单元对应于一条出弧。为了记录弧上的权，链表中每个单元除列出弧的另一个端点外，还可以包含弧上的权等作为数据域。图的整个邻接表可以用一个指针数组表示。图1 1 所示的有向简单图用邻接表表示为；这是一个5 维的指针数组，每一维c _ k 面表示法中的每一行) 对应于一个节点的邻接表，如第一行对应于第一个节点的邻接表( 即第一个节点的所有出弧) 。每个指针单元的第一个数据域表示弧的另一个端点( 即弧的头) ，后面的数据域表示对应弧上的权。5 星形表示法星形表示法的思想与邻接表表示法的思想有一定的相似之处。对每个节点，它也是记录从该节点出发的所有弧，但是它不是采用单向链表而是采用一个单一的数组表示。也就是说，在该数组中首先存放从节点1 出发的所有弧，然后接着存放从节点2 出发的所有弧，依此类推，最后存放从节点以出发的所有弧。对于每条弧，要依次存放其起点，终点和权的数值等有关信息。这实际上相当于对所度约束最小生成树问题的研究有弧给出了一个顺序和编号，只是从同一节点出发的所有弧可以任意排列。此外，为了能够快速检索从每个节点出发的所有弧，我们一般还用一个数组记录每个节点出发的弧的起始地址( 即弧的编号) 。在这种表示法中，可以快速检索从每个节点出发的所有弧，这种星形表示法称为向前星形( f o r w a r ds t a r ) 表示法。在图1 1 所示的有向简单图中，我们假设弧( 1 ，2 ) ，( 1 ，3 ) ，( 2 ，4 ) ( 3 ，2 ) ，( 4 ，3 ) ，( 4 ，5 ) ，( 5 ，3 ) ，( 5 ，4 ) 上的权分别为8 ，9 ，6 ，4 ，0 ，3 ，6 ，7 ，图1 1 所示的网络用向前星形表示法见表1 2 和表1 3节点号i1i2i3456l 起始地p o i n t ( i )13l 。579表1 3记录弧信息的数组弧编号l2345678起点l1234455终点23423534权89640367在数组p o i m 中，其元素个数比图的节点数多l ，且一定有p o i n t ( 1 ) = 1 ，p o i n t ( n + 1 ) = m + l 。对于节点f ，其对应的出弧存放在弧信息数组的位置区间为i p o i n t ( i ) ，p o i m ( i + 1 ) - i i 。如果p o i n t ( i ) p o i n t ( f + 1 ) 一1 ，则节点i 没有出弧。这种表示法与弧表表示法也非常的相似，“记录弧信息的数组”实际上相当于有序存放的“弧表”。只是在向前星形表示法中，弧被编号有序存放，并增加一个数组( p o i n t )记录每个节点出发的弧的起始编号。向前星形表示法有利于快速检索每个节点的所有出弧，但是不能快速检索每个节点的所有入弧。为了能快速检索每个节点的所有入弧，可以采用反向星形( r e v e r s es t a r ) 表示法：首先存放进入节点l 的所有弧，然后接着存放进入节点2的所有弧，依此类推，最后存放进入节点行的所有弧。对于每条弧，要依次存放其终点，起点和权的数值等有关信息。这实际上相当于对所有弧给出了一个顺序和编号，只是进入同一节点的所有弧可以任意排列。此外，为了能够快速检索进入每个节点的所有弧，我们一般还用一个数组记录进入每个节点的弧的起始地址( 即弧的编号) 。图1 1 所示的网络用反向星形表示法见表1 4 和1 5节点号fl23456l 起始地p o i n t ( i )l34579第一章绍论表1 5 记录弧信息的数组弧编号l2345678终点22333445起点31i45524权489o67631 4 研究现状最小生成树( m i n i m u ms p a n n i n gt r e e ) 问题是运筹学的网络优化中个常见的基本问题，业已有成熟的算法可进行有效的求解。但如果对生成树中的各项点度数( d e g r e e ) 再加上一定的限制，即不得超过预先给定的数值，则问题的性质将变得截然不同。现实世界中，有着许多这样的例子，如：电路设计、管道铺设、计算机刚络、通信系统等等。这种带有顶点度约束的最小生成树问题被称之为度约束最小生成树( d e g r e e c o n s t r a i n e dm i n i m u ms p a n n i n gt r e e ) ，简称( d c m s t ) ，其组合含义是从所有的生成树中( 总数至多可达撑”2 ) 找出顶点度符合约束且总权数最小的生成树，求解的难度随各顶点度约束的不同而不同。设g ( v ，e ，形) 为赋权的无向网络，v = 1 2 ，玎) 为网络的顶点集，e 为该网络的边集，矿为网络的权矩阵，矿是权矩阵，其中w l , = ，i = 1 ，2 ，疗；若h v e ( g ) ，则，= ( q v ，) ：若h 1 ，岳e ( g ) ，则= m 。并设各顶点的度约束为6 f ，f = 1 , 2 ，玎。于是当岛 n - 1 时，d c m s t 问题即转化为无约束情况下一般的最小生成树问题( m s t ) ，且有有效算法，例如文献【6 】中的p r i m 算法和k r u s k a l 算法。当某个龟 n - 1 时，即为单点度约束最小生成树，也有有效算法( 见 6 】中的g l o v e r - k l i n g r n a n 算法) 。目前，d c m s t 问题还没有找到有效的算法。对于求解一般情形的d c m s t 问题，曾经出现过一些精确的算法( 如分支定界法 3 4 1 ) ，但该算法的时间复杂度为指数级的，无法实现规模较大的实际问题；马良等给出了一种由贪婪思想而来的启发式快速近似算法 3 5 】，该算法的时间复杂度为o ( 矿) 。丁爱兵给出了度约束最小生成树的竞争决策算法( 见参考文献【2 】) 。除此以外，还有很多的智能算法用于求解度约束最小树问题，例如：遗传算法、蚂蚁算法、迸化算法等等。1 5 本文的主要研究内容本文主要研究了网络优化中带有度约束的最小生成树问题，提出了单点最大度约束最小树算法，单点最小度约束最小树算法，单点度约束最小树算法，多点度约束最小生成树问题的研究度约束最小树快速近似算法以及网络的h a m i l t o n 圈的快速近似算法。研究的主要内容如下：1 在第一章，首先介绍了网络优化问题的研究背景和研究现状；然后介绍了一些网络优化问题的典型实例以及图与网络的数据结构表示；最后扼要的介绍了本文的主要研究内容。2 在第二章，我们对单点度约束最小生成树问题进行了研究。首先给出了单点最大度约束最小树算法并分析了该算法的复杂度，该算法的复杂度为o ( n 2 ) 。为了便于在计算机上操作，我们给出了相应的权矩阵法。其次，经过分析我们发现：在网络g ( v ，e g ) 的所有生成树中，顶点v 0 的最小度刚好等于网络g ( v ，e ，g )关于v 0 的分裂数，在此基础上提出了单点最小度约束最小树算法，该算法的复杂度为o ( n 2 ) 。在以上两个算法的基础上，我们推导得出了网络单点度约束最小树存在的充要条件，最后给出了单点度约束最小树算法，对已有的g l o v e - - k l i n g m a n算法进行了改进，大量仿真实验表明改进后的算法是非常有效的。3 在第三章，我们主要研究了度约束最小生成树问题，针对度约束最小树问题我们给出了一种新的快速近似算法，实验结果表明算法的性能良好。在此基础上，我们又提出了解决旅行商问题的两步法，大量的仿真实验表明这一算法取得了良好的效果。第二章单点度约束最小生成树9第二章单点度约束最小生成树本章主要对单点度约束问题进行了研究。首先给出单点最大度约束最小生成树算法和单点最小度约束最小生成树算法，然后给出了改进后的g l o v e k l i n g m a n算法，最后进行了仿真实验，实验结果表明改进后的算法是非常有效的。2 1 单点度约束最小生成树问题的概述最小生成树问题是组合优化中的一个重要的问题。自五十年代后期r o s e n s t i e h l 、p r i m 和k r t m k a l 先后给出求解这一问题的算法以来，人们对这个问题的研究兴趣一直未断，相关的理论被应用到很多领域。现在这个问题已经得到了很好的解决，其中经典的算法有破圈法、边割法、还有避圈法。但是在实际中对最小树问题又会有这样那样的限制，正如本章中所探讨的网络g ( v ，e ，) 关于的最大度约束条件下的最小树问题和网络g ( v ，e ，) 关于的最小度约束条件下的最小树问题，以及网络g ( v ，e ，矿) 关于v 0 的k 度约束条件下的最小树问题。2 2 单点度约束生成树问题的相关概念本章中涉及到的图均指简单的连通图，涉及到的网络均指简单的连通无向网络。用g ( v ，e ) 表示一个简单的连通图，简记为g ，其中矿( g ) 表示图的顶点集，简记为矿。e ( g ) 表示图的边集，简记为e ，特别的用e v o ( g ) 表示图g 中与v 0 关联的边集。用g ( v ，e ，r v ) 表示一个简单的连通无向网络，表示权矩阵，其中= ，i = l ，2 ，以；若v 以g ) ，则= 缈( q v j ) ：若v j 吩g e ( g ) ，则= 0 0 。定义2 2 1 1 6 设g ( v ，e ，w ) 是一个连通的无向网络，v 0 是网络中特别指定的一个顶点，k 为给定的一个正整数，如果r 是g 的一个支撑树且d r ( v o ) = k ，则称r为g 的k 度限制支撑树。其中g 中权最小的k 度限制支撑树称为g 的最小k 度限制树。定义2 2 2 设g ( v ，e ，w ) 是一个简单的连通无向网络，v n 是网络中特别指定的一个顶点，在这个网络的所有支撑树中找出使得吒的度最大的那些支撑树，并且在所找的这些支撑树中权最小的那个支撑树就叫做网络g ( v ，e ，矿) 关于v n 在最大度约束条件下的最小生成树。1 0度约束最小生成树问题的研究定义2 2 3 设g ( v ，e ，w ) 是一个简单的连通无向网络，是图中特别指定的一个顶点，在这个网络的所有支撑树中找出使得v n 的度最小的那些支撑树，并且在所找的这些支撑树中权最小的那个支撑树就叫做网络g ( v ，e ，w ) 关于v 0 在最小度约束条件下的最小生成树。定义2 2 4 设g ( v ，e ) 是_ 个简单的连通无向图，是图中特别指定的一个顶点。我们称g v o 为图g ( v ，e ) 关于的分裂图，简记为l v o ( g ) ，其中g v 0 表示从图g ( v ，e ) 中去掉以及与v o 相关的边后所得到的新图。定义2 2 5 设t v o ( g ) 是图g ( v ，e ) 关于v 0 的分裂图，不妨设l v o ( g ) 有r 个连通分支，则我们称t 为图g ( v ，e ) 关于的分裂数，我们用q ( k ，e ) ，信1 2 ，t 来表示分裂图l v o ( g ) 的t 个连通分支。定理2 2 1 设g ( v ，e ) 是简单的连通图，我们用表示图g ( v ，e ) 的所有支撑树的集合，即= 口i 堤图g 自勺支撑树) ，则碍臻 由( v 0 ) ) = 如( v o ) ，( 其中西( v 0 ) 表示顶点v o 在t 中的度，如( v 0 ) 表示顶点v 0 在g 中的度) 。证明在图g 的生成树集合中任意取一棵生成树r ，显然露m ) 如( v o ) ，所以我们只要能构造出一棵生成树，其中v 0 的度等于如“) 。而这样的生成树是存在的，构造方法如下：在g 中任取一个圈c l ，从c 1 中去掉一条不与v o 关联的边，从而得到图g l ，在g l 中任取一个圈c 2 ，从c 2 中去掉一条不与v o 关联的边，从而得到图g 2 ，这样依此下去，直到所得的图没有圈为止，因为每次去掉的边不与v 0 关联，所以每次所得图中v 0 的度不会变，即最后所的到的图就是我们要构造的树。定理2 2 2 设g ( v ，e ) 是简单的连通图，我们用表示图g ( v ，e ) 的所有支撑树的集合，即= p i 琨图g 的支撑树) ，则零簪 露( v 0 ) = f ，( 其中露( v o ) 表示顶点v 0 在丁中的度，t 为图g ( v ，e ) 关于v 0 的分裂数) 。证明在图g 的生成树集合中任意取一棵生成树r ，显然有西( v o ) r ，所以我们只要能构造出一棵生成树，其中的度等于吃( ) 而这样的生成树是存在的，构造方法如下：设q ( k ，互) i = l ，2 ，t 是图g 关于v o 分裂后的，个连通分支，首先分别求这r 个第二章单点度约束最小生成树连通分支的支撑树，记为7 = ，i = 1 ，2 , - - t ，然后在这，棵支撑树中各找一个在g 中与v 0 关联的顶点，记为e ，江1 , 2 ，f ，最后将这，棵支撑树以及r 条边q = ( v o ，m ) ，i = 1 , 2 t 合起来就组成了我们要构造的生成树。定理2 2 3 嘲设r 是g 的k 度限制支撑树，则r 是g 的最小k 度限制树当且仅当下面三个条件同时成立：( i ) 对于g 中任何两条与关联的边所产生的r 的可行交换都是不可改进的，即是说，r 通过这类可行交换得到的新的i 度支撑树r 满足形口) 形( d ；( i i ) 对于g 中任何两条不与v n 关联的边所产生的丁的可行交换都是不可改进的；( i i i ) 对于丁的任何两个! e l z - 交换( + q ，一彳) 和( 十p 2 ，一左) r 若白，五与关联，e 2 ，石不与关联，则有) + ( 五) ( e 1 ) + 矿( 吃) 。2 3 单点最大度约束最小树问题2 3 1 单点最大度约束最小树的算法设两络g ( 矿，e ，形) 是一个简单的连通网络，其中f y 栉，i e 埘，用e v o ( g )表示网络g 中与v 0 关联的边集，不妨设i 如( g ) k 。用e ( g ) e v o ( g ) 表示网络g中不与关联的边集，显然j e ( g ) 、( g ) l - 槐一k 。算法步骤：s t e p o ：求e v o ( g ) ，e ( g ) e v o ( g ) 以及i e v o ( g ) i ，( 不妨设求得i e v o ( g ) | - k ) ，将e ( g ) e v o ( g ) 中的m k 条边按权的大小排好顺序，即要求( 与) w ( e 2 ) ( ) ，令互= ( v ，e v o ( g ) ) ，置i = 1 ，y = k ；s t e p l ：若i + 巳含有圈，转s t e p 2 否则转s t e p 3s t e p 2 ：置i = f + l ，若i m k ，转s t e p l ；否则停止，g 中不存在支撑树；s t e p 3 ：令弓+ i = 弓+ 毫，并置歹= 歹+ l ；转s t e p 4 ：s t e p 4 ：若，= 疗一1 ，则结束，t 就是所要求得网络g ( v ，e ，矿) 关于v 0 的最度约束最小生成树问题的研究大度约束条件下的最小树；否则转s t e p 2 。2 3 2单点最大度约束最小树算法的正确性在算法进行的过程中，弓始终不含圈，因此算法结束时，若得到乙一1 ，则乙一i为网络g ( v ，e ，w ) 关于v o 的最大度约束条件下的支撑树，下面的定理2 3 2 1 将要证明乞一l 就是网络g ( 矿，e ，形) 关于v o 的最大度约束条件下的最小树；若得到0 ，但是j t ，停止，图2 6 中的丁就是所求的网络g ( v ，e ，矽) 关于的最小度约束条件下的最小树，其中露) = 2 ，口) = 1 3 。2 4 3单点最小度约束最小树算法的复杂度现在我们分析一下单点最小度约束最小树算法的复杂度，算法的计算量主要在执行s t e p 2 ，所以我们主要分析第二步的计算量。假设网络g ( v ，e ，形) 关于v 0的分裂图有t 个连通分支q ( k ，磊) ，i - - i ，2 ：- - 1 ，针对每个连通分支求最小树，所需要的计算量为圭盟生匕銎警卫生，又因为t1 k i ：打一1 ，所以单点最小度约束j = lt=l最小树算法的复杂度不会超过求最小树的复杂度，即单点最小度约束最小树算法度约束最小生成树问题的研究2 5 单点度约束最小树算法2 5 ig l o v e k l i n g m a n 算法的理论基础定理2 5 1 嘲设，是g 的最小i 度限制树，e o 是g 中与v o 关联的边的集合，e = e o e ( t ) ，易= e ( 丁) 磊，令m = ( 十p ，一) l ( + p ，一力是7 的可行交换，e c e l ，厂岛) ，若m = o ，则g 中不存在k + l 度限制支撑树；若m a ，设w ( e ) 一w ( f ) = m i n w ( e ) 一w l ( + p ，一) m ，则t = t + e - 一广是g 的一个最小k + l 度限制树。定理2 5 2 嘲设r 是g 的最小j 度限制树，e o 是g 中与v 0 关联的边的集合，岛= e ( g ) 、( 岛u e ( 丁) ) ，日= 昂n e ( t ) ，令n = ( + f ，一力f ( + p ，一厂) 是t 的可行交换，e e e 3 ，厂目 ，若= o ，则g 中不存在j i 一i 度限制支撑树；若a ，设w ( e ) 一w ( f ) = m i n w ( e ) 一矿( 门f ( + p ，一力 ，则r = r + p 。一厂是g 的一个最小k - 1 度限制树。2 5 2g l o v e - k l m g m a n 算法的步骤算法步骤：s t e p o ：求出g 的最小树t ；s t e p l ：计算露( ) 。若由( v o ) = | i ，结束，r 为g 的最小后度限制树；若由( v 0 ) k ，转s t e p 3 ；s t e p 2 ：求出m ，若m = g ，停止，g 中不存在k 度限制支撑树；否则，求出e 和厂，置r = r + e 一厂，转s t e p l ；s t e p 3 ：求出j ，若n = g ，停止，g 中不存在k 度限制支撑树；否则，求出p 和厂，置t = t + e 一f ，转s t e p l 第二章单点度约束最小牛成树2 5 3 改进后的g l o v e k l i n g m a n 算法对g l o v e k l i n g m a n 算法改进之前我们首先给出以下的定理。定理2 5 3 设g 是一个连通的无向网络，是特别指定的一个顶点，r 是g的最小| i 度限制树，其中t k 吒( v o ) ，f 是g 关于v o 的分裂数，e o 是g 中与v 0 关联的边的集合，巨= 毛、e ( t ) ，e 2 = e ( r ) ，令m = ( + e ，一，) i ( + p ，一厂) 是丁的可行交换，e c e l ，厂岛) ，则m d 。定理2 5 4 设g 是一个连通的无向网络，v o 是特别指定的一个顶点，r 是g的最小露度限制树，其中， 素s 龟( 吒) ，是g 关于吒的分裂数，e o 是g 中与关联的边的集合，毛= e ( g ) ( u e ( t ) ) ，日= n e ( t ) ，令n = ( + p ，一) l ( + p ，一厂)是r 的可行交换，e e e 3 ，厂& ) ，则彩定理2 5 5 设g ( v ，e ，矿) 是一个简单的连通无向网络，v o 是图e p 指定的一个顶点，则网络g ( 矿，e ，肜) 关于v o 黼c 4 , k 度限制树存在当且仅当f k 如( ) ，其中f 为网络g ( v ，e ，矽) 关于的分裂数。设网络g ( v ，e ，矽) 是一个简单的连通无向网络，其中i v l _ h ，i e l = m 。改进后g l o v e k l i n g m a n 算法的算法步骤：s t e p 0 ：计算网络g ( v ，e ，形) 关于v 0 的分裂数t ，计算网络g ( 矿，e ，) 中与v o 关联的边数i i ，求网络g ( 矿，e ，形) 的最小树毛，并计算五中v o 的度如( v 0 ) ；s t e p l ：若k i e v o ( g ) l ，停止，网络g ( 矿，e ，) 没有最小后度限制树，若k = t ，停止，由单点最小度约束最小树算法可直接求得g ( v ，e ，)的最小量度限制树，若t k 矗( ) ，转s t e p 2 ，若七= 矗( v o ) ，停止，s t e p 0 中所求得毛即为刚络g ( 矿，e ，) 的最小k度限制树，度约束最小生成树问题的研究若矗( v 0 ) n - i 时，d c m s t 问题即转化为无约束情况下一般的最小生成树问题( m s d ，且有有效算法，例如文献 6 i c p 的p r i m 算法和k m s k a l 算法。当某个6 f n - - 1 时，即为单点度约束最小生成树，也有有效算法( 见【6 】中的g l o v e r - k l i n g m a n 算法) 。目前，d c m s t 问题还没有找到有效的算法。对于求解一般情形的d c m s t 问题，曾经出现过一些精确的算法( 如分支定界法 3 4 】) ，但该算法的时间复杂度为指数级的，无法实现规模较大的实际问题；马良等给出了一种由贪婪思想而来的启发式快速近似算法 3 5 】，该算法的时间复杂度为o ( n 3 ) 。3 2 度约束最小生成树的数学模型设g ( v ，e ，) 为赋权的无向图，v = 1 ，2 , - - - , 胛 为图的顶点集，占为边集，为网络的权矩阵，其中w i ，= o o ，i = l ，2 ，疗；若q e ( g ) ，则= 矽( k _ ) ；若v j g e ( 6 9 ，则= 0 0 。并设各顶点的度约束为6 f ，i = i ，2 ，胛，则d c m s t 问题的数学模型为：度约束最小牛成树问题的研究r a i nz = w , , x v，d ，= 1=q si , j e s而龟聍一1i iv s c v ，r s gv f y矗 o ，1 )v i ，v( 3 1 )( 3 2 )( 3 3 )(