（运筹学与控制论专业论文）κ匹配的子正交匹配分解与路染色问题.pdf

原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进 行研究所取得的成果。除文中已经注明引用的内容外，本论文不包含任何 其他个人或集体已经发表或撰写过的科研成果。对本文的研究作出重要贡 献的个人和集体，均已在文中以明确方式标明。本声明的法律责任由本人 承担。 论文作者签名：二阻 日 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学校保 留或向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅 和借阅：本人授权山东大学可以将本学位论文的全部或部分内容编入有关 数据库进行检索，可以采用影印、缩印或其他复制手段保存论文和汇编本 学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：蝉导师签名为垂盗舀 期：2 11 皇：y 山东大学硕士学位论文 卜匹配的子正交匹配分解与路染色问题 朱建明 ( 山东大学数学与系统科学学院，济南2 5 0 1 0 0 ) 摘要 本文主要可分为两个部分，第一部分所讨论的问题是，t 一匹配的予正交匹 配分解及一些近似算法，包括第一章到第四章：第二部分是路染色问题，包括 第五章。 在第一部分中将主要讨论j i 一匹配的子正交匹配分解问题，这个问题可以描 述如下： 给定一个最大度为七的无向图g ，和g 上的一个k - - 匹配m 将边集划分 成 巨，e 2 ，局) ，满足每一个置都是g 的一个匹配且最多包含m 中的一条边， 目标是求这样的一个最小划分，即求，的最小值。 对于这个问题，主要有以下结果： 定理2 3 匹配m 是简单二部图g 的一个完美匹配，则g 存在关于们的正 交匹配分解。 定理2 4 算法i 能够在多项式时鲥内给出简单二部图g 关于完美匹配m 的一个正交匹配分解。 定理3 3 算法2 是最多用2 i 一1 次匹配的多项式近似算法。 定理4 1 算法4 能够在多项式时间内给出问题( p ) 的一个用2 k 一1 次匹配 的解。 在这一部分中，本文的主要结构是如下： 第一章；引言部分简单介绍问题的应用背景，及一些基本概念，还有目前的一 些主要结果和算法。 第二章：将证明给定的图g 是简单二部图，匹配m 是图g 一个完美匹配，则 图g 存在关于匹配肘的正交匹配分解。并给出边集的一个关于吖的 正交匹配分解算法。 山东大学硕士学位论文 第三章：将舍弃二部图的限制，讨论给定一个最大度为女的简单图g ，是g 的一个完美匹配，寻找关于m 的最小子正交匹配分解。在这一章中 将给出这个问题的一个最多需要2 七一1 次匹配的多项式近似算法，并 且还将说明这种算法思想的下界是i 三七i ，最后再给出种特殊情况 下的i 兰j 次匹配的近似算法。 第四章：在这一章中将给出( - p ) 问题的一个最多需要2 七一1 次匹配的近似算 法，并且讨论这种贪心算法的下界。 在第二部分中，将主要讨论光网络中的路染色问题。路染色问题可以描述如 下： 在一个连通图g 上，对于给定的一组路的集合j p ，给每一条路分配一种颜色 使得任意有公共边的两条路分配不同的颜色，目标是求最小颜色数。 在光网络中，连通图g 的拓扑结构是特殊的，根据光网络的常用拓扑结构， 得到抽象的图g 是树、环和树环等，本文就主要讨论在这三种特殊图g 上的路 染色问题。 对于树、环和树环上的路染色问题，有下面的主要结果： 定理5 2 星型图上的路染色问题是a ，尸困难的。 定理5 5 对于双向星型图上有向路染色，可以在多项式时间内用上种颜色 对pj - f 常着色。( l 是最大负载) 引理5 2 一条顺向路和一条逆向路可以染同一种颜色。 定理5 7 可以根据一个无向环上路染色问题的近似算法得到个双向环 上的有向路染色问题的算法，且保持近似比不变。 在这一部分中，本文的结构如下： 第一节： 引言部分主要介绍路染色问题在光网络通信波分复用中的作用，和一 些研究成果及算法。 第二节：讨论树型网络和双树型网络上的路染色问题，并引入星型网络上的一 些概念和结果。 第三节：讨论环型网络和双向环型网络上的路染色问题，并证明无向环上路染 2 山东大学硕士学位论文 色问题的近似算法可以用于解决双向环上的有向路染色问韪，且保持 近似比不变。 第四节： 介绍有关树环型网络上的路染色问题，及一些主要结果。 关键词 子正交匹配分解，多项式时间算法，路染色，光网络 山东大学硕士学位论文 s u bo r t h o g o n a lm 队t c n gd e c o m p o s i t i o no f 眉也a t c h i n ga n dp a t hc o l o r i n g j i a n m i n gz h u ( d e p a r t m e n to f m a t h e m a t i c s ，s h a n d o n gu n i v e r s i t y , j i n a n 2 5 0 1 0 0 ) a b s t r a c t i nt h i sp a p e r , i tc a l lb ed i v i d e di n t ot w op a r t s t h ef i r s tp a r t ，f r o mc h a p t e r1t o c h a p t e r4 ，i sm a i n l ya b o u ts u bo r t h o g o n a lm a t c h i n g rd e c o m p o s i t i o no f k - m a t c h i n ga n d i t sa p p r o x i m a t i o na l g o r i t h m s i n c l u d i n gc h a p t e r5 t h es e c o n dp a r td i s c u s s e sp a t h c o l o r i n gp r o b l e m i nt h ef i r s tp a r t , w em a i n l yd i s c u s st h ep r o b l e mo fs u bo r t h o g o n a lm a t c h i n g d e c o m p o s i t i o no f k - m a t c h i n g t h i sp r o b l e mc a r lb ed e s c r i b e d a s ： l e tgb ea l lu n d i r e c t e dg r a p hw i t hm a x i m u md e g r e ek ( k 3 ) ，a n dmi sa k - m a t c h i n gi ng ap a r t i t i o n e l ，e 2 ，e j o f e w h e r ee v e d r 最i sam a t c h i n gi ng a n di n c l u d e sa tm o s to n ee d g eo fmi sc a l l e das u bo n h o g o n a lm a t c h i n g d e c o m p o s i t i o no f m f i n dt h e ：s m a l l e s tp a r t i t i o no f e t h a ti st of i n dt h em i n i m u m t ot h i sp r o b l e m ，t h ef o l l o w i n g sa l eo u rm a i nr e s u l t s ： t h e o r e m2 3l e tmb eap e r f e c tm a t c h i n go fas i m p l eb i p a r t i t eg r a p hg t h e n t h e r ee x i s t sa l lo r t h o g o n a lm a t c h i n gd e c o m p o s i t i o no f m t h e o r e m ：2 4a l g o r i t h m1c a ng i v ea l lo r t h o g o n a lm a t c h i n gd e c o m p o s i t i o no f p e r f e c tm a t c h i n gm i ns i m p l eb i p a r t i t eg r a p hgi np o l y n o m i a lt i m e t h e o r e m3 , 3a l g o r i t h m2i sa p o l y n o m i a la p p r o x i m a t i o na l g o r i t h mo fu s i n ga t m o s t2 k - im a t c h i n g s t h e o r e m4 1a l g o r i t h m4c a ns o l v et h ep r o b l e m ( 即b yu s i n ga tm o s t2 k - 1 m a t c h i n g si np o l y n o m i a lt i m e t h eo u t l i n eo f t h i sp a r ti sa sb l o w ： c h a p t e r1 ：a p p l i c a t i o no f t h i sp r o b l e mi si n t r o d u c e di nt h ep r e f a c e i n c l u d es o m e 4 山东大学硕士学位论文 c o n c e p t i o n s ，r e s u l t sa n da l g o r i t h m s c h a p t e r2 ：l e tm b ea p e r f e c tm a t c h i n g o fas i m p l eb i p a r t i t eg r a p hg t h e nw ew i l l p r o v et h a tt h e r ee x i s t s8 , 1 1o r t h o g o n a lm a t c h i n gd e c o m p o s i t i o no fm a tt h e s a m et i m eap o l y n o m i a la l g o r i t h mw i l lb eg i v e n c h a p t e r3 ：w i t h o u tt h er e s t r i c to fb i p a r t i t e 。l e tm b eap e r f e c tm a t c h i n go fa s i m p l e g r a p hg f i n dt h em i n i m u ms u bo r t h o g o n a lm a t c h i n gd e c o m p o s i t i o no fm i ng i nt h i sc h a p t e r , ap o l y n o m i a la p p r o x i m a t i o na l g o r i t h mo fu s i n ga tm o s t 2 缸t sw i l - b eg i v e n ，肌a wb o u n d o f t h i sc o n c 印“s 阱3 k a tl a s t ，w ew i l lg i v eap o l y n o m i a l 印p r o x i m a t i o na l g o r i t h mo f u s i n ga tm o s t 医小n 鼬t n g s i nac 。n 她沁阳咖c e c h a p t e r4 ：i nt h i sc h a p t e r , ap o l y n o m i a la p p r o x i m a t i o na l g o r i t h mo fu s i n ga tm o s t 2 k - lm a t c h i n g sw i l lb eg i v e nf o rp r o b l e m ( 竹a n dt h eb o u n do fg r e e d y a l g o r i t h mw i l lb ed i s c u s s e d i nt h es e c o n dp a r t ，w ew i l lm a i n l yd i s c u s st h ep r o b l e mo fp a t hc o l o r i n g t h i s p r o b l e mc a l lb ed e s c r i b e da s - l e tgb eac o n n e c t e dg r a p ha n dpi sas e to f p a t h s a s s i g nc o l o r st oe a c hp a t h ，s o t h a ta n yt w op a t h ss h a r i n ga ne d g ea r ea s s i g n e dd i f f e r e n tc o l o r s a n dt h eg o a l i st o m i n i m i z e 也en u m b e ro f c o l o r su s e d i na l l o p t i c a ln e t w o r k s t h et o p o l o g i e sa r es p e c i a l ，s u c ha st r e e s ，r i n ga n dt r e eo f r i n g s i nt h i sp a p e r ，w em a i n l yd i s c u s st h ep r o b l e mo fp a t h c o l o r i n gi n t h e s e t o p o l o g i e s t h em a i nr e s u l t sa b o u tp a t hc o l o r i n gi nt r e e ，r i n ga n dt r e eo f f i n g sa r ea sf o l l o 懈： t h e o r e m5 2p a t hc o l o r i n gi nas t a ri sa t - c o m p l e t e t h e o r e m 【5 5d i r e c t e dp a t hc o l o r i n gi nab i d i r e c t e ds t a rc a nb es o l v e di n p o l y n o m i a lt i m eu s i n glk i n d so fc o l o r s i st h em a x i m u ml o a do na r c si nt h eg r a p h a b o u tt h eg i v e ns e to f p a t h s ) 一l e m m a5 2i nb i d i r e c t e dr i n g ，ap a t hi nt h ec l o c k w i s ed i r e c t i o na n dap a t hi nt h e c o u n t e r c l o c k w i s ed i r e c t i o nc a l lb ea s s i g n e dt h es a m ec o l o r 山东大学硕士学位论文 t h e o r e m5 7a c c o r d i n gt oa l la p p r o x i m a t i o na l g o r i t h mo fp a t hc o l o r i n gi na l l u n d i r e c t e dr i n g ，w ec a nd e s i g na na p p r o x i m a t i o na l g o r i t h mo fd i r e c t e d p a t hc o l o r i n g i nf lb i d i r e c t e dr i n g ，w h i c hk e e p st h ea p p r o x i m a t i o nr a t i ou n c h a n g e d t h eo u t l i n eo f t h i sp a r ti sa sb l o w ： s e c t i o n 1 ：1 1 1 ep r e f a c em a i n l yf o c u s e so nt h ee f f e c to fp a t hc o l o r i n gi naw d m o p t i c a ln e t w o r k s ，s o m er e s e a r c hr e s u l t sa n da l g o r i t h m s e c t i o n2 ：u n d i r e c t e da n dd i r e c t e dp a t hc o l o r i n gi nt r e en e t w o r ka n db i d i r e c t e dt r e e n e t w o r k sa r ed i s c u s s e di nt h i ss e c t i o n a n da l s oi n t r o d u c et h ec o n c e p to f s t a rn e t w o r k s e c t i o n3 ：u n d i r e c t e da n dd i r e c t e dp a t hc o l o r i n gi nr i n gn e t w o r ka n db i d i r e c t e dr i n g n e t w o r ka r ed i s c u s s e di nt h i ss e c t i o n a c c o r d i n gt oa l la p p r o x i m a t i o n a l g o r i t h mo fp a t hc o l o r i n g0 1 1 【a l l u n d i r e c t e dr i n g ，w ec a l l i d e s i g na n a p p r o x i m a t i o na l g o r i t h mo fd i r e c t e dp a t h c o l o r i n go nab i d i r e c t e dr i n g ， w h i c hk e e p st h e 印p r o x i m a t i o nr a t i ou n c h a n g e d s e c t i o n4 ：u n d i r e c t e da n dd i r e c t e dp a t hc o l o r i n gi nt r e eo f r i n g sa n db i d i r e c t e dt r e eo f r i n g sa r ed i s c u s s e di nt h i ss e c t i o n k e y w o r d s s u bo r t h o g o n a lm a t c h i n gd e c o m p o s i t i o n ，a p p r o x i m a t i o na l g o r i t h m ， p a t hc o l o r i n g ，o p t i c a ln e t w o r k s 6 山东大学硕士学位论文 第一章引言 随着网络的广泛应用，信息的传输质量和安全至关重要，所以需要对传输的 过程进行抽样监测，以确保发射点和接收点处理信号的质量，由于检测设备的有 限性，可能每次只能监测所需监测传输线路中的一条。可以抽象出下面问题： ( p ) ：给定一个图g 和图上的一个匹配吖，已知图g 的最大度和匹配的 边数都是k ，要求每次从g 中取出一个匹配，满足取出的匹配最多只能包含给定 匹配m 中的一条边，目标是求用最少次数的匹配将图g 的边取完。 这个问题，也涉及到一些带有限制条件的时间表安排问题 9 】，而且在排序 问题上也有一定的应用。 定义1 1 边集的一个子集肘称为g 的一个匹配，如果吖中的任意两条 边( 不包括端点重合的边) 都不相邻，即没有公共端点。m 中任意一条边的两个 端点称为在m 上被匹配。顶点v 被叫做一饱和的，如果它在上被匹配。对 于一个匹配m ，如果g 中的每个顶点都是吖一饱和的，则称匹配m 是g 的一个 完美匹配。 定义1 2 子正交匹配分解是指对于g 的一个匹配吖，将边集划分成 。，岛，- ，目 ，满足每一个e 都是个匹配且最多包含m 中的一条边。这样一 个划分就叫做g 关于肘的子正交匹配分解。 定义1 3 最小子正交匹配分解是指g 关于m 的予正交匹配分解中集合个 数最少的那个分解。 则( p ) 问题可以用子正交匹配分解的定义来叙述： 给定一个图g 和图上的匹配m 已知图g 的最大度和匹配m 的边数都是k ， 目标就是求g 关于匹配m 的最小子正交匹配分解。 首先不考虑匹配掰的情况下，对g 进行边染色，同一种染色的边集中可能 有若干条m 中的边，则可以再分配另外的颜色使得村中的边不染同种染色，这 样问题就转化为图的边染色问题。 于是，当g 是简单图，利用v i z i n g 定理【1 ，2 】，很容易得到一个用2 1 次匹配 的多项式算法。 山东太学硕：i ：学位论文 g 是重图时，在 3 】中，n i s h i z e k i 和k a s h i w a g i 对于重图上的边染色问题给出 了最多需要l 1 1 z7 ( g ) + o 8 j 种颜色染色的近似算法，由此我们可以得出问题( ，) 的一个1 1 1 z ( g ) + o 8 j + k 1 次匹配的近似算法。 问题( 户) 在二部图上讨论时，应用c m a g i m m i s 和k a k l a r n a n i s 4 的方法， 容易得到需要昙_ j 次匹配的近似算法。 上 下面给出正交匹配的定义， 定义1 4 称边集e 的划分 e 。，e 2 ，日 是g 的一个关于的正交匹配分 解，如果对每一个是g 的匹配并且包含且仪包含中的一条边。 山东大学硕士学位论文 第二章二部图上匹配的子正交匹配分解 在这一章中将证明当给定二部图的匹配是一个完美匹配时，存在这个匹配的 正交匹配分解。并给出边集的一个关于m 的正交匹配分解算法。 第一节简单二部图上匹配的子正交匹配分解 当给定的匹配m 不是二部图的完美匹配时。就不一定存在m 的正交匹配分 解了，例如： 给定二部图g = ( x i ，；d ，x = 缸l 。虬，“，“。 ， m “2 虬z 4 y = v i ，也，b ，v ； ，k = 3 ，如右图，给定匹配 m = ( m ，v 。) ，( “：，v ：) ，( “，b ) ，对于这个图，就不存在关于 村的正交匹配分解。首先，对于边( “，v 。) 可以得到的满足 不包含m 中其它两条边的最大匹配边数是3 ，又= 1 2 ，如果存在正交匹配分 解，则另外两个中必有一个边数大于4 ，则它一定不是图g 的匹配。 所以就要寻找肘的最小子正交匹配分解。 定义2 1 图g 是加正则的，如果g 的每个顶点的度都是k 。 定义2 2 无环图g ( 具有同一端点的边称为环) 的一个卜边着色是把e ( g ) 划分成k 个子集e = 1 , 2 ，- 一，k ) 的一种分法，e 中的每条边均着以i 色。封i 果g 中任意相邻两边均着以不同颜色，即e 均是g 中的匹配，则称这卜边着色是正 常的，若g 有正常的扣边着色，则称g 为卜边可着色的图。 定义2 。3 边色数z ( g ) 是g 的所有卜边可着色中最小的k ，若( g ) = k ， 则称g 为卜边色的。用a ( g ) 表示g 的最大度，显然有z ( g ) ( g ) 。占( g ) 为g 的最小度。 9 山东大学硕士学位论文 对于二部图，设是图g 的最大度，则有下面的定理， 定理2 1 1 】若g 是二部图，则z ( g ) = a 。 所以对于无约束二部图的边染色问题，一定可以a 种颜色着色。对此，许多 快速有效的算法都已经提出【5 ，6 ，7 ，8 】。 二部图限制下的( ，) 问题，则可以看作是一种约束条件下的边染色，即已 经有k 条边染了k 种不同的颜色，然后选择最少的颜色数将其他边染色。 首先，介绍一个命题， 命题【2 l 若g 是二部图，则g 是某一个一正则二部图g 的子图。 证明设g 是以( x ，r ) 为分划的二部图，x = 五，工。 ，y = y 。，y 。j 。 若g 是正则图，则取g 。= g 。若g 不是正则图，于是有( g ) a ( g ) ，首先将g 的两个拷贝g ，g ，用下面的方 法构造二部图，如图所示，其顶点 分划为( u ，“，x ：1 u y 2 1 ) ，然 后将g 中度小于的顶点，在 g o ，g 瞳中的对应点间连以边( 图 中用一表示) ，最后所得的图记作 g ，由g 的作法，g 中的顶点若 对应在g 中的度为时，它在g ，中的度仍为，而g ，中其它的顶点的度相对于 它在g 中的对应顶点的度要增加1 。若g l 已经是正贝矿图，贝憾g ：g ，否则类 似于由g 构造g l 的方法，由g 构造g ：，如此继续构造下去。显然，g 。一。即为 所求的g 。且若g 是单图，这样得到的g + 也是单图。 d 由上面的命题可以知道，g + 上关于肼的子正交匹配分解限制在g 上，一定 是g 关于m 的一个子正交匹配分解。则问题转化为寻找卜正则二部图上匹配m 的最小子正交匹配分解。 根据c a r a g i a r m i s 和k a k l a m a n i s 4 给出的定理， 0 山东大学硕士学位论文 定理2 2 ( c a r a g i a n n i s ，k a k l a m a n i s ) g 是卜正则的二部图，已经有s 条 边被染了s 种颜色，则存在多项式时间算法最多需要m a x l + s 2 , s 种颜色将g 的 边染色。 在定理中，如果令，= j | s = 七，则容易得到最多需要七+ 孝= 三2 i 次的多项式 近似算法。 第二节二部图上完美匹配的正交匹配分解 在这一节中我们将证明当给定匹配m 是简单二部图g 上的一个完美匹配时， 存在关于m 的正交匹配分解。最后并给出边集e 的一个划分算法。 给定二部图g 和完美匹配m = 矗，p ：，咋 ，图g 的顶点集v = u r ，设 x = 如一f 2 ， ，y = h ，v 2 ，v 女 ，且满足q = ( 虬，v ，) ，f _ 1 , 2 ，k 。下面记 从顶点“，到顶点的边为e 。，即p 。= ( ，v ，) 。 定理2 3 匹配是简单二部图g 的完美匹配，则g 存在关于吖的正交匹 配分解。 证明当g 不是完全二部圈时，只需要将g 完备化，得到g ，容易证明， 如果在g 上存在关于m 的f 交匹配分解，则对于同一个分解只需要将额外增加 的边从相应匹配中去掉就能得到g 上的一个证交匹配分解。所以下面只要在完 全二部图g 上对定理进行证明即可。 根据k 的奇偶性，分两种情况。 当k 是奇数时。 将= 部图对应产生一个k x k 矩阵，也就是图g 的点点关联矩阵，如下： 气气 0 0 ，p 0 q岛。巳唧 0 0 0 0q色巳；吼 j j j q乞巳 吼 山东人学联j 学位论文 按照从右上到左下的对角线方向将矩阵的元素集合记为，第l 行到第2 女一l 行，主对角线恰是第k 行，即第1 行是e l l ，第2 行是 p ：”e l , 2 ，当f s k 时，第 i 行是鲰i ，p h l 2 ，p i i ，第k + i 行是扣k 1 + lp ，! ，p l + i 。由此构造集合，为 所有第i 行和第k + f 行的元素，f = 1 , 2 k - i ，e k 恰好选取主对角线第k 行。下 面将证明这样的构造满足条件。 由矩阵与边的对应关系，容易知道每个e ，i = 1 , 2 ，k ，都是矩阵中两两不 同行不同列元素的集合，所以一定是图上的匹配。又因为k 是奇数，pl ，p ：。，e 分别在第1 ，3 ，七，k + 2 ，2 k 一1 行，由e 的构造方法知道，每个e 中有且仅有一 条a ，中的边。所以每一个均j 下交与给定匹配从 当k 为偶数时。 同样对应上面的矩阵，只是e 的构造方法不同，主要考虑的是从左上到右 下的对角线方向元素。i 从l 到七一2 。每一个对应矩阵不同行不同列的一种取 法，方法如下，对巨首先把p ，放到巨中，然后在矩阵中将第一行和第一列的 元素去掉，得到一个k l k l 矩阵，再取这个矩阵主对角线右侧第1 行的元素 和左侧第k - 2 行的元素；对e ：，首先把p 2 ：放到e ：中，然后在矩阵中将第二行 和第二列的元素去掉，又得到一个k 一1 x k 一1 矩阵，再取主对角线右侧第2 行的 元素和左侧第k 一3 行的元素，以此类推，对。，同样首先把e k _ ：。放到e 。中， 然后在矩阵中将第k 一2 行和第七一2 列的元素去掉，又得到个k 一1 k i 矩阵， 主对角线右侧第k 一2 行的元素和左侧第l 行的元素放到邑一，中。容易证明不会 有元素被重复取道。因为根据的选取规则，已经取过的元素不会出现在后面将要 选取的对角线上。显然，e ，i = 1 , 2 ，k 一2 ，是m 的i e 交匹配。去掉 eu e ：u u e k 一：对应元素后的矩阵如下： 山东大学硕士学位论文 每一行每一列恰有两个元素，由这些边形成的子图中，每个顶点的度都是2 ，所 以一定是一些圈的集合，又由矩阵可以看出，每一个圈恰好有4 个顶点。4 条边 是一个个的4 - 圈，而且由于边e j ，吼。i 1 已经取走，所以p h 十p 。j 不在同一个 圈上。每一个4 一圈可以产生两个匹配，下面将这些元素划分成两个集合e 。和 t ，满足每个集合都是的正交匹配，方法如下，首先，e k - l - + e 对应的两 个a 一圈分别是 吒吐。，。 卜。，e 争卜：以吐 和 。，鼍。，鼍 卜将这两个圈划 分出的匹配进行组合，使得满足e 。在集合e 。中，而吼。在集合b 中，这是 可以做到的，然后对于其它的每一个4 - 圈，将其中一个匹配放在e ，另一个 放在e 。这样最终可以得到e ，i = 1 2 ，k ，满足要求。 口 由定理的证明过程，可以得到求匹配的正交匹配分解的多项式算法。 算法l ： 当k 是奇数时，边集e 按下面方法划分， e l = 乩；p 2 岛扣l ，一， 3 ，吼2 ， & = 扛，气i ；e 3 ，p 蚶，吒吐4 3 ， t l = k n i ，e 2 h ， 一 o o ； o ：o e p 0吃；o o ：o o；o o ；o 印oo 如。o g o ；o 扣；o 已 o o冬6； 山东大学硕士学位论文 & = 卜 吃。，e 等竽， 当i 是偶数时，边集e 按下面方法划分， e 。= i z t j ；吃，q 。，p j ，。，吐。，2 ， e 2 = e 2 2 ；p 35 ，p 4 6 ，p + 2 ，8 * 一2 ，p 女一，p i 3 ， e = 扛s j ；e + 】+ l + ，p ，+ 2 j + 2 + j ，p ，+ ，j + 。+ ，p 一j ，p t 一，+ 1 1 ，p t 1 一l ，p i + l ， e 心= 轨- 2 _ h ；p m n ，q ，吃l ，p 卜4 ， 令e = e e ，u e u u e 一：，由上面的构造知， = e 1 2 , e l , 3 ；e 2 , 4 , e ：，；，；e ；? ，e ；。；e ；+ ，：，e ；+ ，；e 。，e ；， ，贝u e。一。=p。一。一，p；一，。一：；p；。，p。，；p。，p；+。，：；p：，p；+：。；p；一：j一，p。一：。一。 e k = e l 矗 容易得到下面的定理， 定理2 4 算法l 能够在多项式时间内给出简单二部图g 关于完美匹配吖 的一个芷交匹配分解。 4 、lrj 2 山东大学硕士学位论文 第三章简单图上完美匹配的子正交匹配分解 在这一章中，将舍弃二部图的限制，讨论给定一个最大度为七的简单图g ， m 是g 的一个完美匹配，寻找关于肘的最小子正交匹配分解。下面将给出这个 问题的一个最多需要2 七- 1 次匹配的近似算法，并且说明这种算法思想的下界是 睦e 1 ，最后再给出一种特殊情况下的陪后1 次匹配的近似算法。 第一节引言 首先介绍文章中将要用到的两个重要算法，f t e u r y 算法和a + 卜边着色算法 f l ，2 】。 第一个是求e u l e r 图上e u l e r 环游的f l e u r y 算法， 定义3 1连通图g 的一条闭途径阢如果它过所有的边且只通过一次，贝j 称矿为g 中的一个e u l e r 环游。 定义3 2 存在e u l e r 环游的图称为e u l e r 图。 在很早的时候，e u l e r 就给出了判断一个图是不是e u l e r 图的充要条件， 定理3 1 ( e u l e r ) 非空连通图是e u l e r 图的充要条件是它不合奇数度的点。 给定e u l e r 图g ，顶点集，边集，则有下面f l e u d 算法，可以给出6 的 一条e u l e r 环游。 f l e u r y 算法： 第l 步；选任意一个顶点v 。，令= v 。 第2 步：假设迹w j = v o p 。v q v 已选好，从酣和；，p ：，p ， 中按下列方法选 择一条边p 。： ( i ) ：e j + i 与v 。关联。 ( i i ) ：除非没有其它选择，气：不是g ，= g e ，岛，巳 的割边。 山东大学硕士学位论文 第3 步：当第2 步不能执行时，停止。 第二个是在单图g 上寻找正常+ 卜边着色的多项式时间算法， 定义3 3 假如关联顶点v 的一条边着以i 色，则称i 色在顶点v 处出现。 定义3 4 给定g 的卜边着色f 后，用c ( v ) 表示在v 上出现的不同颜色的数 目：若不存在另外一个j 】卜边着色f ，它在v 上出现的不同颜色的数目为c ( v ) - 使c ( v ) c ( v ) ，则称f 为g 的个最优卜边着色。 惟幢l 引理3 a 1 2 1 设f = ( 巨，e ：，。) 是g 的一个最优卜边着色。若存在g 中 的一个顶点u 和不同的颜色i 及j ，使得j 色在不出现，而j 色在“至少出现两 次，则g ( 置u ，) 中包含群的分支是奇蹈。 定理3 2 ( v i z i n g 定理) 若g 是单图，则z7 ( g ) = ( g ) n ：a ( g ) + l 。 由v i z i n g 定理可知，对任意的单图，一定存在难常的a + 卜边着色，且+ 卜 边着色是币常的当且仅当它是最优的。所以要寻找一常的+ 卜边着色只要寻找 最优的+ 1 一边着色即可。 由引理3 1 知，一个+ 1 一边着色，若存在顶点和颜色i 及，使得i 色在 l f 不出现，研色在“至少两次出现，且6 ( e u e 包含l l 的那个分支( 记为g 。( “) ) 不是一条奇圈，则它不是最优的。这样可以改进原先的+ 1 边着色，方法如下： 若g f ( “) 是e u l e r 图，在g f ( 甜) 上使用f l e u r y 算法，得到瓯( 甜 的一个e u | e r 环游。 若g ， ) 不是e u l e r 图，则用增添一个新顶点并把它和g 。( z ，) 中每个奇度的 顶点连以边的方法构造一个e u l e r 图g ： ) 。在g ：( “) 上使用f l e u r y 算法，得到 瓯( “) 上的个e u l e r 环游。 将上面得到的e u l e r 环游，依各边在环游上的顺序关系交错地着i 色和，色。 ( j 。0 ) 上的这样的边着色与g 。( “) 外的原+ 卜边着色一起构成了g 的一个改进 的+ l 一边着色。如果这种改进盼着色仍不是最筑的，又可以重复上述的过程， 直至得到最优得+ 卜边着色。d 表示顶点个数，具体的算法如下： 6 山东大学硕士学位论文 + 1 一边着色算法： 第0 步：d ( v i ) 一以( _ | = 1 , 2 ，西：任给一个+ l 一边着色( 置，e 2 ，e 。) 。 第1 步：0 _ q ( 七= 1 , 2 ，u ) ；0 斗g ，1 _ s 。 第2 步：令p = o 。 第3 步： e s 彩，任取v ，q e ，p u 以，) 一p ，转第4 步：否则，转第 5 步。 第4 步：e p ，v ，) 一e ，转第3 步。 第5 步：v k p ，令“+ 1 _ 唧。 第6 步：若s + l ，则s + 1 一j 转第2 步：否则，转第7 步。 第7 步：若q u ，则q + 1 _ q ，转第8 步：否则，停。 第8 步：若气 噍，则令“= _ ，ji , j 色，使在甜上f 色不出现，歹色至少 出现两次，找出g 【巨u j 含甜的分支g ，0 ) ，转第9 步；否则，转第7 步。 第9 步；若色0 ) 是e u l e r 图，在q 0 ) 上使用f l e u r y 算法，求g 。( ) 上的一 个e u l e r 环游。转第1 1 步。 第t 0 步：增添新顶点，构造e u l e r 图g ：0 ) 并在g ：( ) 上使用f l e u r y 算法， 求0 ) 上的一个e u l e r 环游。转第1 1 步。 第1 1 步：将e u l e r 环游上的边依次排好，次序为奇数( 偶数) 且属于g 。0 ) 的边集记为e ( e ) 。令池e 皖( “) ) ) u 譬斗互，( e j e ( g ，( “) ) ) u f - + ， v h i , j ，毛专e ，转第l 步。 算法的分析： 算法的第1 步至第8 步是判断十1 一边着色是否为最优的+ 1 邀着色，主 要是计算各个顶点出现的不同的颜色数q ( j = 1 ，2 ，u ) ，其中运算次数不会超过 ( 3 c ：+ v x a + i ) 。第8 步中构作g 。( h ) 的运算次数不超过础。第9 步至第l l 步 是改进+ i 一边着色，其中主要是f l e u r y 算法，已知它是好算法，且改进的循环 山东大学硕士学位论文 次数不会超过2 9 。因而+ 卜边着色算法是好算法。 以上两个算法均是多项式时间的好算法。 在这一节中，给出的算法分三个阶段执行： 第一阶段是将图g 的顶点集矿划分成两个部分x 和n 使得满足下面两个 条件： 1 对于m 中的任何一条边e 的两个端点“，v ，有“。x & v 】，或者 i t ，y & q 爿： 2 由和j ，分别生成子图g ( x ) 和g ( 1 ，) ，使得在这两个子图的晟大度尽量 小。 第二阶段是在子图g ( x ) 和g ( y ) 上分别执行+ l 一边着色算法。 第三阶段，g 中未染色的边恰好构成以和】，为两个顶点集的二部图，在 这个二部圈上执行上一节的币交匹配分解算法l 。 其中，算法第一阶段的条件2 是核心的内容，以下所提及的算法，均是为了 达到更好的满足条件2 。 第二节上述算法思想的下界是陪七 次 特殊情形下，图g 上一个顶点“与匹配吖中的j _ k - 厂ij 条边的两个端点均育 边相连，则显然“的度不会超过k ，在这种情况下，点“所在子图g ( ) 或者g f y ) 中度至少是l 等 惘算法可知4 腑l 等j 小t = 斟。其中4 肘表示 算法输出的近似解，也就是所需要的匹配次数。 第三节一种最多需要2 k 一1 次匹配的近似算法 根据上面的思想，容易得到下面是多用2 k 一1 次匹配的近似算法 山东大学硕士学位论文 算法2 ： 第一阶段：从任一满足条件l 和条件2 的矿的划分肖和y 丌始，生成子图 g ( x ) 和g ( y ) 。 在子图g ( x ) 中，如果有两个以上的度为k - i 的顶点，则将其中任意一个顶 点与它在y 中相应的顶点对换，得到新的x 和y ，然后转入第二阶段： 如果有且仅有一个度为k l 的顶点，检查在g ( y ) 中与这个顶点相应顶点， 如果它与x 中的所有顶点都有边相关联，则交换除这对顶点外的其它任意一对 顶点，得到新的x 和n 然