（计算机应用技术专业论文）halin图上的k条不相交路径问题.pdf

论文题目：h a l i n 图上的k 条不相交路径问题 专业：计算机应用技术 硕士生：夏春汛 指导教师：娄定俊教授 摘要 给定一个图g = ( v ，e ) ，以及图g 中的k 对顶点( “。，h ) ， ：，v 2 ) ，( 心，) ， 所谓的k 条不相交路径问题就是，找到图g 中的k 条不相交路径分别连接这k 对 顶点，即路径丑连接甜l 和v l ，路径丑连接蚝和k ，并且这k 条路径必须互 不相交。k 条不相交路径问题总共有四种不同的版本，即考虑图g 是有向图或无 向图的情形，以及考虑路径是顶点不相交的或边不相交的，从而可以得到四种不 同的组合情形，该问题在布线问题、v l s i 设计等方面有着广泛的应用。 普通图上的k 条不相交路径问题目前还没有很好的研究成果，而h a l i n 图最 先是作为极小3 连通平面图被研究的，它本身有着很多良好的连通性质。本文提 出一个线性时间算法来解决h a l i n 图上的k 条顶点不相交路径问题，整个算法主 要基于c o r n u e j o l s 、n a d d e f 和p u l l e y b l a n k 所提出来的扇收缩方法。算法的大 概思想是，先对h a l i n 图的特征树进行后序遍历，在遍历的过程中不断对h a l i n 图上的扇区进行收缩处理，同时保存大量有用的信息。当后序遍历完特征树后， 算法利用刚才所保存的有效信息，来寻找问题所要求的那k 条顶点不相交路径。 k 条不相交路径问题的难点在于，这k 条不相交路径所有可能的情形是非常 复杂的。由于h a l i n 图进行扇收缩后仍然是h a l i n 图，但是图的规模却比原来变 小了，因此只要在扇收缩的过程中保存足够多的信息，就可以运用类似动态规划 的思想来解决这个问题。算法通过不断地对h a l i n 图进行扇收缩处理，直到最后 判定题目是否有解。有解的话再根据扇收缩过程中保存的信息，来还原出那k 条 顶点不相交路径，从而完成对h a l i n 图上k 条不相交路径问题的解决。 关键词：h a l i n 图，扇收缩，不相交路径 t i t l e ： g a j o r ： n a m e ： s u p e r v i s o r ： t h ek - d i s j o i n tp a t h sp r o b l e mo nh a l i ng r a p h s c o m p u t e ra p p l i c a t i o nt e c h n o l o g y x i ac h u n x u n p r o f l o ud i n 西u n a b s t r a c t g i v e na g r a p hg = ，e ) a n dkd i s j o i n tv e r t e xp a i r s ( ，v 1 ) ，似2 ，v 2 ) ，( ，v k ) o fg t h ek - d i s j o i n tp a t h sp r o b l e mi s ，t of i n do u tkp a t h si ngs u c ht h a tp a t h 置 c o n n e c t s u a a n dh ，p a t h 丘c o n n e c t su ka n dk ，a n dt h e s ekp a t h sm u s tb e d i s j o i n t d i s j o i n tm a ym e a nv e r t e x - d i s j o i n to re d g e d i s j o i n t , a n dt h eg r a p hgm a yb e d i r e c t e do ru n d i r e c t e d ，s ot h ekd i s j o i n tp a t h sp r o b l e mh a sf o u rv e r s i o n sa sw ec a l ls e e t h ek d i s jo i n tp a t h sp r o b l e mh a sa p p l i c a t i o ni n w i r er o u t i n g ”，w h i c hi sa l li m p o r t a n t p r o c e s so ft h el a y o u td e s i g no fv l s i s t h ek - d i s j o i n tp a t h sp r o b l e mi sd i f f i c u l ti nt h eg e n e r as i t u a t i o n t h eh a l i n g r a p h sa r ef i r s ts t u d i e db yr h a l i na sm i n i m a l l y3 - c o n n e c t e dp l a n a rg r a p h ，a n dt h e i r f e a t u r e sa b o u tc o n n e c t i v i t ya r es ob e a u t i f u lt h a tal i n e a ra l g o r i t h mi sp r e s e n t e di nt h i s p a p e rt os o l v et h ek - d i s j o i n tp a t h sp r o b l e mo nh a l i ng r a p h s t h ea l g o r i t h mi sb a s e d o nt h e “f a nc o n t r a c t i n g ”m e t h o dw h i c hi sf i r s ts t u d i e db yc o m u d j o l s ，n a d d e fa n d p u l l e y b l a n k t h eb a s e i d e aa b o u tt h ea l g o r i t h mi st h a t ，f i r s tap o s to r d e rw a l ki s p e r f o r m e do nt h ec h a r a c t e r i s t i ct r e eo ft h eh a l i ng r a p h ，t h e nu s e “f a nc o n t r a c t i n g m e t h o dt od e a lw i t he v e r yf a no ft h eh a l i ng r a p hb e t w e e nt h ew a l k w h i l ec o n t r a c t i n g t h ef a n , ap l e n t yo fu s e f u li n f o r m a t i o nm u s tb es t o r e d a f t e rt h ew a l k ，t h ea l g o r i t h m u s e st h ei n f o r m a t i o nj u s ts t o r e dt of i n dt h a tkv e r t e x - d i s j o i n tp a t h s t h ed i f f i c u l t ya b o u tk - d i s j o i n tp a t h sp r o b l e mi st h a t ，a l lt h ep o s s i b l es i t u a t i o n s a b o u tt h e s ek - d i s jo i n tp a t h sm a yb ev e r yc o m p l i c a t e d ah a l mg r a p hi ss t i l lah a l i n g r a p ha f t e rp e r f o r m i n g f a nc o n t r a c t i n g o ni t , b u tt h eo r d e ro f t h eg r a p hb e c o m e sa l i t t l es m a l l e r ，s oi ft h ea l g o r i t h mc a l ls t o r ee n o b g hi n f o r m a t i o nw h i l ep e r f o r m i n g “f a n c o n t r a c t i n g ，t h e nt h ed y n a m i cp r o g r a m m m gm e t h o dc a i lb ee a s i l yu s e dt od e a lw i t h t h i sp r o b l e m t h ea l g o r i t h mk e e p sp e r f o r m i n g “f a nc o n t r a c t i n g u n t i li tc a nd e c i d e w h e t h e rt h ep r o b l e mi ss o l v a b l eo rn o t i ft h ep r o b l e mi ss o l v a b l e ，t h ea l g o r i t h mu s e s t h eu s e f u li n f o r m a t i o ns t o r e db e f o r et of i n dt h ekv e r t e x - d i s j o i n tp a t h s k e yw o r d s ：h a l i ng r a p h ，f a nc o n t r a c t i n g ，d i s j o i n tp a t h s 论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究工作所取得的成果。除文中已经注明引用的内容外，本论 文不包含任何其他个人或集体已经发表或撰写过的作品成果。对本文 的研究作出重要贡献的个人和集体，均已在文中以明确方式标明。本 人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：趸查! 銎 e l期：兰! f ! 生! 盛兰旦 学位论文使用授权声明 本人完全了解中山大学有关保留、使用学位论文的规定，即：学 校有权保留学位论文并向国家主管部门或其指定机构送交论文的电 子版和纸质版，有权将学位论文用于非赢利目的的少量复制并允许论 文进入学校图书馆、院系资料室被查阅，有权将学位论文的内容编入 有关数据库进行检索，可以采用复印、缩印或其他方法保存学位论文。 学位论文作者签名：夏奄汛 日期：2 0io 年6 月2 日 导师签名：j 錾定馁 日期：钧幻年6月了 日 第1 章绪论 第1 章绪论 1 1 研究背景 1 1 1图论简介 图论( g r a p ht h e o r y ) 是数学的一个分支，它以图作为研究对象。图论中的 图指的是由若干给定的点以及连接两点的线所构成的图形，这种图形通常用来描 述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个 事物问具有这种关系。 图论本身是应用数学的一部份，因此，历史上图论曾经被多位数学家各自独 立地研究过。关于图论的文字记载最早出现在欧拉1 7 3 6 年的论文中，他所考虑 的原始问题有着很强的实际背景，即著名的柯尼斯堡七桥问题。 芦? 譬孑外 d 1 莎3 莎 三匿 图1 - 1 柯尼斯堡七桥问题 1 8 5 9 年，英国数学家哈密顿发明了一种游戏：用一个规则的实心十二面体， 它的2 0 个顶点标出世界著名的2 0 个城市，要求游戏者找一条沿着各边通过每个 顶点刚好一次的封闭回路，即“绕行世界 。用图论的语言来说，游戏的目的是 在十二面体的图中找出一个生成圈，这个问题后来就叫做哈密顿问题。由于运筹 学、计算机科学和编码理论中的很多问题都可以转化为哈密顿问题，因此图论逐 渐引起人们广泛的注意。而h a l i n 图就是种有着很多特殊性质的哈密顿图，其 最初是作为极小3 一连通平面图被研究的 1 。b o n d y 2 证明了每个h a l i n 图h 是 1 - h a m il t o n 的，即h 是哈密顿图，并且删除h 中任意一个顶点后仍然是一个哈 第1 章绪论 密顿图。 图论在实际生活中的广泛应用，极大地促进了它自身的发展。2 0 世纪4 0 年 代至6 0 年代，拟阵理论、超图理论、极图理论，以及代数图论、拓扑图论等都 有很大的发展。而h a l i n 图由于其自身良好的性质，也不断有学者把自己的精力 投入对它的研究中，从而推动了整个图论领域的发展。下面介绍论文使用到的图 论基本概念以及记号。 1 1 2 图论基本概念 图( g r a p h ) 是指有序的三元组( v ，e ，) ，其中v 非空称为顶点集( v e r t e x s e t ) ，e 称为边集( e d g es e t ) ，而杪是e 到v x v 的映射，称为关联函数( i n c i d e n t f u n c t i o n ) ，l f ，描述了边租顶点对之间的关系。若边e 的两个端点为u 和v ，则 有y ( p ) = ( “，v ) ：在图g 中，如果边集e 中的边都没有方向，则图g 称为无向图 ( u n d i r e c t e dg r a p h ) ：如果边集e 中所有边都设有方向，则图g 称为有向图 ( d i r e c t e dg r a p h ) 。本文若未明确指出是“有向图”时，所涉及的图都是指无 向图。 本文采用广为使用的图的简单表示法，即g = ( v ，e ) ，并用y ( g ) 和e ( g ) 分 别表示图g 的顶点集和边集。图的顶点数，即集合v 中元素的个数矿( g ) i 称为图 _ 的阶( o r d e r ) 。类似地，用旧( g ) i 或者表示图g 的边数。无向图中的边用无 序对( u ，v ) 来表示，若不需标明顶点，可用小写字母e 直接表示边( p e ) 。 不论图g 是否有向，序对中的点都称为边的两个端点( e n d v e r t i c e s ) 。边与它 的两端点称为关联的( i n c i d e n t ) ，同一边上的两端点或者与同一顶点相关联的 两边称为相邻的( a d j a c e n t ) 。 一个图称为有限图，如果它的顶点集和边集都有限。本论文只研究有限图， 故术语“图 一词总是指“有限图”。只有一个顶点的图称为平凡图，其它所有 的图都称为非平凡图。 两端点重合的边称为环( 1 0 0 p ) 。具有相同端点的两条边称为平行边 ( p a r a l l e le d g e s ) 或者重边( m u l t i - e d g e s ) 。对于有向图，序对中的端点必须 2 第1 章绪论 对应相同才能称为平行边；在无向图中，只需两序对中的端点相同就可称为平行 边。不存在环或者平行边的图称为简单图( s i m p l eg r a p h ) 。无向图g 中，与顶 点u 相关联的边的数目称为顶点u 的度( d e g r e e ) ，记为d ( u ) 或者如 ) 。 令形= v o q m 乞气咋，其中巳e ( g ) ，l f 后，v ，v ( g ) ，o k 且q 与 v f - l 和v f 相关联，则称w 是图g 的一条道路( w a l k ) 。其中k 为长度，顶点v o 和唯 分别称为w 的起点和终点，而v l ，v 2 ，一l 称为内部顶点( i n t e r n a lv e r t i c e s ) 。 如果道路w 的边互不相同，则w 称为迹( t r a i l ) 。如果道路w 的顶点互不相同， 则w 称为路( p a t h ) 。起点和终点重合的路叫做圈( c y c l e ) 。图g 的哈密顿圈是 指包含g 的每个顶点的圈。 若图g 的两个顶点u 、v 之间存在道路，则称u 和v 连通( c o n n e c t e d ) 。若 图g 的任意两个顶点均连通，则称g 是连通图( c o n n e c t e dg r a p h ) 。不含圈的连 通图称为树( t r e e ) 。 若在图g 中任意删去k - 1 个顶点，图g 仍是连通图，则称g 是k 一点连通图 ( k - v e r t e x - c o n n e c t e dg r a p h ) ，其中k 为大于1 的整数。类似地，若在图g 中 任意删去k - 1 条边，图g 还是连通的，则称g 是k - 边连通图( k - e d g e c o n n e c t e d g r a p h ) 。对v ( g ) 的子集s 和s ，用【s ，s t 】表示一个端点在s 中，另一个端点在s 中的所有边的集合。所谓图g 的边割( e d g ec u t ) 是指形为【s ，司的e ( g ) 的子集， 满足s 彩和i = 矿( g ) s a 。边数为k 的边割称为k 边割。 每一对不同的顶点都有一条边相连的简单图称为完全图( c o m p l e t eg r a p h ) 。 n 个顶点的完全图记为e 。 1 1 3h a l i n 图的相关定义 在平面上嵌入一棵树t ，t 的每个内部顶点的度数至少为3 并且t 至少有一 个内部顶点。作一个圈c 连接t 的所有叶子顶点，t 的所有叶子顶点组成圈c 上 的所有顶点。这样得到的平面图就称为h a l i n 图 1 ，树t 称为h a l i n 图的特征 树( c h a r a c t e r i s t i ct r e e ) ，圈c 称为h a l i n 图的伴随圈( a c c o m p a n y i n gc y c l e ) 。 第1 章绪论 以上的描述就是h a l i n 在其1 9 7 1 年关于极小n 一连通图的论文中对h a l i n 图的定 义。 h a l i n 图还有很多类似的等价定义，这里列出另外一种稍微不同的定义，使 读者对h a l i n 图有更深入的了解。对于一个3 一连通平面图g ( v ，e ，f ) ，如果其某 一面五边界上所有顶点( 记为圪) 的度数均为3 ，把该边界上所有的边都删去，结 果得到一棵非悬挂点度数至少为3 的树t ，则称图g 为h a l i n 图。圪中的点称为 图g 的外点，其余的点称为图g 的内点，t 称为图g 的特征树。设面五的边界上 有n 个点，则石的边界是圈g ，称为图g 的伴随圈。这个定义来自于文献 3 。 图1 - 2h a l i n 图 1 1 4 h a l i n 图上的“扇收缩”方法 对于研究h a l i n 图的学者来说，所谓的“扇收缩”方法 4 是再熟悉不过的。 假设h = t u c 是一个h a l i n 图，其中t 是图h 的特征树，c 是图h 的伴随圈。若t 是 一个星，即一个单独的结点v 分别连接到其它n 个结点，则称h 为一个轮( w h e e l ) ， 它是h a l i n 图的一种平凡情形，称v 为轮的中心。现在假设t 至少包含2 个非叶子结 点，记w 是t 的一个非叶子结点，并且w 只与t 的另外一个非叶子结点相连接，则把 t e 与w 相连接的叶子结点所构成的集合记为c ( w ) ，也就是伴随圈c 上与w 相连接结 点的一个连续序列。我们称由 w ) u c ( w ) 所得到的子图为h 的一个扇( f a n ) ，同 时称w 为扇的中心。 4 第1 章。绪论 图1 - 3h a l i n 图中的扇( 虚线所围区域即是) 假设f 是h a l i n 图日= r u c 的一个扇，则把图h 由收缩扇f 成为一个伪点v 。所 得到的图记为h x f ，也就是说，顶点集v ( h x d = v f ) u ( 日) y ( f ) ) ，边集 e ( h x f ) 的定义如下：1 ) 删除那些两个端点都位于f 中的边；2 ) 那些两个端点 都位于日一f 中的边维持原状；3 ) 对于那些一个端点位于日一f 中、另一个端 点位于f 中的边，则把其位于日一，中的端点与所得到的伪点1 ，。相连接起来即可。 这种扇收缩方法最初是由c o r n u 6 j o l s 、n a d d e f 和p u l l e y b l a n k 在文献 4 中提出来 的，他们用这种方法给出了h a l i n 图上旅行商问题的一个线性时间算法。扇收缩 方法为h a l i n 图上的相关研究引进了一个强有力的工具，本文所提出的算法主要 也是基于这种扇收缩方法的思想的，不过实际操作过程中可能存在着很多不同之 处，后面第3 章会详细介绍整个算法的具体流程。 本文中其它没有另外定义的名词或符号，均可参考 5 中的相关定义。 1 2h a li n 图的研究现状 1 2 1 h a l i n 图相关性质 s y s t o 和p r o s k u r o w s k i 在文献 6 中对h a l i n 图的相关性质做了详细的介 绍，包括h a l i n 图的连通性，h a l i n 图的环结构以及h a l i n 图的平面嵌入等。下 面给出该文中关于h a l i n 图几个比较重要的性质：1 ) 每个h a l i n 图都是3 一连通 的，这是h a l i n 图最基本的性质之，也是h a l i n 当初最开始研究h a l i n 图时就 发现的；2 ) 一个3 一连通的平面图是h a l i n 图，当且仅当它有一个m a c l a n e 圈基 ( m a c l a n ec y c l eb a s e s ) c 。并且该圈基上的每个圈都有条外边；3 ) 删除h a l i n 第1 章绪论 图的任意一条边或一个顶点，所得到的图是2 连通的；4 ) h a l i n 图h 的任意一 条边都属于图h 的一个哈密顿圈。 上面提到文献 2 证明了每个h a l i n 图h 是1 - h a m i l t o n 的，即h 是哈密顿图， 并且删除h 中任意一个顶点后还得到一个哈密顿图。在文献 7 中，娄定俊对文 献 2 中的结果作了进一步的推广，证明了每个h a l i n 图h 是哈密顿连通的，即 g 中任意两个顶点u 和v 之间存在一条哈密顿路径，并且从对这个定理的证明中 得出一个推论，即假设h 是h a l i n 图，那么h 中的任一边必定包含在h 的一个哈 密顿圈中，也就是上面提到的性质4 ) 。这个推论不能进一步推广，即存在h a l i n 图中的两条边不包含在任何哈密顿圈中。 文献 8 中提到一些有关h a l i n 图路分解( p a t hd e c o m p o s i t i o n ) 的研究成 果。设g 为一个图，v 为g 中的一个顶点。若v 的度数为奇数，则称v 为g 的奇 顶点，否则称为g 的偶顶点。我们记图g 的奇顶点数为o d d ( g ) 。对于一个图g ， 如果能把g 的边集e ( g ) 分解成k 个互不相交的子集互，岛，邑的并集，且使得 每个e ( 1 f 七) 都为一条路径，则称图g 有一个k 一路分解。g 的路分解数，记为 万( g ) ，是把g 的边集分解成路径的最小数目。关于图的路分解有以下猜想，图 的路分解猜想( p d c ) ：对任何的简单图g ，有厅( g ) f y ( g ) 2 。作者在该文中 证明了：若h 是一个h a l i n 图，则z ( g ) = o d d ( g ) 。 文献 9 也是一篇关于h a l i n 图路分解方面非常详细的论文，f o m i n 和 t h i l i k o s 主要证明了可以在线性时间内计算h a l i n 图h 的路宽，并且h 的路宽 近似于其特征树t 的路宽的3 倍。作者的这种近似算法是基于树的“r e s p e c t f u l o r d e r i n g 组合方法而得到的。树宽( t r e e w i d t h ) 和路宽( p a t h w i d t h ) 的概念 最初是由r o b e r t s o n 和s e y m o u r 在文献 1 0 和文献 1 1 中引进的，之后这两个概 念经常出现在h a l i n 图的相关研究中。设x e ( g ) ，让8 ( x ) 表示与x 和e ( g ) x 中的边都关联的那些点的集合，记口= ( q ，p ：，e m ) 为e ( g ) 的一个排序，对 i l ，2 ，掰) 记e ，= u | ，。砖 。定义m g ，仃) = m a ) 【l 艿( 巨) i ，ie 1 ，掰) 以及g 的线 宽( 1 i n e a rw i d t h ) 为伽( g ) = m i n 1 w ( g ，仃) ：盯是e ( g ) 的- - 个排序) ，则有下面的 6 第1 章绪论 结论：设h 是一个h a l i n 图，其特征树记为t ，则有m ( r ) 1 w ( h ) 3 1 w ( t ) ，以 及存在线性时间算法使得对任意的h a l i n 图有东一l t w ( h ) 3 k ，其中k 是某个 整数。 1 2 2 h a l i n 图上的染色问题 具有重要理论意义和实用价值的图染色问题，是图论的主要研究内容之一。 由于实际和理论上的需要，新的染色概念在各种重要的文献中不断涌现出来。平 面图的染色问题是图论的起源之一，同时也是染色理论中最重要的研究内容。关 于图染色的基本问题之一就是确定图g 的色数，即能够对图g 进行k 着色的最小 k 值，图的色数有很多不同的版本，比如点色数、边色数、全色数等等。 图染色问题是图论领域的经典问题之一，其中最基本的问题就是确定一个图 的色数。文献 1 2 非常详细地研究了h a l i n 图上的色数问题。对无环图g ( v ，e ) 用k 种颜色将v ( e ，或v ue ) 的所有元素染色，使相邻( 或相关) 元素染色均不相 同的方法，称为g 的k 一正常( 点) ( 边，或全) 染色法，而z ( g ) = m i n k i g 的 k 一正常染色法 ，z f ( g ) = m i n k l g 的k 一正常边染色法 ，z r ( g ) = m i n k i g 的 k - 正常全染色法) 分别称为g 的( 点) 色数、边色数和全色数。关于h a l i n 图的 色数，作者得到以下定理：若图g 是h a l i n 图，则有 z ( g ) = 妻霎暑2 兰以m o d 2 的。关于h a l i n 图的边色数，作者得到如下定理： 若图g 是一个h a l i n 图并1 5 a ( g ) 4 ，则有z ( g ) = 。更进一步地，作者得到： 若图g 是一个h a l i n 图并e t a ( g ) = 3 ，则有z ( g ) = 3 。关于简单图的点边全染色， 1 9 6 5 年b e h z a r d 1 3 和v i z i n g 1 4 分别独立地提出了著名的全着色猜想( t h e t o t a lc o l o u r i n gc o n j e c t u r e ，简记为t c c ) ：对于简单图g 有所( g ) ( g ) + 2 。 而对于h a l i n 图的全色数，作者得到如下定理：若图g 是一个h a l i n 图并且 a ( g ) 5 ，则有筋( g ) = a + i 。更进一步地，文献 1 5 3 对a ( g ) = 4 时h a l i n 图的 全色数做出解答，即证明了若图g 是一个h a l i n 图并a ( g ) = 4 ，则有所( g ) = 5 ， 第1 章绪论 从而推广了文献 1 2 中有关h a l i n 图的全色数的结论。最后，文献 1 6 给出了 ( g ) = 3 时h a l i n 图的全色数，即：若图g 是h a l i n 图并g a ( g ) = 3 ，则有 4 筋( g ) 5 。 上文研究了h a l i n 图上最常见的点色数、边色数和全色数问题，之后其他学 者开始研究h a l i n 图上比较复杂的色数问题，比如文献 1 7 研究了h a l i n 图上的 圈着色问题。假设图g 为平面图，使在同一个t 面( t k ) 上的顶点均染为互不 相同颜色的方法称为图g 的k 一圈着色；使平面图g 得到k 一圈着色的最少颜色数 就称为k 一圈着色数，记为航( g ) ，着色方法记为口。由四色猜想很自然可以得 到筋( g ) 4 。平面图的圈着色这个概念最早是由o r e 和p l u m m e r 在1 9 6 8 年提出 来的 1 8 。关于3 一连通平面图，p l u m m e t 和t o f t 在1 9 8 7 年给出猜想 1 9 ：当七3 时，有筋( g ) k + 2 。文献 1 7 对3 一连通图中的h a l i n 图确定了其相应的圈色数， 符合h u m m e r 和t o f t 所提出的3 一连通平面图上的猜想，其主要结论有以下两个 定理。( 定理1 ) 当尼= d ( f o ) 并且图g 是h a l i n 图时，有下面结论成立：1 ) 若图 g 是轮，则航( g ) = k + l ；2 ) 当图g 不是轮时，若图g 是中心h a l i n 图，则 胛) 芝：嚣6 3 ) 当图g 不是轮也不是中, 6 , h a l i n 图时有胛m o ( 定 理2 ) 当k d ( 厶) 并且图g 是h a l i n 图时，有下面结论成立：1 ) 若图g 是轮， ( g ) l a t x ) - f l ( 其中a ( x ) 表示那些一个端点位于x 中、另一个端点位于 v x 的边集，因此a ( x ) 肯定不包含环) 。然后作者证明了问题“边集f 何时是g 可分的”等价于2 条边不相交路径问题，其中顶点对( 墨，) ( 1 i k ) 对应于 f = p l ，e i ) 中那些哑边( d u m m ye d g e s ) 的端点。m e n g e r 定理给出了由平行边 所组成的边集f 是g 可分的充分必要条件，但在一般情形下暂时还没有相关的结 论，作者在该文中解决了两种比较简单的特殊情形：i ) f f f = 2 ；2 ) f 中的每条 边都是由连接3 个给定顶点中的2 个而得到的。另外的，作者所用的方法还可以 推广到2 条顶点不相交路径问题的情形，但是却不能推广到有向图的情形。 上述提到的各种解决2 条不相交路径问题的算法都是基于串行算法的，文献 3 1 则从并行算法的角度来考虑这个问题，给出了解决2 条不相交路径问题的一 个处理器高效的并行算法。如果给定的图g 是平面图，则作者给出一个快速的并 行( n c ) 算法来解决该问题，算法需要c ( n ，n ) 个处理器，每个处理器的处理时 间为o ( 1 0 9 n ) ；如果给定的图g 是非平面图，则作者先找出图g 的一个库拉托夫 斯基同胚( k u r a t o w s k ih o m e o m o r p h ，即墨3 或墨的同态子图) ，然后利用这个 同胚作为一个“开关( s w i t c h ) ”来解决上述问题，算法需要o ( 甩2 ) 个处理器， 每个处理器的处理时间仍然为o ( 1 0 9 n 1 。为了使并行化操作成为可能，作者从算 法方面给出一个相关的结构，即他们所提出来的“p q - 图 ( p q - g r a p h ) ，同时证 明了所谓的p q 一图定理( t h ep q g r a p ht h e o r e m ) 。 t h o l e y 3 2 在对无向图上的2 条顶点不相交路径问题做了更深入的研究后， 提出一个近乎线性时间的算法来解决该问题。该算法把之前最优算法的时间复杂 度从o ( n 2 ) 减少到o ( n + m a ( m ，z ) ) ，其中口表示阿克曼函数( a c k e r m a n n f u n c t i o n ) 的逆 3 3 。通过对大家所熟知的归约算法进行些许修改后，作者对上 述结果进行推广，从而给出一个时间复杂度为o ( n l o g n + m a ( m ，2 ) ) 的算法，来解 决无向图上的2 条边不相交路径问题。更进一步地，利用文献 3 4 中提到的时间 复杂度为o ( m l 0 9 2 + 胁n + n l 0 9 3 力) 的归约方法，作者把他们的算法推广到解决有 1 4 第1 章绪论 向无环图上2 条不相交路径问题的情形，新算法的时间复杂度为 o ( m l 0 9 2 圳。n + n l 0 9 3 ，z ) 。 1 3 2 k 条不相交路径问题 l y n c h 3 5 给出了数理逻辑陈述( s t a t e m e n t si nm a t h e m a tic a ll o g ic ) 和 互连网络问题( i n t e r c o n n e c t i o np r o b l e m s ) 之间互相转换的一种简单方法。作 者证明了，假如存在一个切实可行的方法来解决互连网络问题，那么对于该问题 的数理逻辑陈述，就一定存在一个切实可行的证明方法。互连网络问题的图论模 型如下，给定一个图g = ( v ，e ) 和顶点集v 的个不相交子集墨，s ：，s 。，要 求找出顶点集。v 的不相交连通子集互，疋，疋，使得对于任意的i 有s 互， 1 i 七。作者在该文中证明了，给定一条关于命题演算的公式仃，则存在一个 图使得其上的互连网络问题是可解的，当且仅当盯是可满足的。这个结论与电路 板上的布线问题密切相关，作者给出上述结论的一个构造性证明，在证明的过程 中特别强调了布线问题的困难。从互连网络问题的图论模型可以看出，互连网络 问题与不相交路径问题有着密切的联系。通过这篇文献中的结论，我们知道了平 面图上的k 条不相交路径问题是n p 完全的。 从上一篇文献中我们知道，对于k 条不相交路径问题，假如k 不是固定的( 即 k 也是该问题输入的一部分，从而是变动的) ，则k 条不相交路径问题是n p 完全 的，甚至在平面图上的情形也是如此。但是对于任意固定的k ( 即k 不是输入的 一部分) ，有向平面图上的k 条不相交路径问题可以在多项式时间内得到解决 3 6 。在 3 6 中，s c h r i j v e r 的目标并不是追求运行时间的最优化，但他确实证 明该问题可以在多项式时间内得到解决。s c h r i j v e r 的方法主要基于自由群 ( f r e eg r o u p s ) 的上同调( c o h o m o l o g y ) 理论，也就是利用代数工具来研究这 个问题。为了解决k 条不相交路径问题，s c h r i j v e r 的方法中用到由k 个生成元 所组成的自由群，这其实就是对文献 3 7 中所提到的无向图上基于同伦 ( h o m o t o p y ) 的方法的推广。从某个角度来说，上同调与同调是对偶的，同样可 以在有向图上进行相关的定义，即使该图没有嵌入到某个曲面上。作者先对给定 第1 章绪论 图的对偶平面图进行扩展，然后在扩展后的图上运用上同调理论进行处理，因为 直接对给定图进行同调处理看起来还不足以解决该问题。在该文中，作者只是利 用自由群和同调理论来构建一个框架，这样可以更容易地说清楚其所提出来的方 法，其实也可以不用这些数学工具，那样的话整个方法可能会显得复杂一些。 s c h r i j v e r 解决了有向平面图上的k 条不相交路径问题，而r o b e r t s o n 和 s e y m o u r 则把结论推广到无向图的情形( 对平面性不做要求) 3 8 ，他们给出了 一个时i - j 复杂度为o ( i v ( g ) i ) 的算法，来解决无向图上的k 条不相交路径问题。 可惜的是，他们所提出来的算法在实际上是不可行的，因为其中所涉及的常数因 子大到实际无法接受，不过他们所用的方法仍具有非常重要的理论意义。作者所 用的方法主要是基于“图m i n o r 理论的相关内容，为了解决问题他们提出了一 个核心概念：f o l i o ( 具体定义参考该文献) 。首先作者给出一个时间复杂度为 0 0 y ( g ) 1 3 ) 的算法来解决如下问题( f o l i op r o b l e m ) ：给定一个图g ，对于任意 固定的6 ，彳0 ，假设顶点集z v ( g ) 并且l z l f ，问图g 限制在顶点集z 上的 万一加f f d 是什么。然后作者详细说明了如何通过解决f o l i o 问题来解决无向图上 的k 条不相交路径问题，并且算法的时间复杂度仍然是o ( j y ( g ) l ) 。这是第一篇 解决普通图上k 条不相交路径问题的文献，推翻了之前学者们对该问题困难程度 的种种猜测，因此该文献对后来的研究具有非常重要的意义。 上面提到r o b e r t s o n 和s e y m o u r 给出无向图上k 条不相交路径问题的第一个 多项式时间算法，而他们的递归算法中的一个步骤就是，在树宽有限( 即树宽不 超过某个常数) 的情况下找到图g 的一个树分解。假如能够找到这样的树分解， 则可以运用动态规划的思想来解决该问题，也就是找到图g 上的k 条不相交路径。 有关树分解的第一个算法是由r o b e r t s o n 和s e y m o u r 提出来的 1 1 ，他们所提出 来的算法时间复杂度为o ( ，2 厂( ) ，之后有很多学者坚持不懈地对树分解算法进行 改进，直到最后b o d l a e n d e r 给出了一个线性时间算法来求解图g 的树宽不超过 k ( k 是给定的常数) 的树分解 3 9 。通过对b o d l a e n d e r 所提出的线性时间算法 进行部分调整，p e r k o v i 6 和r e e d 4 0 提出一个新的算法来求解图g 的树宽不超 过k ( k 是给定的常数) 的树分解。更进一步地，他们的新算法具有如下附加的 1 6 第1 章绪论 特征：假如图g 的树宽大于k ，则新算法会返回图g 的一个树宽大于k 的子图g 以及g 的一个宽度不大于2 k 的树分解。利用改进后的树分解算法以及动态规划 的思想，p e r k o v i 6 和r e e d 给出一个时间复杂度为0 0 v ( g ) 1 2 ) 的算法，来解决通 常意义下的k 条不相交路径问题。 由于文献 4 0 所采用的算法框架和文献 3 8 所采用的算法框架基本类似，因 此文献 4 0 所提出的算法只是具有理论上的意义，也就是说，到目前为止还没有 切实可行的算法来解决通常意义下的k 条不相交路径问题。为了绕开这道“难以 逾越”的坎，有的学者开始转向寻找k 条不相交路径问题的近似算法，例如文献 4 1 3 。通过利用网络流和对集理论中的相关算法，n g u y e n 4 1 顺利解决了经过某 个给定顶点的不相交路径问题，再利用c h e k u r i 和k h a n n a 所提出来的技巧 4 2 3 ， n g u y e n 给出无向图上k 条不相交路径问题的一个o ( 聆) 近似算法。关于k 条不 相交路径问题的第一个近似算法是一个贪心算法( g r e e d ya l g o r i t h m ) ，它是由 k l e i n b e r g 4 3 所提出来的，可以同时处理有向图和无向图的情形，并且该近似 算法的近似比( a p p r o x i m a t i o nr a t i o ) 为朋。文献 4 1 中所提出来的近似算 法并不是一个贪心算法，不过该算法的近似比相对以前的算法有了一定的提高， 因此能够帮助我们更好地理解k 条不相交路径问题。该算法主要基于c h e k u r i 和k h a n n a 4 2 所提出来的方法，首先利用贪心策略寻找给定顶点对之间的最短 路，要求这些最短路的长度小于l ( 1 是预先选择好的参数) ，然后把这些最短路 从图g 中删去。当剩下的给定顶点对之间不再存在所要求的最短路时，对于每个 剩下的给定顶点v ，作者分别解决经过顶点v 的不相交路径问题，然后从中挑出 最优的结果，这就是n g u y e n 所提出来的近似算法的主要思想。 1 3 3 其它相关研究 如果将k 条不相交路径问题的某些条件稍微放宽一点，比如不相交路径问题 考虑的是给定的k 对顶点之间的路径，若考虑任意k 对顶点之间的不相交路径问 题，那么这就是图的“l i n k a g e ”问题，它是与k 条不相交路径问题密切相关的。 假设_ ，s 2 ，s k 是k 个正整数，一个图g 称为( q ，s 2 ，s k ) 一l i n k e d ，若：图g 至 第1 章绪论 少包含：。s j 个顶点，并且对任意满足晦j = 墨( 1 f j ) 的k 个不相交顶点集 s ，是，s k ，有图g 包含顶点不相交的连通子图互，e ，e 使得ss 矿( e ) 。该 问题q = 屯= = & = 2 的情形已经被广泛地研究过。一个( 2 ，2 ，2 ) 一l i n k e d 的图称为k j i n k e d ，也就是说，对任意2 k 个不同的顶点五，m ，吃，儿，故，以， 存在图中的k 条不相交路径墨，昱，e 使得鼻连接五和m (