（运筹学与控制论专业论文）图的导出匹配覆盖.pdf

摘要 本文所讨论的图均为有限的简单图对于任意图g ，y ( g ) 和e ( g ) 分别表示 它的顶点集和边集对顶点集x y ( g ) ，令 g g ( x ) = 札 e ( g ) ：钍，口x ) x 的邻点集0 ( x ) 定义为 g ( x ) = 可v ( g ) x ：存在z x 使得z 口e ( g ) ) x 的悬挂邻集o ( x ) 定义为 o ( x ) = 可g ( x ) ：d ( ) = 1 ) 对任意顶点”，”的悬挂度定义为 d 0 ( ”) = i o ( ”) 对于m e ( g ) ，令 v ( m ) = v ( g ) ：存在一个顶点z y ( g ) 使得计z m 如果m e ( g ) ，xcy ( g ) 使得x y ( m ) ，我们称m 覆盖x 如果m e ( g ) ，且 对任意不同的边e ，m ，矿( e ) n y ( ，) = 0 ，则称m 是图g 的一个匹配若匹配m 满足v ( 肼) = y ( g ) ，则称m 是图g 的完美匹配若匹配m 满足岛( y ( m ) ) = m ， 则称m 是图g 的导出匹配 集合x 的一个一划分是指一个七元组( 蜀，恐，甄) 使得蜀，凰，瓜 是满足u 五= x 的x 的互不相交的子集如果g 是有完美匹配的连通图， 假设( ，k ) 是y ( g ) 的一个七一划分我们说( k ，k ，k ) 是g 的一个 七一导出匹配划分，如果对每一个i ( 1 茎i 墨七) 而言，g f 是g 的一个l 一正则 导出子图g 的导出匹配划分数定义为使得g 有七一导出匹配划分的最小整数 ，记为。m p ( g ) 设m ，是g 的个导出匹配，若y ( 尬) u u y ( 慨) = y ( g ) ，则 称 舰，慨) 是g 的一个南一导出匹配覆盖g 的导出匹配覆盖数定义 为使得g 有七一导出匹配覆盖的最小整数七，记为i m c ( g ) 如果g 是顶点数至少为3 的树我们记 o ( g ) = m o z d o ( u ) ：u 矿( g ) ) ， ；( g ) = m o z d 0 ( 札) + d o 扣) ：u ，”y ( g ) ，札 e ( g ) ) 在本文中，我们主要研究了以下两个部分：( 1 ) 树和3 一正则无爪图的导出 匹配覆盖；( 2 ) 图的导出匹配覆盖问题的计算复杂性 第二章讨论了树和3 一正则无爪图的导出匹配覆盖，主要得到以下结果： 定理1 设g 是顶点数至少为3 的树则i m c ( g ) f 邻( g ) ，铋( g ) + l ，甾( g ) + 2 ， 其中茜( g ) = m n 。 d 0 ( “) + d o ( ”) ：u ，u y ( g ) ，u ”e ( g ) ) 进一步，如果；( g ) o ( g ) ，贝0i m c ( g ) ；( g ) ，；( g ) + 1 ) 定理2 设g 是3 一正则无爪图，则i m c ( g ) 2 ，3 第三章研究了图的导出匹配覆盖问题的计算复杂性，主要结果如下： 定理3 直径为6 的图的2 一导出匹配覆盖问题是n p 一完备的 定理4 直径为2 的图的3 一导出匹配覆盖问题是n p 一完备的 定理5 设g 是直径为2 的图令x = 。y ( g ) ：d g ( z ) = 2 ) 则i m c ( g ) = 2 当且仅当下列两个条件之一成立： ( 1 ) i 叩( g ) = 2 ； ( 2 ) i 盯巾( g ) 2 ，且存在这样的顶点z x 使得( g 一 z ) ) u + 局，记为g 1 ， 满足2 ”印( g 。) = 2 ，其中k 是空图，1 y ( ) 【= 2 ，kny ( g ) = 0 ，玩= ( 可，z ) ： g ( z ) ，z ) 最后还给出了直径为2 的图的2 一导出匹配覆盖问题的多项式时间算法 关键词：导出匹配；导出匹配覆盖；树；3 一正则无爪图；n p 一完备；多项 式时间算法 a b s 七r a c t g r a p h sc o n s i d e r e di nt h i 8p a p e ra r ef i n i t ea r l d8 i m p l e f b rag r a p hg ，y ( g ) a n de ( g ) d e n o t ei t 8s e t so fv e r t i c e sa n de d g e 8 ，r e s p e c t i v e l y f 0 rav e r t e xs e tx s 矿( g ) ，s e t ) = “”e ( g ) ：“，”x ) t h en e i g h b o rs e t 舀( 玎) o f yi sd e f i n e db y 0 ( x ) = g 矿( g ) x ：t h e r e 诂z x8 “c ht 耐z 届( g ) ) t h ep e n d a n tn e i g h b o rs e t j ( x ) o f xi sd e 6 n e db y 0 ( x ) = g ( x ) ：d ( ) = 1 ) f 0 ra n yv e r t e xu ，t h ep e n d a n td e g r e eo h i sd 幽1 1 e db y f b rm f ( g ) ，s e t d o ( ”) = f 批( ”) 矿( m ) = 矿( g ) ：t e r e 如z v ( g ) s 乱c t t 茁n 彳 i fm e ( g ) a n dxcy ( g ) a l es u c ht h a tx v ( m ) ，w e s a ym c o v e r sxi fm e ( g 1 a n d ，f 【) re v e r yt w od j s t j n c te d g e se ，l ，们，v ( e ) ny ( ，) = d ，w e s a yt h a ta ，j sam a t c h i n g o fg 彳i sc a i l e dap e r f e c tm a t c h i n go fg ，i fv ( 彳) = y ( g ) am a t c h i n g 且fi si r l d u c e di f 日；( y ( m ) ) = m a 南。p a r t i t i o no fas e txi sa 肛t u p i e ( x 1 ，恐，甄) s u c ht l l a t 置，恐，凰a r e m u t u a l l yd i s j o i n t8 u b s e t so fx8 u c ht h a tu 咒= x a 七一i n d u c e d m a t c h j n gp a r t j t i o no f ag r a p l lgw l l i c hh a sap e r f e c tm a t c h i n gi 8a 缸p a r t i t i o n ( k ，k ) o fy ( g ) s u c h t h a t ， f o re a c hi ( 1 茎i 后) ，t h es u b g r a p hg i 】o fg i n d u c e db yki s1 一r e g u l a r t h ei n d l l c e d m a t ( 如i n gp a r “t j o nn u m b e ro fag r a p hg ，d e n o t e db yi 7 n p ( g ) ，i st h e1 1 1 i n i i n u mi n t e g e r 七 s u c ht h a tgh a sa 七一i n d u c e d m a t c h i n gp a r t i t i o n 1 l l l e t 尬，坞，呱b e i n d u c e dm t c l l i n g so fg w es a yt h a t 尬，慨) i 8 a 七一i n d u c 缸m a t c h j n gc o v e ro fg i fy ( 尬) u uy ( 慨) = 矿( g ) t h ei n d u c e dm a t c l l i n g n u m b e ro fg ，d 锄o t e db yi m c ( g ) ，i sd e 矗n e dt ob et h em i n i m u mn u m b e r 后s u c ht h a t gh a sa 屉一i n d u c e d m a t c h i i 培c o v e r i fgi sat r e ew i t ha tl e a s tt h r e ev e r t i c e s w e8 e t o ( g ) = m n z 而如) ：让矿( g ) ) ；( g ) = m n z d 0 ( u ) + d 0 ( 口) ：u ，口y ( g ) ，“u e ( g ) ) ， i nt h i sp a p e r ，w ep a yo u ra t t e n t i o nm 缸n l yt ot h ef o u o w i n gt w op a r t s ：( 1 ) c o v e rt h e v e r t i c 朗o fat r e eo ra3 _ r e g u l 盯c l a 舯f r e eg r 印hb yi n d u c e dm a t c h i n g s ；( 2 ) t h ec o m p l e x i t y o fc o v e r i l l gt h ev e r t i c e so fag r a p hb yi n d u c e dm a t c h i n g s i nc h a p t e r2 ，r ed i s c u s st h ep r o b l e mo fc o v e r i n gt h ev e r t i c e so fat r e eo ra3 r e g u l a r c l a w f r e eg r a p hb yj n d u c e dm a t c h i n g s w bo b t a i nt h ef 0 1 l o w i n gr e s u i t s ： t h e o r e m1l e tgb eat r e ew i t ha tl e a s tt h r e ev e r t i c e s t h e ni m c ( g ) j ( g ) ，；( g ) + 1 ，；( g ) + 2 ) ，w h e r e ；( g ) = m o z d 0 ( 札) + d o ( ) ：钍，可v ( g ) ，“ e ( g ) ) m o r e o v e r ， i f j ( g ) o ( g ) ，t h e n 如q c ( g ) ；( g ) ，；( g ) 十1 ) t h e o r e m2l e tgb ea3 - r e g u l a rc l a w f r e eg r a p h t h e ni m c ( g ) 2 ，3 ) i nc h a p t e r3 ，w ei n v e s t i g a t et h ec o m p l e x i t yo fc o v e r i n gt h ev e r t i c e so fag r a p hb y i n d u c e dm a t c l l i r l g s w eo b t a i nt h ef o l l o w i n gr e 8 u l t s ： t h e o r e m3t h e2 一i n d u c e d m a t c h i n gc o 、佗rp r o b l e mo fg r a p t l sw i t hd i 呦e t e r6i s n p c o m p l e t e t h e o r e m4t h e3 一i n d u c e d 一l a t c h i n gc o v e rp r o b l e mo fg r 印h 8w i t hd i a m e t e r2i s n p c o m p l e t e t h e o r e m5l e tgb eag r a p hw i t hd i a m e t e r2 ，a n dx = z y ( g ) ：d 8 ( z ) = 2 ) t h e ni m c ( g ) = 2i fa n do n l yi fo n eo ft h ef o l l o w i n gt w oc o n d i t i o n sh 0 1 d 8 ： ( 1 ) i m p ( g ) = 2 ( 2 ) i m 田( g ) 2 ，a n d t h e r ee ) 【i 8 t 8a 、他r t e xzo f x8 1 l c ht h a t ( g 一 。) ) u j f + 上 0 ，d e n o t e d l v b yg 1 ，s a t i 8 f i e si m p ( g 1 ) = 2 ，w h e r eki s 柚唧p t y 口a p h w i t hl y ( k ) i = 2 ，k n y ( g ) = 0 ， a n d 岛= ( ，z ) ：舀( 茁) ，z k _ ) f i n a l ly 】w eg i v eap 0 1 y n o l i a l - t i i n em g o r i t h mf o rt h ep r o b l e mo fc o v e r i n gt h ev e r t i c e s o fag r a p hw i t hd i a m e t e r2b y2i n d u c e dm a t c h i n 9 8 k e yw b r d s ：i n d u c e dm a t c h i n 舀i n d u c e dm a t c h i n gc o v e r ；t r e e ；3 一r e g u l a rc l a - f r e e g r a p h ；n p c o m p l e t e ；p 0 1 y n o m i 止t i j n ea l g o r i t h m v 郑重声明 本人的学位论文是在导师指导下独立撰写并完成的，学位论文没有剽窃、 抄袭等违反学术道德、学术规范的侵权行为，否则，本人愿意承担由此产生的 一切法律责任和法律后果，特此郑重声明 学位论文作者：彳晡 卅年牛月“日 第一章引言 这一章将对本文进行简要介绍其中第一节介绍匹配理论的有关知识，第 二节列出本文用到的概念以及符号，第三节给出一些已知的相关结果，第四节 列出本文的主要结论 1 1 匹配理论简介 匹配理论是图论中的一个重要内容它的应用非常广泛近几十年来，随 着组合数学的迅速发展，匹配理论成为许多重要理论的基础和源泉 匹配理论和线性规划里面的任务分配问题一样，无论在理论研究还是在实 际工作中都有十分广泛的应用比如，在一些实际问题中，为了寻找所有的最 优篇，人们希望描述一个图g 的所有的最大匹配的结构性质如果图g 的一 个匹配包含它的所有顶点，则称其为完美匹配，关于完美匹配，图论工作者已 经做了大量的工作，得出许多重要的结论 h a l l 定理 5 】给出一个二部图有完美匹配的充分必要条件n t t e 和l o v a s z 5 ，6 给出了一般图具有完美匹配的描述，k u h n 和h a l l 第一次提供了在二部图 中寻找完美匹配的算法，对一般图中的完美匹配，e d m o n d s 2 】在1 9 6 5 年首先 给出多项式时间的算法 p l u m m e r 【17 】提出如下的扎可扩图的概念：设p 和礼为正整数，且扎s 一2 ) 2 一个p 个顶点的图g 称为n 可扩的，如果图g 的每一个包含咒条边的匹配都 能扩充为一个完美匹配h e t ”i 1 4 】研究了二部图的n 可扩性在十九世纪五 十年代后期，k 0 t z i g ( 1 4 】开始研究具有完美匹配的图的分解问题，但是不幸的 是，因为他们的论文是用斯洛伐克语撰写的，所以没有得到应有的重视十九 世纪六十年代初期，g a l l a i 【1 4 】和e d m o n d s 1 8 开始各自独立地研究图的最大 匹配的分解问题受h e t ”i ，k o t z i g ，g a l l a i 和e d m o n d s 结论的启发，l 删z 将已 有的分解进行了扩充，使之更加精确和规范一个图g 称为二临界的，如果对 图g 的任意一对不相同的顶点u ，”，图g 一札一”有一个完美匹配如果一个图 1 是二临界的，则它是1 可扩的一个有趣的结论是，如果一个图是2 可扩的， 则它或者是二部图或者是二临界的另外，如果一个图是n 可扩的，则它也是 n 一1 可扩的 c a m e r o nf 3 】给出了导出匹配的定义，我们称一个匹配m 是导出匹配，如果 如( y ( m ) ) = m 对于导出匹配，人们在二部图，3 一正则图和4 一正则图等方面 做出了一系列的结论 原晋江 1 0 l 提出了图的导出匹配可扩性问题对一个简单有限图g ，如果图 g 的任意一个导出匹配都包含在一个完美匹配中，则称图g 是导出匹配可扩 的导出匹配可扩性可以看成是n 可扩性的变异情形图的1 可扩性在化学图 论当中有着重要的应用注意到导出匹配可扩图一定是l 可扩的，因此导出匹 配可扩图的提出可以看成是1 可扩性的另一个方面的延伸 我们知道存在寻找一个图的最大匹配的多项式算法但是c a m e r o n 3 】证明 了即使对二部图来讲，寻找它的最大导出匹配问题也是n p 困难的导出匹配 可扩性问题比起他可扩性问题似乎要难一些，杨帆和原晋江【1 9 】证明了直径为 2 的图和直径为3 的二部图的导出匹配可扩性问题是c o n p 困难的 图的一导出匹配划分问题最早是作为一个组合优化问题 7 】被人们所研究 的g a r e y 和j o h 璐o nf 7 1 证明了图的一导出匹配划分问题是n p 一完备的，分别 证明了2 一导出匹配划分问题的n p 一完备性和3 一正则平面图的一导出匹配划 分问题的n p 一完备性原晋江和王勤 9 证明了，如果图g 是一个有完美匹配 的图，则i m p ( g ) s2 ( g ) 一1 ，其中i ”妒( g ) 是指g 的导出匹配划分数，( g ) 是指 g 中顶点的最大度9 1 进一步证明了，如果g 是连通的，则i 唧( g ) = 2 ( g ) 一1 的充分必要条件是g 同构于扔或者g 4 或者p e t e r s e n 图，这里g 是指长度 为佗的圈杨爱峰和原晋江 8 又给出了图的导出匹配划分问题的n p 困难性 证明f 9 1 证明了直径为6 图的的2 一导出匹配划分问题和直径为2 的图的3 一 导出匹配划分问题的n p 一完备性，此外还给出了直径为2 的图的2 一导出匹配 划分问题的多项式时间算法 图的导出匹配划分问题是在一个图有完美匹配的基础上进行研究的但 是，对于任意图而言，不一定存在完美匹配后来，原晋江提出了图的导出匹 2 配覆盖问题我们可以将图的导出匹配划分与导出匹配覆盖做如下比较t( 1 ) 图的导出匹配划分要求的图类具有完美匹配，而图的导出匹配覆盖仅要求所研 究的图类没有孤立点因此，图的导出匹配覆盖相对于图的导出匹配划分而言 适应于更多的图类( 2 ) 对有完美匹配的图类，图的导出匹配覆盖数也有小于 其导出匹配划分数的可能例如：c k + 。的导出匹配划分数为3 而其导出匹配覆 盖数为2 ；h e a w o o d 图的导出匹配划分数为4 而其导出匹配覆盖数为3 ；p e t e r s e n 图的导出匹配划分数为5 而其导出匹配覆盖数为3 本文就是针对图的导出匹 配覆盖问题做出的一些结果文中界定了树和3 一正则无瓜图的导出匹配覆盖 数的精确取值范围，并给出了图的导出匹配覆盖问题的n p 困难性证明 1 2 概念和符号 本文所讨论的图均为有限的简单图对于任意图g ，y ( g ) 和e ( g ) 分别表示 它的顶点集和边集对于x y ( g ) ，x 的邻点集g ) 定义为 0 ) = y ( g ) x ：存在。x 使得z e ( g ) ) x 的闭邻集定义为 v 舀陋 = g ( x ) u x x 的悬挂邻集0 ( x ) 定义为 o ( x ) = 目g ( x ) ：d 匆) = 1 x 的闭悬挂邻集定义为 0 】_ 0 ( x ) u x 对任意顶点订，w 的悬挂度定义为 d 0 ( ”) = j 0 ( u ) | 对于m 至e ( g ) ，令 v ( m ) = y ( g ) ：存在一个顶点z v ( g ) 使得口z m ) 3 对于s y ( g ) ，我们记 髓( s ) = 钍钉e ( g ) ：札， s 我们称m 覆盖x ，如果m e ( g ) ，x v ( g ) 使得x y ( m ) m e ( g ) 称为g 的一个匹配，如果m 中任意两条不同的边e ，满足y ( e ) n y ( ，) = o g 的一个 匹配m 称为完美匹配，如果y ( m ) = y ( g ) g 的一个匹配m 称为导出匹配， 如果奶( y ( m ) ) = m 集合x 的一个七一划分是指一个元组( x t ，娲，) 使得x ，局，讯 是满足u 咒= x 的x 的互不相交的子集图g 的一个女一着色是指矿( g ) 的 一个一划分( k ，k ，k ) 使得每一个k ( 1si 茎) 是g 的一个独立集g 的 点着色数，记为) ( ( g ) ，是指使g 有七一着色的最小整数 如果g 是有完美匹配的连通图，假设( k ，k ，k ) 是y ( g ) 的一个一划分 我们说( k ，k ，k ) 是g 的一个一导出匹配划分，如果对每一个i ( 1 ts ) 而言，g k 是g 的一个1 一正则导出子图 g 的导出匹配划分数定义为使得 g 有一导出匹配划分的最小整数，记为i 唧( g ) 假设尬，尬，慨是g 的七个导出匹配我们说 尬，慨) 是g 的 一个一导出匹配覆盖，如果v ( 尬) u u y ( ) = y ( g ) g 的导出匹配覆盖数 定义为使得g 有七一导出匹配覆盖的最小整数七，记为打n c ( g ) 显然，j m c ( g ) 是 定义在没有孤立点的图上的 下面列出一些与计算复杂性相关的定义 判定问题：一个判定问题是一个二元对a = ( x ，y ) ，其中x 是在多项式时间 内可判定的语言，y x x 中的元素称为a 的实例；y 中的元素称为a 的 y e s 一实例；x 】，中的元素称为a 的n o 一实例其中， “判定问题”中的“判 定”是指判定z y ( e s ) 或z 隹y ( n o ) p 问题：p 表示多项式时间算法所能解决的判定问题 n p 问题：一个判定问题a 称为是n p 的，当且仅当对a 的每一个y e s 一实 例而言，存在对剪的一个简短( 即长度以目的长度的多项式为界) 证明，使得 能在多项式时间内检验这个证明的真实性 4 n p 一完备问题：一个判定问题a n p 称为是n p 一完备的，如果所有其他 的n p 问题都能多项式地归结到a 1 3 已知相关结果 本节列出一些关于图的导出匹配划分问题的重要结论 定理1 3 1 1 l ( b r 0 0 k s 定理) 如果g 是连通图，且g 既非奇圈，也非完全 图，则x ( g ) ( g ) 定理1 3 2 9 对于一个有完美匹配的连通图g ，i 仃巾( g ) s2 ( g ) 一1 ；等 式成立的充要条件是g 同构于尬，a 蚪。或者p e t e r s e n 图 定理1 3 3 2 】设问题p 和q 是两个判定问题如果p 是n p 问题，q 是 n p 一完备问题，并且q 可以多项式转化为问题p ，那么p 也是n p 一完备的 定理1 3 4 7 】“无否定字符的三分之一3 一适定性”问题是n p 一完备的 定理1 3 5 8 直径为6 的图的2 一导出匹配划分问题是n p 一完备的 定理1 3 6 8 直径为2 的图的3 一导出匹配划分问题是n p 一完备的 定理1 3 7 8 设g 是直径为2 的图令 岛= z e ( g ) ：g g ( z ，) ) 】的每一个分支同构于k t 或尬 则i ”妒( g ) = 2 当且仅当下面两个条件之一成立； ( 1 ) 存在e 7 垦e ( g ) 使得1sie ，i 2 ，且g 0 ( y ( e ，) ) 】和g a b ( y ( e ，) ) 都是 1 - 正则的 ( 2 ) 岛是g 的一个完美匹配，且g 蜀是一个二部图 算法i m p ( h ) 8 】= 直径为2 的图的2 一导出匹配划分问题的多项式时间算法 输入：直径为2 的图日 第1 步：计算目= 。可e ( 日) ：日【( z ，9 ) ) 的每一个分支同构于k 。或凰) 第2 步：如果晶是日的完美匹配，且日e 。是二部图，则日的一个2 一导 出匹配划分( k ，) 可以利用h 的2 一划分求得转第6 步； 否则，转下一步 5 第3 步：令 a = e 7 e ( 日) ：1 l e i 曼2 ) ， b = h ( 矿( f y ) ) ：e 7 a 第4 步：如果存在某个x 日使得日】和h x 都是1 一正则的，则( ，k ) 是日的一个2 一导出匹配划分，其中m = x ，= y ( 日) x 转第6 步； 否则，转下一步 第5 步：输出：i 印( ) 2 第6 步：输出：日的一个2 一导出匹配划分( ，) 1 4 本文主要结论 在这篇文章中，我们研究了图的导出匹配覆盖问题，得出以下结论： 定理1 设g 是顶点数至少为3 的树，则 m c ( g ) 锦( g ) ，铺( g ) + 1 ，铺( g ) + 2 李中；( g ) = m n z d 0 ( ) + d 0 ( ) ：“，”v ( g ) ， e ( g ) 进一步，如果茜( g ) 0 ( g ) ，则i m c ( g ) 6 ( g ) ，锔( g ) + 1 ) 定理2 设g 是3 一正则无爪图，则i m c ( g ) 2 ，3 ) 定理3 直径为6 的图的2 一导出匹配覆盖问题是n p 一完备的 定理4 直径为2 的图的3 一导出匹配覆盖问题是n p 一完备的 定理5 设g 是直径为2 的图令x = z v ( g ) ：d g ( z ) = 2 ) 则一c ( g ) = 2 当且仅当下列两个条件之一成立： ( 1 ) i m p ( g ) = 2 ； ( 2 ) i 盯妒( g ) 2 ，且存在这样的顶点z x 使得( g 一 z ) u k + 岛，记为g ， 满足i 印( g ，) = 2 ，其中k 是空图，i y ( k ) l = 2 ，knv ( g ) = 0 ，蜀= ( ，z ) ：口 ( z ) ，z ) 算法i m c ：直径为2 的图的2 一导出匹配覆盖问题的多项式时间算法 6 第二章两类图的导出匹配覆盖 2 1基本概念 本文所讨论的图均为有限的觯图对于任意图g ，y ( g ) 和e ( g ) 分别表 示它的顶点集和边集对于g 中任一点z ，d g ( z ) 表示z 在g 中的度，( g ) 和 d ( g ) 分别表示g 的最大度和最小度对于x 矿( g ) ，我们记 g ( x ) = m a x d g ( z ) ：z x 如陋) = m i n d g ( z ) ：z x ) x 的邻点集舀( x ) 定义为 b ( x ) 2 y ( g ) x ：存在。x 使得z 鲈e ( g ) ) 对任意。y ( g ) ，简记g ( 忙) ) 为g ( z ) x 的悬挂邻集0 ( x ) 定义为 0 ( x ) = g ( x ) ：d g ( 可) = 1 对任意z v ( g ) ，简记0 ( z ) ) 为0 ( z ) 对任意x 至y ( g ) 和。y ( g ) ，我们记 j ) v 0 x = g ( x ) u x ， g m = b ( z ) u z ， j x = j ( x ) u x ， b z 】= v b ( z ) u z ) g 中任一点u 的度，悬挂邻集，和悬挂度分别表示为 d g ( n ) = f b ( 乱) 4 ， j ( “) = 。y ( g ) ：。“e ( g ) ，如( z ) = 1 ) ， 7 d 0 ( 让) = l 0 ( u ) 对于m e ( g ) ，令 y ( m ) = y ( g ) ：存在一个顶点。y ( g ) 使得u 。m ) 对于e ( g ) 中任一条边e ，简记y ( e ) ) 为y ( e ) 对于s y ( g ) ，我们记 上1 g ( s ) = u 订e ( g ) ：“， s ) 我们称m 覆盖x ，如果m e ( g ) ，xcy ( g ) 使得x v ( m ) m e ( g ) 称为g 的一个匹配，如果m 中任意两条不同的边e ，满足y ( e ) ny ( ，) = 0 g 的一个 匹配m 称为完美匹配，如果y ( m ) = y ( g ) g 的一个匹配m 称为导出匹配， 如果玩( y ( m ) ) = m 假设尬，慨是g 的个导出匹配我们说 尬，喝，地) 是g 的 一个一导出匹配覆盖，如果y ( g ) = y ( 舰) u uy ( 懈) g 的导出匹配覆盖数 定义为使得g 有七一导出匹配覆盖的最小整数七，记为i m c ( g ) 显然，。m c ( g ) 是 定义在没有孤立点的图上的 52 2树的导出匹配覆盖 设g 是顶点数至少为3 的树我们记 o ( g ) = m o z d 0 似) ：珏v ( g ) ；( g ) = m o 。 d 0 ( “) + d 0 ( 口) ：“， y ( g ) ，扎u e ( g ) ) 下面这些简单的结果对我们的证明是非常有用的 引理2 2 1 设g 是顶点数至少为3 的树，则i m c ( g ) 锑( g ) 证明由；( g ) 的定义可知，至少存在两个顶点札，”y ( g ) 满足札”e ( g ) ， 且d o ( u ) + d 0 ( ”) = 甾( g ) 由于任意两个顶点z o ( u ) 和0 ( ) 不能被同一个 8 导也匹配所覆盖，所以至少需要茜( g ) 个导出匹配才能覆盖0 ( 钍) u o ( ) 故 i m c ( g ) ；( g ) 引理2 2 2 设g 是满足。( g ) = 1 的任意树，则必存在g 的一个3 一导出匹 配覆盖 尬，m 2 ，m 3 ) ，使得g 的每一个顶点至多被 尬，m 2 ，) 中的两个导出匹 配所覆盖 证明采用反证法 假设g 是使引理2 2 2 的结论不成立的顶点数目最小的满足。( g ) = 1 的 树显然g 不是路，从而( g ) 3 我们记 s = 。矿( g ) ：d g ( z ) = 1 ) 对于每一个。s ，令p ( 茁) 是一条以z 为端点的路，其中j p ( 。) 的另一个端点是 p ( 。) 中唯一一个在g 中的度至少为3 的顶点显然p ( 。) 是由z 唯一确定的 由于o ( g ) = 1 ，我们可以观察到，存在顶点口s 使得i p ( 删2 设u ”e ( g ) 是唯一一条与 关联的边令 t ：g 叫 lg 一 “，”) 如果i 尸( ”) i 3 如果l p ( w ) i = 2 则t 是满足0 ( 丁) = 1 的树由g 的顶点数目最小的性质可知，丁有一个3 一导出匹配覆盖 尬，飓) ，使得丁的每一个顶点至多被 尬，坞，蝎) 中的两 个导出匹配覆盖我们可以选择使得l 尬i 十i 尬i + i 鸠l 最小的一组导出匹配 则t 中满足d 丁( z ) = 1 的任意顶点茁必然只被 m 。，尬，慨 中的唯一一个导出 匹配覆盖因为顶点乱或者满足曲( 珏) = 1 ，或者满足u 萑v ( t ) ，所以必然存在 尬，尬，飓) 中的两个导出匹配，比如说蛆和，使得u 隹v ( 舰u 尬) 也就 是说， 炳u u ) ，坞，尬 是g 的一个3 一导出匹配覆盖，且g 的每个顶点至 多被 尬u 札”) ，尬) 中的两个导出匹配覆盖这与假设矛盾故引理22 2 成立 引理2 2 3 设g 是顶点数至少为3 的树，且邻( g ) = 1 则i 僦( g ) 1 ，2 ，3 ) 9 证明由1 = ；( g ) 0 ( g ) = 1 和引理2 ，2 2 直接可得 引理2 2 4 设g 是顶点数至少为3 的树如果k 至y ( g ) 使得是独立 集，并且对于任意”k 有d 0 ( u ) 1 则g 0 【1 的每一个匹配都是导出匹配 证明如果是独立集，则g 0 【】的每一个连通分支都是一个星图由 于星图的任一个匹配都是它的导出匹配，所以g 0 嘶l 】的每一个匹配也都是它 的一个导出匹配 引理2 2 5 设g 是满足铺( g ) = 2 的树，则i m c ( g ) 2 ，3 ，4 ) 证明设 = u v ( g ) ：d 0 ( u ) = 2 ) 如果= o ，则0 ( g ) = 1 由引理22 2 可知，i m c ( g ) s3 如果k 0 ，那么很显 然是一个独立集 设m 是g 0 l 的一个最大匹配由引理2 2 4 可知，m 是一个导出匹 配设 g 7 = g 一( 0 ( ) n v ( m ) ) ， 则0 ( g ) = 1 利用引理2 2 2 可得，i m c ( g 7 ) 3 故i m c ( g ) 墨3 + 1 = 4 最后由 引理2 2 1 ，结论成立 定理2 2 6 设g 是顶点数至少为3 的树，则 i m c ( g ) ；( g ) ，；( g ) + 1 ，；( g ) + 2 ) 其中 ；( g ) = m n z d 0 沁) + d 。( ) ：钆， y ( g ) ，“u e ( g ) ) 进一步，如果；( g ) o ( g ) ，则 i m c ( g ) ；( g ) ，；( g ) + 1 ) 证明对铋( g ) 采用归纳法 1 n 如果铋( g ) 2 ，由引理2 2 3 和引理2 2 5 可以证明定理2 2 6 的正确性 设詹是正整数，且3 假设定理2 2 6 的结论对于满足锑( t ) 一1 的所 有树t 都成立 设g 是满足；( g ) = 七的任一个树令 ： 札y ( g ) ：d 0 ( 札) ：) ， u ：缸矿( g ) ：d 0 ( 。) ：) 如果d ，我们定义 日= g 】 由于日是一个偶图，我们可以选取日的一个2 一划分( x ，y ) ，使得对于任意 9 y 有如( ) 21 注意到，当日( 日) = 0 时，可以令x = y ( 日) ，y = o 进一步， 如果k = d ，则x = o 我们可以观察到，w = hux 是g 中的独立集设m 是g 0 w 】的最大匹配由引理2 2 4 知，m 是g 的一个导出匹配设 t = g 一0 ( w ) n y ( m ) 则 ；( 丁) = ；( g ) 一1 ， o ( t ) = o ( g ) 一1 由归纳假设，对丁而言，定理2 2 6 的结论成立再把导出匹配m 加入进来考 虑，我们可得 i m c ( g ) z m c ( t ) + 1 故对g 而言，结论也是成立的这就完成了定理2 26 的证明 推论2 2 7 如果树g 满足锦( g ) = o ( g ) ，且g 不是星图则 i m c ( g ) ；( g ) + 1 ，；( g ) + 2 证明设g 是满足锚( g ) = o ( g ) 的树，且g 不是星图则g 中存在顶点w 使得d o ( ”) 一锔( g ) ，且g ( ”) 0 ( ”) 0 由于覆盖0 ( ”) 中的所有顶点至少需要 1 1 ；( g ) 个导出匹配，则任意z g ( ”) 0 ( ”) 都不能被这a ( g ) 个导出匹配所覆 盖，即 m c ( g ) ；( g ) 结合定理2 2 6 可得， m c ( g ) 铋( g ) + 1 ，鑫( g ) + 2 ) 2 33 一正则无爪图的导出匹配覆盖 图g 称为无爪图，如果g 的任意一个导出子图均不与蜀。同构 图g 称为3 一正则无爪图，如果g 是无爪图，且对任意一个顶点”y ( g ) 都有d g ( u ) = 3 在这节中，g ，和仍定义为如下的图 g 1 g 2 引理2 3 1 设g 是3 一正则无爪图，且g 的每个分支均不与甄同构则g 有如下的性质： ( 1 ) 对于每一个”y ( g ) ，g g 或同构于g 。，或同构于g 。 ( 2 ) j y ( g ) j 是偶数 ( 3 ) 如果对于每一个”y ( g ) 而言，都有g 【g 同构于g 。则g 的每一 个顶点仅含于一个三角形 ( 4 ) e ( g ) 中的每一条边e ，或连接两个三角形，或含于某个三角形 证明由于g 是无爪图，且对任意”y ( g ) 有如( ”) = 3 ，故( 1 ) 成立 因为g 是3 一正则的，可以推出| e ( g ) l = ；| y ( g ) | 故( 2 ) 成立 如果g 中任意顶点”满足g k 同构于g 。，假设存在这样的一个顶点 ”y ( g ) ，满足”含于两个三角形由于d g ( ”) = 3 ，所以g k 同构于g 。与已 知矛盾故( 3 ) 成立 最后，由无爪图的定义和性质( 1 ) 可知( 4 ) 成立 这样，引理给出的四个性质就简单地证明完了 引理2 3 2 设g 是3 一正则无爪图如果g 中所有顶点”都满足g 【 k 蚓 同构于g ，则g 有偶数个独立的三角形 证明由引理2 3 1 可知，g 的每一个顶点均含于唯一一个三角形中，且 i y ( g ) l 是偶数由此可以推出g 有偶数个独立的三角形 引理2 3 3 ( b r o o k s 定理 1 】) 如果g 是连通图，且g 既非奇圈，也非完全 图，则x ( g ) ( g ) 定理2 3 4 设g 是3 一正则无爪图，且g 中所有顶点”都满足g g 同 构于g 1 则i m c ( g ) 2 ，3 ) 证明由引理2 3 2 可知，g 有偶数个独立的三角形，记为丑，正将每 一个三角形噩收缩为一个新的顶点砜，i = 1 ，t 得到的新图记为g 我们能 够观察到，g 7 是3 一正则的如果g 7 是一个完全图，容易验证对于原图g 而 言，i m c ( g ) = 2 否则，若g ，不是完全图，由引理2 33 可知，) ( ( g ) s ( g 7 ) = 3 因此，y ( g 7 ) 有一个3 一划分( ，) ，使得m 是独立集，待1 ，2 ，3 论断1 如果g 有完美匹配，则g 有3 一导出匹配覆盖 设m = e - ，e 。) 是g 7 的一个完美匹配令 ，( e 。) = ，。) ， ( e 。) = ，u 。) ， 1si n 这里，”。y ( g 7 ) 是由g 中三角形正。收缩而得的顶点，1sis 佗， 1 南s2 现在我们