（运筹学与控制论专业论文）网络中的超图嵌入问题.pdf

山东大学博士学位论文 网络中的超图嵌人问题 王 琦 ( 山东大学数学与系统科学学院，山东，济南2 5 0 1 0 0 ) 指导教师；李国君教授 中文摘要 在全光网络中，波分复用( w a v e l e n g t hd i v i 8 i o nm l l l t i n e 妇n g ) 网络技术在现实的 通信世界中扮演着基础和决定性的角色 若把网络看作一个图的模型，对于网络中的每一个通讯请求，如果每一个通讯 请求恰好只有网络中的两个节点组成( 一个源信号节点和一个接收信号节点) ，那么 在图模型中需要选择一条路当作它的通讯频道来满足其通讯请求而对于所有此类 通讯请求，需要在图模型中选定一系列通路来实现网络中的通讯请求，这些通路就 组成了这组通讯请求的一个路由 通常在实际的通讯网络中一个通讯请求含有网络中两个以上的节点，所以这种 更普遍的情况是将这一系列通讯请求看作是图( 或网络) 中的一个超图，而其中每个 通讯请求看作是此超图中的一条超边为了实现这种通讯请求，对超图中每条超边 需要确定一个路由算法来建立图( 或网络) 中一条虚拟通路或者说专用通路来连接此 超边的每个节点，在确定这样一个路由算法中最重要的一点是使得图中的每条边上 的最大阻塞度( c o n g e 8 t i o n ) 最小，其中阻塞度为任意一条边上通过的通路的数量， 此问题称作路由和波长( r w a ) 分配问题 如果将网络限定在一个环网络中，问题变为确定一个路由算法来实现超图在此 环中的通讯请求，并且使得此环中任意一边上的最大阻塞度最小此问题称作最小化 超图嵌入圈的最大阻塞度( m c h e c ) 问题此问题的结果在实际生活中应用广泛， 例如在并行计算问题中。并行计算机的处理器可以代表是超图的所有顶点，其中需 要互相传递信息的各组处理器看作是一条超边，m c h e c 问题的最优解对每一组内 所有处理器之间的通讯确定了一个路由算法使得计算机之间的最大阻塞度最小 本论文主要研究来源于w d m 网络带宽分配闻题的几个超图嵌入问题，对两类 有较深应用价值的网络结构：树环网络和环圈网络，考虑了其超图嵌入问题；而后 山东大学博士学位论文 讨论了有关加权有向超图在网络中的嵌入问题，以及图论中有向图的几个问题，共 分为五章 第一章主要介绍了w d m 网络的一些相关的最优化问题，关键定义和相关结 论，以及一些有向图问题的来源和相关结论 在第二章我们简化了m c h e c 问题的算法，用新的方法证明了几个关键引理 并且分别给出m c h e t r ( 超图嵌入树环) 问题和m c h e r c ( 超图嵌入环圈) 问题的 p t a s 算法 g a n l e y 和c o h o o n 提出了m c h e c 问题并且证明了此问题为完备的 定理1 声町m c h e c 问题为 厂户一完备的 m c h e c 问题存在一个p t a s 算法 2 0 】在算法进行过程中我们将超边分为两 部分来嵌入；足。妇， 和玑。，饥，i 。，对不同的u = l 阢。 2 ，也f 超边的嵌入又分两种情 况来讨论 当超边的数目为一个小数目时，利用穷举的方法易证m c h e c 问题的p t a s 算 法是存在的 定理2 廖口，对任意的常数c 0 ，当超边的数目牡e ( 1 0 9n ) 时，职。氲，讧中 的超边嵌入到圈中存在一个p t a s 算法特别地，对任一1 5 0 ，一个( 1 + e ) 近似比 的近似结果可以在o ( n ( c + 1 ) ) 时间内找到 应用线性放松和反随机方法来近似的解决超边为大数目时的m c h e c 问题可 得如下定理 定理4 胆刃当超边数目m 足够大，且锄c m ( 0 0 i np a r t i c u l a r , ，o r a n yg i v e n 0 ，as o l u t i o nw i t h ( 1 + e ) - f a c t o ro t h eo p t i m u m nb ef o u n di nt i m e d ( 佗( c + i ) l ) b yu s i n gl pr e l a x a t i o na n dd e r a n d o m i z a t i o nt e c h n i q u e sw ec a no b t a i nt h en e x t t h e o r e m t h e o r e m41 2 0 1t h em c h e c p r o b l e mc a nb es o l v e dw i t hap t a sw h e nt h e h y p e r e d g es e tr t li ss u f f i c i e n tl a r g ea n d 锄c ：r n ，( o o ) ： n + ： g 】： e ( x ) ： y ( s ) ： g ： w a v e l e n g t hd i v i s i o nm u l t i p l e x i n g p o l y n o m i a lt i m ea p p r o x i m a t i o ns c h e m e d ( ，( n ) ) c y ( 几) f o ra 黜t e m tc 0 粕u n c r a t e dg r a p hw i t hv e r t e xs e tva n de d g es e te a nd i r e c t e dg r a p hw i t hv e r t e xs e tva n da r cs e ta ac l i q u ew i t hnv e r t i c e s a c o m p l e t eb i p a r t i t eo i las e to fmv e r t i c e sa n d8s e to f 冗v e r t i c e s a p p r o x i m a t i o ns o l u t i o n o p t i m a ls o l u t i o n as e to f p a t h s r o u t i n ga n dw a v e l e n g t ha s s i g n m e n t w a v e l e n g t ha s s i g n m e n t a f a m i l yo fa l g o r i t h m s p o s i t i v ei n t e g e r t h es u b g r a p ho fgi n d u c e db ya g i v e nv e r t e xs e tx t h es e to fe d g e si ng i x 】 t h es e to fv e r t i c e si n c i d e n to i las u b s e to fe d g e ss c o m p l e m e n to fg x 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，独立进行 研究工作所取得的成果除文中已经注明引用的内容外，本论文不包含 任何他个人或集体已经发表或撰写过的科研成果对本论文的研究作出 重要贡献的个人和集体，均已在文中以明确方式标明本人完全意识到 本声明的法律责任由本人承担 论文作者签名：丑j 扛日期：珥望：卫 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学校保 留或向国家有关部门或机构送交论文的复印件和电子版，允许论文被查 阅和借阅；本人授权山东大学可以将本学位论文全部或部分内容编入有 关数据库进行检索，可以采用影印，缩印或其他复制手段保存论文和汇 编本学位论文 ( 保密的论文在解密后应遵守此规定) 论文作者签名：王算 导师签日期：刎! 绁 第1 章前沿 1 1 研究背景：基于波分复用技术的全光网络 波分复用( w d m ) 网络技术解决了一些新兴的应用问题，例如，超级电脑的可 视化问题和医学中的成像问题，都需要保证高速数据传输中低出错率，并且要求对 多用户传播的时间延迟最小【7 卅一个w d m 网络由很多传播光波的节点连接一些 点对点的光纤组成，而且节点和光纤组成的网络可以是任意的拓扑结构末梢节点 通过一些光学发送器和接收器与通路中的节点相连接 在w d m 网络中，光纤的带宽可以分为一系列并行信道，每条信道通过不同的 波长来通信每条信道的带宽为节点的传输速率网络通信存在一个关键问题；给 定网络中一系列通信要求( 源顶点和目标顶点对) ，每个通信要求需要找一条通路来 满足，并且分配给每条这样的通路一个信道使得拥有同样信道的通路不能在网络的 同一条连杆上共享因此应用w d m 技术的网络变为多信道网络满足上述通信要 求的一个办法为网络中的每个节点都安装一组信号转换器或过滤器，每个转换器或 过滤器应对一个通信信道显然这样做是要花费相当代价的，因此至于网络中的节 点数目不大时可以应用这个办法另外的办法为设计一种系统来满足当每个节点只 有少量的转发器( 一个或两个) 时的通信要求 一般情况下，w d m 光网络由一系列点对点的光纤连杆连接一系列通信节点构 成，每条光纤连杆的带宽只能够支持一定数量的波长在这种网络中，不同的通信 信号可以用不同的波长通过同一个连杆进入节点口，然后通过不同的连杆用各自原 来的波长离开1 9 唯一的约束为共享同一连杆的两条通路不能分配相同的波长 一个可转换光学网络由终端，开关或者两者兼有的一些互连节点构成终端节 点发送或者接收信号，开关指引这些输入的信号发送到一个或者更多的输出连杆 上在实际生活中每条连杆由一对无向连杆构成并且均为双向的我们可以研究当 通过无向光纤连杆的通信路为无向时的通信问题 1 】同样地，也可以考虑当连杆为 双向或者单向时的通信问题因此我们可以把这样的光学网络当成一个有向或者无 向图g = ( k e ) ，其中的边( 或弧) 代表网络中点对点的光纤连杆一个通信请求由 一个( 有序) 顶点对构成给定一系列通信请求，将波长分配给满足通信要求的点对 的( 有向) 通路，并且使得每条边上不能出现有相同波长的两条通路 1 山东大学博士学位论文 1 2 算法的一些关键定义 在本论文研究组合优化问题之前，我们需要回顾一些复杂度理论和图论方面的 关键定义有些定义很专业，所以我们只能介绍一些必需的定义 定义1 超图是一个有序组( k e ) ，其中v 是顶点的一个有限集合，e 为建立 在这些顶点上的一些超边，并且每条超边均为v- - 4 。q - 集：e = 如，t ，) 2 v ) 倍超边无向时j 定义2 【6 9 】p - 优化问题要么是一个最大化问题要么是一个最小化问题 n 的每个实例j 均有一个非空的可行解集合，每个解都被分配了一个非负有理数作 为目标函数值，并且存在多项式时间算法来确定有效性，可行性和目标函数值 定义3 假设a l 和如为两个判定问题，a l 可以在多项式时间归结为如，当 且仅当a 1 存在一个多项式时间算法a 1 ，且n l 多次地以单位费用把a 2 的算法n 2 用作子程序的算法，并且称a 1 为a 1 到a 2 的多项式时间归结 下面一个定义为多项式时间归结的一种特殊情况 定义4 称判定问题a 1 多项式变换到另一个判定问题a 2 ，如果给定任意字符串 g ，能在( 讥) 多项式时间内构造出字符串! ，使得z 为a 1 的是实例当且仅当! ，是 a 2 的实例 定义6 判定问题a p 称作是p 完备的，如果所有其他的a f t 问题都 能多项式变换到a 为了证明一个问题a 是否为 厂皿完备的，需要证明两个事实； ( 口) 此问题a p ( b ) 所有其他的 厂p 问题都能多项式变换到a 定义6 如果存在一个常数c 0 ，对足够大的m 使得d ( ，( n ) ) sc ，) ，则记此 复杂度为d ( ，( n ) ) 定义7 一个算法被称作有效的，如果此算法为确定性的并且在多项式时间内 完成 2 山东大学博士学位论文 定义8 对于一个p 优化问题，算法被称作a 近似算法，如果 1 此算法在多项式时间内完成 2 此算法得到一个解( a p x ) ，并且和最优解( o p t ) 之间存在一个系数比o ，使得 石a p 可x o t 那么。称为此算法的性能比( 或者近似比) 定义9 对于一个( 最小化) a f p 一优化问题，多项式时间近似方案( p t a s ) 为 一类算法a 如果给定一个常数e 0 ，a 能够在多项式时间内找到一个不超过最优 解1 + e 倍的解算法4 被看作一类算法群 a 1 f o ) 更多的有关n p - 完备性和复杂度的资料可以在g a r a y 和j o h n s o n 【3 1 】，以及 p a p a d i m i t r i o u 【7 3 ，7 6 】的著作中寻找 1 3w d m 网络中的几个优化问题 波分复用光网络中，每个信道用一种波长或者一个颜色来代替这种优化问题 要求最小化信道的总数给定网络中一系列通路p ，使p 中共享网络中任一条连杆 的通路分配不同的颜色称为p 的一个有效着色 这类信道分配的优化问题被称为波长路由分配( r w a ) 问题如下来定义此问 题，给定一系列通信请求，每个请求分配一条通路，并且使用最少的颜色来找到这 些通路的一个有效着色 当这一系列通路为已知时，优化问题被称为波长分配( w a ) 问题，如下来定义 此问题，给定网络这一系列通路，用最少的颜色来找到这些通路的一个有效着色 r w a 和w a 问题在网络和图论( 路染色问题) 中已经被精深的研究 2 4 ，3 2 ，7 8 ， 9 0 】，特别是在w d m 光网络中【2 ，8 ，4 6 ，6 2 ，6 6 ，8 a 在上述研究中将网络看作一个无 向图的模型更是有很广泛的应用 4 7 ，8 3 ，9 0 ，2 2 1 现今，w d m 网络技术在现实的通信世界中扮演着基础和决定性的角色同时 引发了许多新兴的有挑战性的优化问题【2 ，5 4 】下面我们描述几个相关的组合优化 问题 3 山东大学博士学位论文 1 3 1 波长分配和路染色问题 在不支持波长转换的全光网络中，波长的数量是有限的，所以在完成这些通讯 请求时需要使波长的数量最小我们可以将波长以色数来计，则在全光网络中的路 由波长分配问题转化为路染色问题实际生活中的网络用一个有向图g = ( ke ) 来 表示，而通讯请求用一些顶点对来代替，那么建立一个从顶点乱到t ，的通讯通路需 要分配给此通讯要求一条从钍到u 的有向路p ，并且用一种颜色来代替一种波长使 得此颜色和其他与p 共享相同边的通讯通路的颜色不同，也就分配给了此通讯请求 一个不同于其他通讯要求的一种波长路染色问题就是为了分配这些路和颜色给每 个通讯请求，并且使得色数最小 对于r w a 和w a 问题已经有一些很好的算法，在w d m 全光网络中r w a 和 w a 问题也有很好的研究【2 ，4 ，8 ，2 4 ，8 3 如果路是给定的，也就是说，图g 中的路 的集合p 给定，那么问题就恰好变为波长分配( w a ) 问题其中的路染色问题是被 证明是a l p - 困难的，而且在树网络结构，环网络结构，以及树环网络结构中均得到 了很好的研究【2 3 ，2 4 ，3 2 ，8 3 ，9 0 1 3 2 波长转换 很多人研究了波长转换器的应用问题，以求得对波长分配问题的更有效的解 决f 3 ，3 6 ，5 5 ，5 9 ，8 1 在顶点 处放置一个波长转换器可以使得任一经过此顶点的路 在经过顶点口时改变路的颜色( 也就改变了波长) 在一些顶点上使用波长转换器可 以有效的降低在通讯中对波长条数的要求，使得其满足下面的自然阻塞度约束t 即 使应用波长转换器，我们仍然需要一个带宽的下界，此下界即为所有的通讯路经过 某条边时的最大数量，并且使其满足所有的通讯请求由于波长转换器在网络中是 一个很贵重的仪器，所以在使用过程中我们希望在不超过带宽要求的情况侠，用最 少的转换器能够得到最好的通讯效果见与此，w i l f o n g 和w i n k l e r 9 4 】定义了网 络中顶点的有效性，如果在有效的顶点上放置转换器，能够使得通讯路经过转换后 得到的结果能够不超过他的阻塞度约束他们证明了即使是在一个平面图中，找到 这样的一个最小的有效顶点集合的难度也是n p - 完全的 1 3 3 请求排序问题 在全光网络中请求排序问题是将一系列通讯请求给出一个排序，其中每个通讯 4 山东大学博士学位论文 请求均为一个源一目标点对和一个延迟时间每个请求的延迟需要建立一个虚拟的 圈使得邻近的的时间间隔等同于请求的延迟时间，在这种框架下，每个请求不再分 为更短的单元来传播另外的，建立这样的一个通讯也是一个昂贵的过程；需要建 立从源顶点到目标顶点的通路，对应他需要一个波长和一个起始时间正因于此， 如果通讯没有延迟是最好的选择，也就是说，请求的取代是不允许的 这样的一个网络我们用一个连通图g = ( ke ) 来表示一个请求是由图g 中 的一个顶点对来表示，并且每个请求的完成时间是它的起始时间和延迟之和给定 g 中请求的一个排序，要求合理的分配起始时间和通讯路使得任意两个请求不能在 同一时间用同样的波长通过同一条边，而且分配的波长数量不能超过某个界限( 因 为要受到带宽的约束) ，则一个排序的跨度就是所有的请求完成的最终时间，我们的 目标是使得总的时间跨度最小来完成所有请求的排序如果请求的时间延迟和波长 约束都是任意的，那么请求排序问题已经证明是p 困难的【2 4 】 1 3 4 环负载问题 为了研究在w d m 网络中的路由和波长分配问题。一些研究者 8 8 ，8 9 ，9 4 】给出 了如下限制对于环上的任一连杆，通过其上的通路被称为连杆的负载，而所有连 杆上的最大负载被称为环负载给定环上的一系列通讯请求，环负载问题即为找到 这些通讯请求的一系列通路，使得环负载最小，如果环上所有的连杆为有向的，那 么环负载问题是可以在多项式时间内解决的 9 4 】 如果所有的请求是加权的，则加权环负载问题即为找到所有通讯请求的通路 使得任一连杆上的最大负载( 定义为所有经过此连杆的通路的权重之和) 最小而 加权无向环负载问题( 也就是说，每条连杆允许双向通信) 已经有人作出了一些研 究【8 8 ，8 9 】，并且给出了一个多项式时间近似方案【5 6 】而加权有向环负载问题也 在【4 ，6 7 】中得到了研究，并且也给出了一个多项式时间近似方案 1 4 一些优化问题的相关结论 由w d m 网络在通信方面的应用，例如，波长分配和波长转换方面我们可以研 究由此产生的一些图论问题和时序安排问题对于r w a 问题，j l g a n l e y 和j p c o h o o n 将研究重点放在一个圈网络中。由此提出了最小化超图嵌入圈的最大阻 塞度( m c h e c ) 问题 5 1 】 5 山东大学博士学位论文 嵌入问题在矩形路由网络中【2 6 ，3 3 ，3 4 ，5 8 ，8 6 】，以及在圈和护城河路由网络 中【7 ，3 0 ，6 5 ，9 3 】都是很有挑战性的问题m c h e c 问题已被g a n l e y 和c 0 h o o n 证 明是皿完备的，并给出了一个3 - 近似算法，并且可在0 ( ( n m ) 1 ) 判定阻塞度为 k 的嵌入存不存在然后不同近似比的算法纷纷产生，g o n z a l e z 【9 1 】，l e e 和h o 【8 5 】， g u 和w a n g 【7 7 】用不同的方法提出了2 - 近似算法，最近x i a o t i ed e n g 和c u o j u n l if 2 0 】证明了此问题存在一个p t a s 算法 图嵌入圈的模型是为了满足无圈网络中的一系列仅有两个节点构成的通信请 求，每个请求仅含有一个源顶点和一个目标顶点显然m c g e c 问题是m c h e c 问 题的一个特殊情况，只是通信请求只含有两个节点m c g e c 问题已经解决，其最 优解可以在多项式时间内得到f r a n k ，n i s h i z e k i ，s a i t o ，s u z u k i 和t a r d o s 【2 6 ，2 s 加权的m c g e c 问题的p t a s 算法已经被s h r i j v e r ，s e y m o u r 和w i n l d e rf 8 8 ，8 9 ， 以及k h a u n a 【5 6 】证明也是存在的 而对于有向版本的加权m c h e c 问题，我们将在第三章中证明是a f p - 完备的， 并给出一个常数近似比的贪婪算法 1 5 有向图的一些相关问题 在本论文中我们还讨论了关于竞赛图和无向图定向的一些问题 竞赛图图的研究已经有很长的历史了，我们提出了强竞赛图的一个新的强连通 性质，并且应用此性质给出了m o o n 定理的一个简单的证明 无向图的最小直径定向问题在二部图和多部图中也得到了广泛的讨论，其结论 在运输流量| 可题和网络问题中得到了广泛的应用我们应用已经得到的结论给出一 类特殊图s p l i t 完全图的最小直径问题的一个结论 1 5 1 强连通图的强连通性 竞赛图是一个完全有向图，它是一类特殊的局部准完全有向图研究局部准完全 有向图是很有意义的，不只是因为这种图是竞赛图的拓展类，而且因为他们固有的支 撑子图的性质这种图已经被很精深地研究，例如在，f 1 6 ，2 9 ，4 2 ，4 3 ，4 4 ，4 5 ，4 8 ，4 9 ，5 2 】 竞赛图含有很多有用的性质一个m 部图( 或者多部) 竞赛图即为一个m 都完 全图的定向得来，一个竞赛图可以看作是一个m 部完全图，只是其中每一部仅含有 一个顶点多部竞赛图的性质已被很多人讨论。例如，b a n g - j e n s e n 和g u t i n 4 1 ，5 0 ， 6 山东大学博士学位论文 v o l k m a n n 【9 2 】，以及y e o1 9 5 ，并且产生了很多著名的结论，m o o n 【s 4 ，b o n d y 【6 】， g u t i n1 3 9 1 ，g u o 和v o l k m a n n 3 7 】，y e of 9 6 ，以及g o d d a r d 和o e l l e r m a n nk 嘲 应用局部准完全有向图的相关性质以及一个关键定义一无圈排序，我们可以证 明强竞赛图的一个新的强连通性而且还可以得到强竞赛图点泛圈( m o o nt h e o - r e m 碑】) 的一个简单证明。 1 5 2 最小直径定向问题 图的定向问题在图论和组合最优化方面已经得到了很精深的研究。并且有着很 长的研究历史 1 9 2 9 年，r o b b i n s 证明了定向问题和连通性之间的等价关系，一个无向图存在 一个强连通定向当且仅当此无向图是2 _ 边连通的从此以后，多种多样的有关定向 问题的研究被引入和发展，包括一些研究描述特殊连通性的定向问题，以及一些寻找 拓扑性质的定向问题，例如，紧密度( 图g 存在一个定向使得定向后的直径和g 的 直径相同，则称g 是紧密的) ，度数约束，以及无圈性例如n a s h - w f f i i a m s 7 0 1 ( 1 9 6 0 ) 的一个经典结论描述了图的珏边连通定向问题c h u n g ，g a r e y 和t a r j a n 【1 3 ( 1 9 8 5 ) 则给出了一个线性时问的算法来检验一个图是否存在一个强连通定向并且如果存在 的话能够找到一个这样的定向 一 1 9 7 8 年，c h v a t a l 和t h o m a s s e n 提出了一个叫定向壹径的问题t 给定一个图 g ，寻找g 的一个强连通定向使得定向后的图直径最小他们证明，对于一般的图， 此问题是x p - 困难的而后，f o m i n ，m a t a m a l a 和r a p a p o r t 2 5 ( 2 0 0 4 ) 证明了即使 限制在一系列弦图中时此问题依然是 一困难的，并且给出了一些可近似和不可 近似的结果 b o e s h 和t i n d e l l 1 2 证明了如果二部图两部分顶点个数相同时，它的定向的最 小直径至少为3 p l e s n i k 【7 2 和s o l t e si s 4 分别得出了对于普通的二部图最小直径定 向的结果而后g u t i n 【3 8 ，4 0 ，以及k o h 和t a n 【5 7 】又分别研究了当n 3 时，n 一 部图的最小直径定向问题 s p l i t 图是由一个团和一个独立集组成。s p l i t 完全图是一类特殊的s p l i t 图，可 以将s p l i t 完全图看作一个特殊的多部图，那么应用上述多部图的定向的结论我们可 以给出s p l i t 完全图的一个最小直径的定向 7 第2 章超图嵌人问题的一些p t a s 算法 2 1 引言 在第一章中，我们介绍了路由与波长分配问题：给定一系列通信请求，每个请 求分配一条通路，并且使用最少的颜色来找到这些通路的一个有效着色 已经有一些有效的算法来解决r w a 问题，而且在这些研究中每个请求仅仅含 有两个顶点，一个源顶点和一个目标顶点但是实际网络中每个请求通常都是多播 请求，也就要求每个请求含有网络中两个以上的顶点这些请求可以看作是一个超 图，在解决此问题时要求找到网络中的一个路由算法来连接每条超边的所有顶点 在本章中将研究环网络中的r w a 问题，将超图的每条超边以一条路的形式嵌入 到圈中。并且使得最大阻塞度( 经过圈中任一边的路的数量) 最小此问题称为最小 化超图嵌入圈的最大阻塞度( m c h e c ) 问题，它是由j l g a n l e y 和j p c o h o o n 【5 1 】 在1 9 9 7 年提出的，并且给出了常数阻塞度时的一个多项式时间算法 超图嵌入圈的问题在很多方面都是很有挑战性的问题，例如在计算机网络，通 信，并行计算，电子自动化方面【2 6 ，3 3 ，3 4 ，5 8 ，8 6 】在电子路由方面主要是研究圈和 护城河路由网络【7 ，3 0 ，6 5 ，9 3 】解决问题的焦点在于找到一个路由算法使得网络中 边上的最大阻塞度最小 本章内容如下安排在2 2 节中介绍m c h e c 问题的来源，并且介绍此问题的 一些相关算法 在2 3 节中，我们给出m c h e c 问题的一些记号和定义，并且简化邓小铁和李 国君的算法给出m c h e c 问题的p t a s 证明 由于超边数目的不同，嵌入过程分为两种情况进行显然，如果超边的数量为 一个常数，问题是很简单的当超边的数目上限为c l o g n 时，应用穷举的方法可以 得到此问题的p t a s 证明；当超边数目足够大m c l o g n ，而且最优解和超边数日 相关( 大于或者等于c m ，c 0 为常数) ；对于一个普通的超图将上述两种方法结合 l i ，m a 和w a n g 解决字符串问题的方法 6 0 】可得到m c h e c 问题的一个p t a s 结 果 在2 4 节中，我们首次提出超图嵌入环圈( m c h e r c ) 的问题，并且给出了 m c h e t r 问题和m c h e r c 问题的p t a s 算法，同时我们给出了这两个问题的 8 山东大学博士学位论文 x p - 完备性证明 在2 5 节中，对本章进行了一些总结 2 2m c h e c 问题的来源以及一些相关的结论 商品流问题在【7 1 ，7 5 】中已经被很好地研究，而后a f r a n k 解决了在网格中的 商品流问题，且在 2 8 】中提出了边不交路问题在实际生活中，发点和收点并一定 能够被一系列边不交路来连接，因此图的嵌入问题就应运而生其中的一种特殊情 况，图嵌入圈( m c g e c ) 问题就是将通讯问题限定在一个环网络中，而且每个通讯请 求由网络中的一对节点组成；一个发点和一个收点m c g e c 问题有很多有效的算 法，它的最优解已经被f r a n k ，n i s h i z e k i ，s a i t o ，s u z u k i 和t a r d o s 【2 6 ，2 8 】证明可以在 多项式时间内找到而加权m c g e c 问题已经被s h r i j v e r ，s e y m o u r ，w i n l d e r 8 8 ，8 9 ， 和k h a n n a 【5 6 】证明存在一个p i ：a s 算法 在提出m c h e c 问题的同时，g a n l e y 和c o h o o n 5 1 1 证明了此问题是弘完 备的并且提出了一个3 - 近似算法将阻塞度的上限定为k ，此算法可以确定m c h e c 问题的解是否存在，如果存在的话，则可以在0 ( ( 彻；) 1 ) 内找到一个合理的嵌入 而后又产生了一系列不同近似比的算法，g o n z a l e z 【9 1 】，l e e 和h o 【8 5 】用不同的方 法给出了近似比为2 的近似算法g u 和w a n g 【7 7 用一个重新嵌入的方法给出了 一个1 8 - 近似算法 最近，邓小铁和李国君 2 0 1 证明了m c h e c 问题存在一个p t a s 算法他们应 用了很不同于前人的方法，对于m c h e c 问题的一种特殊情况应用组合的方法就可 得其解；而对于一般情况的m c h e c 问题，对它的整数规划应用随机和反随机过程 来找到最优解的一个放松解在下一节中，我们用不同于邓和李的方法证明此p t a s 算法的一些关键引理来简化m c h e c 问题的p t a s 算法 2 3m c h e c 问题的一个p t a s 算法 首先我们给出m c h e c 问题一些定义和必需的记号圈c 为一个顶点集为 v = 俐1 i n ) ，边集为e g = e d l i n ) 的无向图g = ( k 上踣) ，其中每 条边岛连接顶点i 和顶点i + 1 ，i = 1 ，2 ，n + 1 被看作1 ) 不失一般性，假 设顶点 1 ，2 ，n ) 以顺时针方向排列在圈上为确定起见，将边e d = ( i ， + 1 ) 记 9 山东大学博士学位论文 做i 令日= ( u 五k ) 为一个建立在v = 俐l i 咒) 上的超图，其超边集合为 e h = h t ， 。) 其中每条超边吩由y 中两个或两个以上的元素构成 超边( 1 j m ) 在圈g 中的连通路为连接妨中所有顶点的最小路弓，即 为，b 的两个端点属于那么对每个吻我们可得i 吗1 个这样的连通路超边的连 通路的集合就组成了超图日在圈e 中的一个嵌入给定一个嵌入，阻塞度为圈上任 一连杆上经过此连杆的连通路的数目给定一个圈和定义在圈上的超图，m c h e c 问题就是找到此超图在圈上的嵌入使得任一连杆上的最大阻塞度最小 不失一般性，假设h j 的k j 个顶点0 p ，i 挈，i ( ) 1 ( 1 j m ) 以顺时针排列 在圈c 上那么吩的顶点将圈c 分为如个段：p # ，t 挈】，p 乒， 箩】，瞄盟l ，i 器】， 瞄lk j ，i # 】，而且此向个段同样以顺时针排列在圈口上令掣表示圈c 中顶点睁) 】 到顶点p 鼢1 ( 磅+ 1 被看作1 ) 的一段，也就是说， 酵= e g ，k ，) ，e 。，) l 由超边吻分割得到的在同一段掣中的连杆称作与超边吩关联的故超边b 将互b 的连杆分为乜个关联组，而且任意两条连杆为关联的当且仅当它们在吻的 同一关联组中 b = i # ，i 箩，i 兽) 的一个掣一嵌入为心的一条起点为锟终点为i p 的 连通路( 以顺时针方向) ，也就是说的这样一条连通路由圈g 的所有边除去掣中 的边得到，记为品一砰显然对于任一超边b = i p ，i 箩，i 兽) ，j = 1 ，2 ，m ， 圈c 中存在个这种不同的连通路而超图的一个嵌入由所有的m 条超边在圈中 的嵌入组成，故m c h e c 问题的所有这种可行解的总数为后1 如k 令= ( z - ，z 。，) 为一个m 维向量，其中巧确定了超边的一个嵌入， 即为q = e b 一碟，0 ：1s 岛，1 j m 我们称由z 确定的超图h 的嵌入为 $ 一嵌入显然z 为m c h e c 问题的一个可行解假设岛为圈g 的任一边，我们用 e ( z ) 来表示由争嵌入得到的日上的阻塞度，那么m c h e c 问题可以表示为如下优 化问题 i = 1 ，2 ，n ( 2 1 ) g a n l e y 和c o h o o n 通过n m t s ( n u m e r i c a lm a t c h i n gw i t ht a r g e ts u m s ) 问题 3 1 1 1 0 z 筋、j n 茁 m 龟 ，、【 山东大学博士学位论文 到m c h e c 问题的等价问题c c m c p ( c y c l ec o v e rp r o b l e mb yt h em 1 1 l t i p l ec h o i c e p a t h s ) 问题的多项式转换得到了m c h e c 问题的a l p - 完备性 定理1 卢玎m c h e c 问题为p 一完备的 我们感兴趣的就是要找到m c h e c 问题的一个p t a s 算法，也就是说，要找到 一个算法a 使得它的近似比满足 r a ( i , e ) = 器1 + e 其中，a p x ( i ) 是由算法a 得到的结果，o p t ( i ) 为最优解，并且满足当e 为一个 常数时，算法为多项式复杂度 2 3 1 算法的思想 窑记做阻塞度为c 哪的最优解对任一e l 五b ，z ( 1 ) 嵌入表示e lgz ? 的嵌 入，j = 1 ，2 ，m ，也就是说，霉( ) - 嵌入不经过边自下面我们证明e i ( z ( 。) ) s2 c 哪， 岛e c 我们称这个算法为同边去除算法，算法分两个步骤 1 对于任一1 j m ，令巧= 如一e 。o 。) 表示吩的一个嵌入，其中磷表示e l 在圈中的一段，1 sk h 岛，1 z 儿 2 输出z ( 。) 嵌入 引理1 对于任一边白e c ，同边去除算法的近似比为2 ，也就是说，岛( z ( d ) 2 e 哪 证t假定最优解c 耐由最优嵌入争嵌入得到那么弘嵌入中经过边e l 的连 通路的条数最多为g 叩t 令蜀表示嵌入经过边e l 超边集合显然可得l 场i g 叫由 同边去除算法得到的嵌入和铲嵌入之间的差异在于竭中的超边的嵌入，所以将弘 嵌入转换到同边去除算法得到的嵌入只需要改变凰中的超边的嵌入，这个转换使 得圈中除了e l 外的所有的边的阻塞度最大增加了c 。故圈中除了e z 外其他边的阻 塞度最大为2 c 哪，且e l 的阻塞度为o ，也就是说，对于任一e e v ，白( z ( ) ) 2 哪_ 我们同时考虑k 条边岛，( 可以是圈中任意k 条边的组合) 来推广这 个近似比为2 的算法回顾与超边的一个相关组，假定为掣，假定z 和c 哪均 山东大学博士学位论文 为已知的令忍“。，“表示所有七条边岛。，属于同一个超边相关组的超 边的下标集合，也就是说， 尼。 2 = f 1 j m 1 3 1 ，2 ，向) 使得白，霹 对于任一y - 嵌入，我们用! ，i 皿，蛳来表示下标在尼。，t 。，。中的超边的嵌入 令阢。氟，缸= 1 ，2 ，m 卜一尼，忍i 我们的主要思想是讨论两个下标集合。 最“。，“和阢。m ，i 。，分别找到他们的 近似解，而后得到m c h e c 问题的一个多项式近似方案下面的一个引理对于解决 下标在矾“。，也中的超边的嵌入很关键 引理2 筘哪i 阢，m ，“i 冬缸哪且i 尼。，瓴a i m 一后哪 证 假设j 阢，缸，“由矾。，如，“的定义可知e 4 。，不属于超边 吻的同一段，故存在一条边e 4 。使得，也就是说，的阻塞度在最优嵌 入中增加1 由于( z ) 哪，所以每条边e 4 。使得集合仉， i 2 ，o 。最多增加c 唧 考虑所有的k 条边8 小，可得i 阢，妇，i 七6 唧由r 。j 。，缸的定义可知 i 忍。出，。j m 一七锄t _ 下面证明，存在这样的一个下标集合i l ，如，4 ，对于所有下标在忍。，玩，“中 的超边，使得i 风一。一嵌入为z 的一个很好的近似嵌入而对于下标在职，t 2 ，讳 中的超边，应用整数规划、随机取整和反随机方案同样可得一个近似解【6 8 ，8 7 】 2 3 2 嵌人下标在尼。，i 。， r 中的超边 为了完成下标在忍。如， 中的超边的嵌入，邓和李应用来源于字符串问题【6 0 】 线性放松的方法来得到一个茹n k m _ 一嵌入 首先介绍一些定义和记号令。i 风| 恕，。为下标在冠。，屯，中的超边的最优嵌 入则对于任一常数r ，我们需要找到合适的r 个下标 i 1 ，t 2 ，0 得到需要的近 似z i m 。* 一嵌入下面的引理对于忍。氲 中超边的嵌入很关键这个引理表 明了一定存在这样一个下标集合i 1 ， 2 ，0 使得z ( 1 ) l 风。如* 一嵌入为z i 鱼。恕。的 一个很好的近似解 1 2 山东大学博士学位论文 引理3 对于任一常数r ，2 r c ；哪r ，则存在一条边满足茹l 巩中超边的连通路 错过边的条数超过c 叫步类似地，令皿，i j 表示嵌入经过 岛，) 的超边集合 那么i x i 如l 。i 表示z l 风。中经过边的连通路的条数可得i 甄。, i 2 i 0 , u c ( 1 0 9 凡) 令z = ( z l ，茁2 ，) 为下标在， 2 ， 山东大学博士学位论文 中超边的一个嵌入( 不一定最优) ，弘嵌入为我们要逼近的，其中巧= 正b 一磷，i 0 如，为超边a j 的嵌入，j = 1 ，2 ， 假设i m l ，m 2 ，m r 礼为圈c 中r 个不同边的下标令q 。，。，。表示一个超边的下标集合，如果超边的下标j 属于 这个集合当且仅当础至少包含e 。，e 。，e 。中的一个元素，也就是说。 。 n 丌u ，m ，。= 1 歹钍j 础n e m 。e m ，e ，m ) 叮， 其中，= b e 一础为z 的第j 个元素如此可知，f k 。，。，主要依赖于z 和 r 令一为下标在阢。，2 中超边的任嵌入，且仅当j f k 。，。，。时候， = 巧，也就是说，下标在f 2 仇，。，。中的超边在两个嵌入和一中有相同的连 通路，其中蟛( 巧) 表示( 茹) 中第j 条超边吩，歹= 1 ，2 ，牡的嵌入下面的引理 表明了任意一个一为z 的一个很好的近似解 引理4 令z = ( z l ，勘，钆) 为下标在阢“。 中超边的一个嵌入体一定最 优j ，对于任一固定的下标1 r f l , 1 u ，存在r i 个下标他，m 3 ，协满足弓= q ， 仅当j k ，m ，l r 时则对于任一边e i 点b ，可得 e ( 一) 一q ( z ) ；e ( z ) 证。z = z 1 ，z 2 ，z 。) 为下标在阢。船一。“中超边的一个嵌入，其中； 五治一硝为超边的嵌入令n = q 。，。为如上定义碍到的超边下标集合 我们要找到符合要求的r 1 个下标首先随意选取圈e 的一条边e 1 = ( 1 ，2 ) = ( m l ，m 1 + 1 ) 令c 为z 得到的边的最大阻塞度则在嵌入z 中，最多有( t 一c ) 的 嵌入满足，e 1 础即为最多有cb 的嵌入使得e l 岳础令三为满足e l 础 的超边集合( 最多为c ) 用如下算法可得剩余的r i 个下标 1 选定圈c 的任一边。 2 如果存在超过c r 条超边b 珥满足e 。础，则选定m h ，令日r = 珥一 j l e 。e j u ) 3 如果i 珥i 大于c r ，转步骤l ，否则结束 1 4 山东大学博士学位论文 因为每一步均使得j 研i 至少减小c r ，珥最多c ，故