（运筹学与控制论专业论文）图的导出匹配可扩性(1).pdf

中文摘要 肇眦j 9 本文所涉及的图均为无向、简单有限图。本文研究了图论中与图的导出匹配 可扩性有关的一些问题，由以下两部分组成： i 局部同构的连通的5 一正则无爪导出匹配可扩图的刻划 “单位区间图与循环图c 2 。( 1 ，掰) 的导出匹配可扩性 l 局部同构的连通的5 一正则无爪导出匹配可扩图的刻划 对边集m e ( g ) ，如果g 的任意顶点至多与m 中的一条边关联，则称m 是 g 的匹配称覆盖所有顶点的匹配为完美匹配我们称图g 的一个匹配m 为g 的 导出匹配，如果由材覆盖的点导出子图以m 为它的边集称图g 是导出匹配可 扩图，如果图g 的任一导出匹配都包含在它的一个完美匹配中称图g 是n 一可扩 图，如果图g 的任一有n 条边的匹配都包含在它的一个完美匹配中p l u r a r a c r 1 9 提出了n 一可扩性问题c a m e r o n 2 提出了导出匹配的概念，在文 2 6 中我们能 找到一般图、二部图、3 一正则图、4 - 正则图的导出匹配的一些性质1 9 9 8 年，原 晋江在 3 中提出了导出匹配可扩图的概念并研究了一些重要的性质在 1 6 中 刻画了连通的4 一正则无爪导出匹配可扩图杨帆和原晋江还在文 1 7 中证明了 2 n 个顶点的无爪图如果局部2 一连通，则一定是导出匹配可扩的受到他们的理 论的启发，本文第二章刻画了局部同构的连通的5 一正则无爪导出匹配可扩图并 得到了如下结果 定理1 1 局部同构于k 。u k 。的连通的5 一正则无爪导出匹配可扩图只有 k s k 2 定理1 2 局部连通但非2 一连通且局部同构的连通的5 - 正则无爪导出匹配 可扩图只有g 【k ：】，n 4 2 单位区间图与循环图c 2 。0 ，m ) 的导出匹配可扩性 l 浚五，五，五是实数辘上馥拜个攀整馥送滴定义蓬g 为：礞点集 ，( 国= 五，五， ；i 蠹蒸要( 谚= 五! l 喾歹，五n # 多 。遮撵撂到的 黧g 称为单位隧闻图送闽蹦肖很多独特的性痰。 称2 栉个顶点 y l ，弄2 ，x ：。的图为步长为i 和m 的循环图，记为岛。( 1 ，m ) 。如 果对于li - ji i ( m o d 2 n ) 或者ll 一，l ；埘( r o o d 2 n ) 的f 和j ，均有并l 嚣( 国 第兰章研究了单位区间图与循环图c 2 。( 1 拱) 的导出匹配可扩性。 图g 称为黼导出禚配爵扩前，蒋鹜g 的任何个支撑母露蚜为罨国嚣蘸埘扩 熬。 定理2 1 偶数个颚点的3 一连通单位区间图是强导出匹配可扩的 定瑗2 2 偶数个顶点的2 - 涟遥单位区间隔g 燕簿出逛毹可扩静当最仅当 辩匿s 鹣柽一2 一熹裁扭，谤，g 一粒，嵋) 。0 蹇溪2 3 疆数个顶点蘸2 - 遴逶单位篷溺强g 燕强导题配霹扩豹巍且仅 巍； ( 1 ) 对g 的任一2 一点割砸，v ，o ( g 一位，v ) ) = o 臣g - ( u ，q 恰脊两个禚分支 铖，g 。，使樽或者联锈) c 心( 每，谛) 或者联嚷) c 哦秘，v ) ： 穗) 甏g 最多毒秀个穗器熬2 一点裁莠董辫霭g 媾蓊个籀异2 一煮裁，赠 它磐3 互琴穗交。 寇凝2 。4 图g 。( 1 ，3 ) ，抖芑4 ，戆导出匹配可扩的 定理2 。5 图g 。( 1 弭一蛉，n 3 ，是爵出匹配可扩的 关键词；凿，罨出珏煞，导崮疆配爵扩蘅，无忝盈，循耀藤，蕈位遴阕隧，鼹舔 鬻饕。 2 a b s t r a c t g r a p h sc o n s i d e r e di nt h i st h e s i sa r ef i n i t e ，u n d i r e c t e da n ds i m p l e r o u g h l y s p e a k i n g , t h ep r o p e r t i e sw e a r ec o n c e r n e di nt h i st h e s i sa r e m a i n l y 雒f o l l o w s ： 1 c h a r a c t e r i z a t i o n so f l o c a l l yi s o m o r p h i c5 - r e g u l a r c l a w - f l e ec o n n e c t e d i m - e x t e n d a b l e g r a p h s 2 t h e i m e x t e n d a b i l i t y o f u n i t i n t e r v a lg r a p h sa n d c y c l i cg r a p h s c 2 。化m ) t h e o r g a n i z a t i o no f t h e t h e s i si s 髂f o l l o w s ：i nt h ef i r s tc h a p t e r , w el i s ts o m en o t a t i o n s a n di n t r o d u c es o m e t o p i c sa b o u tm a t c h i n gt h e o r ya n d t h ei n d u c e d m a t c h i n ge x t e n d a b l eg r a p h s i n t h es e c o n dc h a p t e r , w ep a m yc h a r a c t e r i z el o c a l l yi s o m o r p h i ca n d5 - r e g u l a rc l a w - f r e ec o n n e c t e d i m - e x t , n d a b l ；i nt h et h i r dc 岬m r , t h ei s e x m n d a b i l i t yo f u n i ti n m r v a l 霉印h sa n dc y c l eg r a p h s c 2 ( 1 ，m ) a r e p r e s e n t e d c h a r a c t e r i z a t i o n so f l o c a l l yi s o m o r p h i c a n d 5 - r e g u l a r c l a w - f r e e c o n n e c t e di m - e x t e n d a b l e g r a p h s m 量e ( g ) i sam a t c h i n go fg ，i fy ( e ) n v ( f ) = 妒f o re v e r yt w od i s t i n c t e d g e se ，f m i f a m a t c h i n g c o v e i 苫a l l t h ev e r t i c e so fg ，w ec a l l t h e m a t c h i n ga p e r f e c tm a t c h i n go fg am a t c h i n gm o fgi si n d u c e d ，i fe ( 矿( m ) ) = m a g r a p hgi si n d u c e dm a t c h i n ge x t e n d a b l e ( s h o r t l y , i m , e x t e n d a b l e ) ，i fe v e r y i n d u c e d m a t c h i n g o fgi si n c l u d e di nap e r f e c tm a t c h i n go fg g r a p hgi s n 。e x t e n d a b l e i fgh a sam a t c h i n go fs i z ena n de v e r ys u c hm a t c h i n ge x t e n d st o ( i e i sas u b s e t o f ) ap e r f e c tm a t c h i n g i ng s i n c ep l u m m e r 【1 9 】r a i s e dt h ep r o b l e m o f n e x t e n d a b i h t y , m a n yr e s u l t s i nt h i sa s p e c ta p p e a r 【6 ，7 ，8 ，1 9 c a m e r o ng a v et h e c o n c e p to f i n d u c e dm a t c h i n gi n 2 】s o m ef u n d a m e n t a lr e s u l t so n i n d u c e dm a t c h i n g c a nb ef o u n di n 【2 ，4 ，5 】i n1 9 9 8 ，y u a n 【3 】d e f i n e dt h ei n d u c e dm a t c h i n g e x t e n d a b l e g r a p h s ，s h o r t l y , i m e x t e n d a b l eg r a p h s ，a n dc h a r a c t e r i z e dt h e mp a r t l y m o t i v a t e db y t h e i rt h e o r y , w e g e t t h ef o l l o w i n gr e s u l t s ： t h e o r e m 1 1 s u p p o s e t h a tgi sc o n n e c t e da n di m e x t e n d a b l e - i f gi sl o c a l l y 一一 i s o r n o r p h i c t o 鹄u 致* 5 一r e g a t a ra n dc l a w - f l e e , 妇n8i s i s o m o r p h c 撼 墨憨 t h e o r e m1 2s u p p o s et h 髓gi sc o n n e c t e d a n d1 m - e x t e n d a b l eb u ti sn o t l o c a l l y 参c 删婚燃。疆gi s 赫蹴移i 撒喇岛幻e 砖坶黼渊s 谨瞎妇蝴蕊旃黼 强融gi s i s o m o r p h i c t o q 涨2 】f o r 嚣4 ， 鞠ei m - e x t e n d a b l l t t yo fu n i ti n t e r v a l g r a p h s a n dc y c l i c g r a p h s 岛。德麟 融磊，五，蠢b e 黠c l o s e i r 妞r v a l s o n a l i n e , t h e v e r t e x 娥则婚瞅 躁a r e d e f i n e d , 举t i v c i g 姆 矿鼢= 文，矗，五 ；联饿* 磊6 ；l 尊，点 弓拳爹 。 t h e n g r a p hgi sc a l l e d # r e f i ti n m , v a lg r a p h w ew i l ld e n o t e b y 镄# 毽蝴t h ec 榉托g r a p h w i t h2 嚣蛐船而，镌，一， i n w h i c h ￥ji s 钮链簧o f i t i f e i 惫e r i - j 酾融i n ) 材 卜歹 靴( m o d 孙， 、 t h e o r e m2 1i f a - m t i ti n t e r v a lg r a p h w i t h 鞭谚 e v e ni s3 - c o n n e c t s , t h e n gi ss 1 1 , o n g l yi m - e x t e n d a b t e 。 t h e o r e m 五2a2 - e o n n e c t e du n i ti n t e r v a l g r a p h gw i t h 】y ( g ) 1e v e ni s 琢蟊蘸蕾e 醚蛹。谨蠲d 蛾i f f o r a 2 - v e x t e x 蹦承，啼o fg ，o 帮一如，v ) ；0 t h e o r e m 盘尊a2 - 。o t m e e t e du n i ti m 蝴r a lg r a p h 群w i t h y 0 醋) e 擎e ni s s t r o n g l y i m - e x t c n 娃b l e 避嚣证o n 酶, i f l f o r 蓬2 蠼糕蘸c u t 秘，峪o fg ，口簿一参，礤= 0 a n dg - 缸砖蛾s j 毽蟪 柳话寿键靛硼拎敬建蜒q ，嚷，s u c ht h a t 蛙醴矿馥cn o ( u ，磅) 倦 矿( 敛 o a k ( 泓砖； 一4 一 ( 2 ) gh a s a tm o s tt w od i s t i n c t2 - v e r t e xc u t s a n di fgh a st w od i s t i n c t 2 - v e r t e xc u t s ，t h e n t h e y a r e d i s j o i n t ， t h e o r e m2 4 c 2 。( 1 ，3 ) f o r n 4i sd d e x t e n d a b l e t h e o r e m2 5 c 2 。( 1 ，h 一1 ) f o r n 3i s 跏- e x t e n d a b l e k e yw o r d s ：g r a p h ，i n d u c e dm a t c h i n g ，m - e x t e n d a b l eg r a p h s ，c l a w - f r e eg r a p h ， c y c l i cg r a p h , u n i t i n t e r v a lg r a p h ，l o c a l l yi s o m o r p h i c s 一 第一章引论 在这一章里，我们简单地回顾一下匹配问题的历史背景，介绍导出匹配问题 的主要研究课题第一节介绍匹配理论；第二节列出本文中用到的主要术语和记 号；第三节列出导出匹配可扩图的主要已知结果 1 1 匹配理论的应用背景 匹配理论是图论的一个中心研究课题它不仅有应用背景的支持，还包含着 一系列相当丰富的理论问题尤其是最近几十年，对组合论中很多重要领域的发 展起了很大的作用因此，这个课题始终吸引着图论、组合最优化等学科领域的众 多工作者投身于它的研究中 我们知道许多实际问题均可转化为匹配问题匹配理论在线性规划、组合最 优化及排序论中有很广泛的理论和实际应用背景在一些实际应用问题中，比如 婚配问题，我们有撑个男孩子和撑个女孩子，希望他们结为作对夫妻当然一个女 孩子只能和她认识的一个男孩子结婚，这可以转化为一个二部图g = 口，占) 描述 如下：4 是万个男孩子的集合，曰是n 个女孩子的集合，4 中的一个顶点与曰中的 一个顶点相邻当且仅当他们互相认识这个问豚属于完美匹配问题f o r b e n i u s 2 0 给出了对v 七，l 七s 雅，若七个男孩子至少认识k 个女孩子，则婚配问题是有解 的 婚配理论是著名的h a l l 理论 2 1 的前身h a l l 定理给出了偶国有完美匹配的 充分必要条件对于非偶图，t u t t e 和l o v a s z 9 ，2 1 刻划了一般图( 非偶图) 有完 美匹配的条件k u l m 和h a l l 首次给出了在一个偶图中寻找完美匹配的算法几乎 同时，f o r d 和f u l k e r s o n 发表了第一篇关于网络流理论的文章e d m o n d s 在1 9 6 5 年首次给出了一般图的多项式时间匹配算法 p l u m m e r 1 9 中引入了开一可扩的概念设正整数p 和一满足n s 兰i ，称p 二 个顶点的图g 是n 一可扩图，如果图g 有一个边数为n 的匹配且所有的n 匹配都可 扩充为图g 的一个完美匹配很显然，如果图g 是2 - - 临界的( 在一个图g 中任取 两个楣异顶点 ，v ，若g 一越一v 有完美匹配，则称图g 是2 - - 临界图) ，则图g 是 l 霹扩豹。勇努，懿采鹜g 是2 一可扩瀚，粥它不是偶图就是2 一临界的由此可见 匹配可扩阕题的重要性和趣喙性。 二十世纪五十年代晚期，k o t z i g 6 ，7 开始研究有完美匹配的图的分解问题， 不宰静是，因为逡些文章是在s l o v a k 发表韵，它们没有得到应有的重褫。二卡世纪 六十年代初期，g 毡l l a i 1 0 和e d m o n d s 1 1 分爨提出图的最大匹配分孵阃题但是 当研究的图有完荧匹配时，出现了退化情形k o t z i g ，l o v a s z 和一些后继者对这类 图穗经存在的正规分解有了更好酶骈究并强分解出的图属于2 临界图类 鼹晋江在 3 3 孛提出了导掇匹配可扩圉 蠡题如果一令筵单图g 熊任意一个 导出匹配均可扩充为圈g 的一个完美匹配，则称阁g 是婚出匹配可扩的注意到 导国医配阿扩圈一定燕1 一可扩圈，因既一个圈的导出莲配可护性可l ；盂看作避n 一霹扩溺题的变形。我们知道l 一可扩性在纯学图论中有霪要的应用，嚣导出匹配 可扩图的引入是1 一可扩图的另一个发展 我们知道找一个黉的最大匹配怒有多项式时间算法的可c a m e r o n 在 2 中 证甥了寻找一令二帮图的最大导出匹配阊鼹是p 一完全熬。因此导漱匹配闻题 与胆一可扩问题尽管相似，但鞭困难的多实际上，杨帆和原晋泼在 1 8 中证明了 导出匹配问题是c o - - l q p - - 完全的这个领域的很多问题还没有解决 下面我们会绥本文的主要缝论。在局部嚣构条件下裁裁了连通的歪则无瓜 导出匹配可扩图对于单位区间图给出了强导出甄配可扩的充疆条件证明了循 环网c ：。( 1 ，3 ) 和g 。( 1 ，n - i ) 的释出匹配可扩性 1 2 术语察记号 在这一节中，我们主要夯缀术语和记号。详细参考 1 】+ 所有靛图均为簧单、有 限无向图对一个图g ，矿( g ) 和e ( g ) 分别表示图g 的顶点集和边集个顶点所 关联的边的数目称为顶点“的度，记为a ( u ) 占( g ) 一m i n d g 0 ) ：“矿( g ) ) 是圈g 的最小度 ( g ) = m a x a 6 ( “) ：“er ( 6 3 是阐g 的最大度- 顶点集s 三矿( 国称为g 的独溉集，若s 中经意两点都不稠邻 口( g ) = m a x f s ：s 矿( g ) 是g 的独立集 是图的独立数 图g 的分支数和奇分支数分别记为c ( g ) y f t jo ( g ) 一个子集互矿( g ) 的邻集记为 。( 石) ，定义为 n o ( x ) = y y ( g ) x ：g - 在x x ，x y 昱( g ) 对顶点集s y ( g ) ，令 e ( s ) = 鲫联g ) ：“，v 研 对m s g ( g ) ，令 v ( m ) = v g ( g ) ：存在工g ( g ) ，啊m 设m 妄e ( g ) ，着对任意不同的边e ，f m ，v ( e ) n y ( ，) = ，则称m 是图 g 的一个匹配若匹配m 满足矿似) = 矿( g ) ，则称m 是图g 的完美匹配若匹配 肼满足e ( 矿( ) ) = m ，则称m 是图g 的导出匹配若图g 的每一个导出g s l - d 均 可扩充为图g 的完美匹配。则称图g 为导出匹配可扩图显然，导出匹配可扩图的 顶点数必为偶数若图g 的任一支撑母图是导出匹配可扩的，则称圈g 是强导出 匹配可扩的 简单图g 和的乘积图记为g 口，定义为：顶点集v ( g x 日) = g ( g ) x 矿( 日) ， 而顶点( “，v ) 与( “，v ) 相邻当且仅当砧= 甜r w e ( 月) 或者v = v r u u e ( g ) 简单图g 和日的结合图记为g t h ，定义为：顶点集v ( g c h ) = g ( g ) x y ( 日) ， 面顶点q ，与m ，v ) 相邻当且仅u u g e ( g ) 或者扯= “且w e ( h ) ( 即将图 g 中的每个顶点均换为日) 对顶点集s 矿( g ) ，s 的导出子图记为g s 】，定义为：顶点集s ，边集 g ( s ) = l n e ( g ) ：”，v s 一个连通图g 称为局部连通的，若对任意“矿( g ) g 。( “) 】是连通的一个 连通图g 称为局部2 一连通的，若对任意“矿( g ) ，g i n g “) 是2 一连通的 不含量。，作为导出子图的图称为无爪图 1 。3 导出匹配可扩图的一些已知结论 本节我们列出导出匹配可扩图的一些已知结果 图g 的围长记为g ( g ) 是图g 中最短圈的长度 定理1 1 3 若图g 是连通的导出匹配可扩图且f 矿( g ) f 4 ，则g ( g ) 4 定理1 2 3 若图g 是2 一个顶点的连通的导出匹配可扩图，则 i e c g ) 2 孙- 2 ，等式戒立的充要条件是g 兰? x 蜀，其中t 是任意一棵撑个顶点 的树 称2 h 个顶点五，屯，屯。的图为步长为l 和m 的循环图，记为c z 。( 1 ，卅) 如 果对于ii - jja 1 ( m o d 2 n ) 或者jf 一jg m ( m o d 2 n ) 的j 和_ ，均有五j ，层( g ) 定理1 3 3 连通的3 一正则导出匹配可扩图只有qx k ：( n 3 ) 和 c 2 。( 1 ，h ) ( n 2 ) 定理1 4 2 3 不能收缩为k 。的连通图g 是导出匹配可扩的当且仅当 g 兰t x k ：。其中r 是任意一棵再个顶点的树 定理1 5 2 3 唯一的导出匹配可扩的外平面图是梯子只足： 定理1 6 1 2 4 若图g 是无爪图，则v 石ey ( g ) ，n e ( 曲只有以下三种情形： ( 1 ) 若g 【。( z ) 】不连通，则n 。( x ) 是两个顶点不交的团： ( 2 ) 若g 【。( 堋连通度为1 ，则。( 曲被两个顶点不交的团覆盖，并且连接两 个团的所有边都交于其中一个团中的一个公共顶点： ( 3 ) 若g g ( 功】是七一连通的且七2 ，则g 【g ( x ) 是h a m i l t o n 一图 定理1 7 1 6 连通的4 一正则无爪导出匹配可扩图只有c ；，瑶和霉，r 2 其中是有4 r 个顶点“j ，v f ，_ ，y l ( 1 i r ) 的图，r x , j 1 i r ，如j ，v f ，而，y j ) 是一个团，x t n “1 ，) ，l v m 昱( t ) ( m o d r ) 定理1 8 1 1 7 设图g 是2 n 个顶点的无爪图若图g 的最小度大于等于 2 l 量l + 1 ，则图g 是导出匹配可扩的 定理1 9 1 7 设图g 照2 n 个顶点的无爪图若图g 是局部2 一连通的。则 圈g 是导出匹配可扩的 定理1 1 0 1 7 设图g 是勃个顶点驰无瓜图若图g 是k 芷则驰旦k 难， 则阌g 悬导出改配可扩的 设j ，以，以是实数轴上的靠个单位闭区间，定义图g 为：顶点集 r ( g ) = 五，五，以 ；边寨富( g ) = 五lf j ，五n 歹，簪 这样得到瓣匿 g 称秀摹位区瓣蛰。 图g 的一个标号，是一个双射f ：矿( g ) 峥 1 ，2 ，i v ( g ) i ) 。 若，是图g 的一个标号且使得对任意的1 9 i 】是图g 一矿( m ) 的奇分支，与图g 的导出匹配可扩性矛盾 情形2 2 g a , b , c , d ，p ) 】同构于局u 丘 卜 。茹k 渺 淄e 畦 k 拦 不妨设g 【 a , b ，c ，d 】是一个4 一团则仿上可证a ( 4 ) n g 0 ) = 庐，进而得 到 g ( a , b ，c ，d ) ) n g ( 8 ) = 爹 由局部同构性，必有 o k ( a , b ，c ，d ) ) “，v ，x ，y ) 且口口，b a ，c a ，d a e ( g ) 令m = 伽，z e ) 则是图g 的一个导出匹配但gf ，y j ，y ，b ，c ，d ) 】是图 g v ( m ) 的奇分支，与图g 的导出匹配可扩性矛盾 情形3 口( g 【 口。6 c ，d ，8 ) 】) = 1 2 艟i簿 降、p “ il t 馥“k 蕾丑g，文霹 在g a , b ，c ，d ，8 ) 中任二点之间有边相连，故同构与足；由图g 的5 - - 正则 性及连通性，图g 同构于足，k ：口 2 。2 局部连通但非2 一连通且局部同构的连通的5 一正则无爪导出匹 配可扩图的刻划 上一节我们刻划了局部同构于k 。u e 的连通的5 一正则无爪导出匹配可扩 图由文 1 7 ，局部k 一连通( 七2 ) 的5 - 正则无爪图均为导出匹配可扩的，所以我 们只需要再刻划局部连通但非2 一连通且局部同构的连通的5 一正则无爪导出匹 配可扩图 简单图g 和日的结合图记为g 日】，定义为：顶点集y ( g h 】) = y ( g ) y ( 日) ， 而顶点 ，u ) 与( v ，v ) 相邻当且仅当渊g ( g ) 或者“= u g v v e ( h ) ( 即将图 g 中的每个顶点均换为日) 定理2 7 图e 疋 ，n 4 是导出匹配可扩的 证明不失一般性，设图e 【如】的顶点集和边集分别为： 矿； “l ，“2 ，u 。，v l ，v 2 ，v ) ， 五= 群f v f ，u i v i + 1 ，u l + l v l ，u l + l v m1 1 s i s 靠( r o o d n ) 设s ( f ，f + d = “f ，“l + i ，u ，v i + l ，则g s o ，f + 1 ) 】晕k 设m 是图c 【置：】的一个导 出匹配ve m ，jk ，y c s ( k ，k + 1 ) 我们令也= 协u e ( s ( k ，k + 1 ) 矿( ) ， 则= u 。m 是图e 隧：】的一个包含m 的匹配在图e 【足：卜矿( ) 中取出所 有边“。v 。便构成q 瞵：卜矿( 忉的一个完美匹配f 而u f 便是图e 【足z 】中包 含m 的一个完美匹配口 定理2 8 局部连通但非2 一连通且局部同构的连通的5 - 正则无爪导出匹配 可扩图只有e 2 】，l 4 证明 设g 是一个局部连通但非2 - - 连通且局部同构的连通的5 - 正则无爪 导出匹配可扩图由导出匹配可扩图的定义及t u t t e 定理，任取g 的一个导出匹 配m ，g y ( m ) 没有奇分支对图g 的一个顶点“，定义，( “) = ie ( n g ( u ) ) i 论断1 v w e 矿( g ) ，5 ，( w ) 7 若v “v ( g ) ，f ( u ) 4 ，则g 【。( “) 不连通或者含有3 个顶点的独立集，与 图g 是局部连通的无爪图矛盾又因为图g 不是局部2 一连通的，所以，( w ) 7 我们分如下情形讨论： 情形1v “矿( g ) ，f ( u ) = 5 图i图2 由图g 的无爪性、局部非2 一连通性及引理2 2 ，g 【g ( “) 】同构于蜀u k ：+ e 设g 0 ) = v ，w x ，y ，z ) ， v ，w x ) 为3 一团， y ，z ) 为2 一团且w y e ( n g ) ) 并设n g ( v ) “，w , x ) = a , b ) 由5 一正则性及gi n g ( v ) 】兰gi n 6 ( “) 】的性 质，a b e ( g ( v ) ，r a ，b 中恰好有一个顶点和w ，工中的一个顶点相邻由d 。b 的对称性，不妨设口和w ，工中的一个顶点相邻若a 与w 相邻，如图i 此时 n 。( w ) = “，v ，x ，y ，a ) ，且，( w ) = 5 但g i n 。( w ) 】不同构于如u k ：+ p ，与局部 同构性矛盾若a 与x 相邻，如图2 设。( x ) 群，v ，w ，口) = 砖则口与f 必相邻 设疗( d ) v ，x ，b ，c ) = 扣) 由，( 口) = 5 及5 一正则性与b ，c 均相邻此时 g 【。( 口) 1 不同构于k ，u k ：+ e ，与局部同构性矛盾所以这种情形不会发生 情形2 v u y ( g ) ，( “) = 6 由图g 的无爪性、局部非2 - 连通性及引理2 2 ，g 【。 ) 或者同构于 k 3 u k 2 + e l + e 2 ，且q 与e 2 交与k 2 中的一个顶点：或者同构于如w k 2 + e i + e 2 ， 且e 。与e ：交与甄中的一个顶点。 情形2 1 g 【n a ( 甜) 】同构于足，u 足：+ 岛+ 8 ：，1 l e l 与巳交与足2 中的一个顶 点 设心 ) = v ，w , x ，y ，z ) ，( v ，w ) 构成2 一团， 工，y ，z ) 构成3 一团，且 w ，v y e ( n a 0 ) ) 此时在n a ( 中，“，石，_ y 已构成3 一团由局部同构性及 w “e ( 心( v ) ) ，w 必和善，y 中的一个顶点相邻，但这与，0 ) = 6 相矛盾故这种 情形也不会发生 情形2 2g 6 ) 】同构于蜀u 置2 + 毛+ 口2 ，且q 与口2 交与墨中的一个顶 点 此时，图g 的任何一个顶点均在一个4 - - 团( 4 个顶点的团) 中我们有 论断2 对g 的任一个4 - - 团s 。i g ( s ) i = 4 设s = “。，v ，。，v “。) 是图g 的一个4 一团，n o ( u t ) 叶，“f + l ，v “- = 舡“，坼一) 由图g 的5 - - 正则性及局部同构性u ，“。，v 。中有且仅有一个顶点和“。，y 。均相 邻，不妨设为v ，设n o ( u 。) 扣，v ，v 。 - 伽。，v 。) 则伽。，v 。) n 缸。：，v 。) = 庐 否则矛盾于局部同构性， 记g ( 伽j + 2 ，v f + 2 ) ) “，v f + i ) = 伽m ，v m ) ，n g ( 恤f - l ，v h ) ) “f ，v f ) = 伽f _ 2 ，v i 2 ) 对任意的正整数r ，记n 。( “。，v 。，) ) 缸i - r + lv 。+ 。) = 似i - r - i ) v 。一。) 因为图g 是有 限图，故一定存在正整数p ，g ，使得g ( 协f 州”却) ) 扣i + p - i ) 。却一。) = 伽相，。h ) 令 ，l = p + g + 1 ，此时图g 同构于q 【k 2 ，n 2 4 情形3 v u y ( g ) ，f ( u ) = 7 一 由图g 的无爪性、局部非2 一连通性及引理2 2 ，g 【n a ( n ) 同构于k u k 。+ e 设g m ) = v ，w ，五y ，z ) ， v ，w , x ，y ) 构成4 一团，g v z e ( n a ) ) 又设g 0 ) 似，v = 和，6 ，c 则材， ，与a ，6 ，c 之间无边相连从而厂( z ) 4 这与，( ：) = 7 的假设相矛盾所以此种情形也不会发生口 第三章单位区间图与循环图的导出匹配可扩性 在邀一章我俯圭蕊讨论单位醒闷萄的导出隧配可扩性与连通度的关系以及 德繇圈的导出涎嚣蔼扩悭本掌结构如下： 在3 。t 节我们主要研究了3 一连通单位区间豳的强导出腿配可扩性及2 一连 通单位区间圈是导出躁配可扩图及强导出匹配可扩图的充要条件：猩3 2 节主要 讨论循螺强g 。g ，3 ) 嚣g 。( 1 ，- d 豹导出遁醚霹扩往 3 。l 单位区阉图的导出救瓤可扩性 设以，以，以是实数轴上的n 个单位闭区间，定义图g 为：顶点集 矿( g ) = f ，如，以) ：边集e ( g ) = 以lf 譬，山n 喾) 这样得到的 胬g 称为单位区闯胬。区间圈有穰多独特酌佳藤 黧g 熬一个稼弩，是令双赫f ：v ( 0 3 哼 i ，2 ， 矿谚 。 蓍，是图g 菸一个标号傻褥辩任意鹩l f 褥l ，当，。专，“歹) 程g 审棱邻辩，芗魏秀= v 联g ) | ，秘，是圈g 翦个霞，裂穆，是墅 g 麴一个正则标号。 图g 称为强导出匹配可扩的，若图g 的任何个支撑母踊均为导出匹配可扩 懿。壶蹲鑫疆聚嚣扩黟强譬密匿聚霹扩瀚定爻，强导密匹配龌扩菡定是导窭医 配蘑扩篷，但替凄匹配可扩攫不一定是强导出致配可扩蕊。咧翔：竞全偶凰藏。是 导出爨配可扩灼，但不是强导出躁配可扩的 引理3 1 2 1 j m j t t e 定理)圉g 有一个完美莲配警量仅溺辩任予巢 s 亡y ( g ) ，o ( g s ls l ，其串日) 是苴靛奇分支数。 羲谂3 2 鏊g 是导邈莲酝冒扩靛逛曼纹巍对窝g 熬鲣一导班莲嚣型彝程 子集s c 矿( g ) 矿( 拟) ，口( g 一矿c 妊) 妁蔓! si 引理3 3 ( 2 5 图g 是单位区间图当且仅强国g 存在砥则标号 引理3 4 1 2 5 糟图g 是七一逑通的单位区间图， 矿( g ) j = n ，则露s g 由弓i 理3 4 立即得到下列引理： 零l 纛3 5 偶数个顶点鹣连逶攀位区鬻整一迤有完美莲配。 称矿( g ) 的个予集s 为图g 的一个夕子集，若媛s 】豹每个分支均周构于 墨或由强导出匹配可扩图的定义，圈g 是强导出贩配可扩的充分必要条件 悬对图g 的任偶数个顶点的夕一子集s ，g s 有完美逛配。 定理3 6 偶数个顶点的3 一连通单饿区间图是强导出匹配可扩的 诞赘设鬻g 兔一个藕数个顶点的3 一连逶肇位醛阍瑟爨弓l 慈3 。3 ，g 存在 一个歪烈标号，楚得对任塞戆1 i j s | y 簸) | ，当，“国与，。( 歹) 在g 孛相邻 慰，y ( i ，j ) = y 矿 使褥 f ( x a f ( x j ) 由予，是g 瓣歪剩标号，簸慰 ￥封矿( g ) ，vp y ( g ，) 骞，釉 f 。 不妨设q ，q ，色按标号从小到大排列，即v 甜g y ( 毽) ，vv e y ( g l + ，) 均有 ，( “) 八设x 芒矿( g i ) 为g | 中标号最大的顶点，y y ( g 2 ) 为g 2 巾标号最小的 顶点由图g 的3 一连通性，( 曲+ 3 ，( 蝴从而3 个在标号，下相继的顶点 f q ( 厂( 曲+ 1 ，( 功+ 。2 ，( 曲+ 3 ) ) z ，矛盾 设灯是g 的一个支撑母图任取日的一个导出匹配m 则矿似) 是g 的偶数 个顶点的多一予集且矿( 掰) 中不含在标号，下相继的3 个顶点。由论断，v ( m ) t g 是g 的点割集从而g v ( m ) 是偶数个顶点的连通单位区间图，有完美匹配又 因为g y ) 是一v ( m ) 的支撑予图，所以h 一矿( m ) 也有完美匹配口 定理3 7 偶数个顶点的2 一连通单位区间图g 是导出匹配可扩的当且仅当 对图g 的任一2 一点割恤，v ) ，o ( g 一似，n ) = 0 证明设图g 为一个偶数个顶点的2 一连通单位区间图由引理3 3 ，g 存在 一个正则标号，使得对任意的i s i ，iy ( g ) l ，当f - 1 ( f ) 与，j 1 ( j ) 在g 中相邻 时，v ( i ，- ，) = y v ( g ) if s ，( v ) _ ，) 是图g 的一个团我们以下的证明是在g 的 正则标号，下进行 论断g 的任何一个不含2 个在标号，下相继的顶点的顶点子集一定不是 点割集 若不然，设x 是g 的不含2 个在标号，下相继的顶点的点割集，并设g z 含2 个分支，分别记为g l ，g 2 不妨设g l ，g 2 按标号从小到大排列设工y ( g 1 ) 为g 中标号最大的点，y v ( g ：) 为g ：中标号最小的点由图g 的2 - - 连通 性，( 工) + 2 厂) 从而2 个在标号厂下相继的顶点 f 1 ( u o ) + 1 。，( 功+ 2 ) ) s x ，矛盾 必要性 若g 存在一个2 一点割伽，v ) ，使得o ( g - 协，v ) ) 0 ，则鲫e ( g ) 令 m = ”v ) 则m 是g 的一个导出匹配但g y ) 有奇分支，这与g 是导出匹配 可扩图矛盾 充分性 任取g 的一个导出匹配m 若矿( m ) 不含g 的相继2 - - 点割则g y ) 是 偶数个顶点的连通单位区间图，有完美匹配：若矿( m ) 含g 的相继2 - - 点割因为 对图g 的任一2 - - 点割似v ) ，o ( g 一舡，v ) ) = 0 故g 一矿( m ) 是n 个偶分支的并，从 而g y ( m ) 有完美匹配口 定理3 8 偶数个顶点的2 一连通单位区间图g 是强导出匹配可扩的当且仅 当： ( 1 ) 对g 的任一2 - - 点割似，v ，o ( g 一恤，v ) ) = 0 j i g 一伽，v ) 恰有两个偶分支 g i ，g z ，使得或者矿( g 。) c = - n o ( u ，v ) ) 或者矿( g ：) c n o ( u ，订) ： ( 2 ) 图g 最多有两个相异的2 一点割并且若图g 恰有两个相异2 - 点割，则 它们互不相交 证明设图g 为一个偶数个顶点的2 一连通单位区间图由引理3 3 ，g 存在 一个正则标号，使得对任意的i i c 心( 秘；，鼍 ) ，矿( 瓯) c n o ( u ：，毪) 。诧时，毽，啦为突全图，且 y 锈) n y ( 髓) = 多，矿( 龟) n y 澎) = 多，g 中不含毒2 一点割。从蔼 谚一矿e 材) 、托，鼍，群2 ，也) 为镁数个璜点的连通单位区阋圈这样，g 一矿( 肘) 的任 一分支均为偶数个顶点的连通单位区间图，有完美匹配又因为g - v ) 是 盯一矿( 肼) 的支撑子图，从i 耐嚣一y c 材) 有完美匹配口 3 2 循环图的导出匹配可扩性 称2 h 个顶点墨，z ：，工：。的图为步长为1 和搬的循环图，记为c 2 ( 1 ，嬲) 如 果对于ji - js l ( m o d 2 n ) 或者f i - ，f ；m ( m o d 2 n ) 的f 和，均有x 一，e ( g ) 原晋江在 3 中证明了循环图c 2 。( 1 ，n ) ，n 2 是3 - - 正则的导出匹配可扩图受他 的理论的启发，本节主要证明了4 一正则的循环图c 2 。( 1 ，3 ) ，n 4 和 c ：。( 1 ，n - 1 ) ，n 3 的导出匹配可扩性 定理3 9 c 2 。“3 ) ，n 4 是导出匹配可扩的 证明不失一般性，设c 2 。( 1 ，3 ) ，n 4 的顶点集和边集分别为： v = x f ：i z 2 。， e = x f x ：1 s f 任取c 2 。0 ，3 ) ，n 4 的一个导出匹配m ，把m 中的边分成如下四种； 互= 而e 肘：f 是奇数且，一i ；l ， e 2 = 工i - 仨m ：i 是偶数且7 一i = 1 ) ， e 3 = x f - m ：f 是奇数且j i ；3 ) ， e 4 = 置x je m ：f 是偶数且j i = 3 ) 任意的边x r 七层，我们定义顶点集矿的子集s 如算，) 如下： s ( 工2 x 2 1 ) = x 2 i - 1 ，x 2 ， ， s ( x 2 j x 2 i + 1 ) ； 工2 卜l ，x 2 1 , x 2 1 + 1x 2 “2 ) ， s ( x 2 f 1 屯i