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

中文摘翼 本文所涉及到的图均是有限的，无向的，简单图本文主要以下几部分组成 1 直径为2 的无爪图的导出匹配可扩性 2 结合图的导出匹配可扩性 32 n 个点3 n - 1 条边的导出匹配可扩性的刻划 4 2 n 个点3 n 条边的导出匹配可扩性的刻划 5 树的平方图的导出匹配可扩性的刻划 如果边集m e ( g ) 中的任意两条边都没有公共的端点，那么就称边集m 是图g 的 一个匹配。如果图g 的一个匹配m 覆盖了它的所有的顶点，那么称这个匹配为图g 的 一个完美匹配如果g 的匹配m 中的任两条边不相邻，则称m 为导出的如果一个图 g 的任一个导出匹配都包含在它的一个完美匹配里，我们称图g 为导出匹配可扩的。 1 燕径为2 的琵凰嘲的导出匹配可扩牲 如果图g 不包含k 1 , 3 这样的导出子图，则称它为无爪图如果点“和”在g 中是连 通的，则u 和u 的距离d c ( u ，。) 定义为 b l 和 之间最短路的长度。如果图g 中任意两点 间的最大距离为r ，就称图g 的直径为r 在这一部分首先刻划了直径为2 的无爪图是 导出匹配可扩的充分必要条件，进而，给出了判定一个直径为2 的无爪图是导出匹配可 扩的的一个多项式时问算法 定理1 1 假设g 是一个直径为2 的无爪图，m = 知1 “2 ，“。珥。) 是g 的一个 导出匹配且满足g v ( m ) 不连通，则l m s 3 定理1 2 直径为2 的无爪图g 是导出处匹配可扩的充分必要条件是对任意的g 的导 出匹配l m i 3 ，g v ( u ) 没有奇分支 算法1 3 直径为2 的无爪图的导出匹配可扩性的判定 第一步，任取满足j m f 3 的边集m e ( g ) ，判断m 是否是g 的导出匹配并生 成集合m = m e ( g ) im 是g 的一个满足i m is3 的导出匹配) 。 第二步：如果m = 0 ，则终止；g 是导出匹配可扩性的否则，转第三步。 第三步：任取m 朋并生成g v ( m ) 第四步： 如果g v ( m ) 有奇分支，则终止；g 是导出匹配不可扩的。否则，g v ( m ) 没有奇分支，令 朋：= 朋 吖 ， 转第二步。 定理1 4 对于给定的直径为2 的无爪图g ，上述算法能在o ( n e 3 ) 时间内判断出g 是 否为导出匹配可扩的。 2 。结合闰的爵如匹配可扩性 图g 和日的结合图g h 】的点集为v ( v ) y ( 日) ，其中( u ，”) 和“，”相邻的充分必要 条件是u “e ( c ) 或者“= “并且 e ( h ) 在这一部分，刻划了结合图的导出匹配可扩性证明了结合图c h 1 是导出匹配可扩 的如果图g 和日都是平凡的，g 连通并且g 和仃满足下列条件之一： ( 1 ) g 和日中有一个是导出匹配可扩的 ( 2 ) a 和日都有完美匹配； ( 3 ) g 和日中一个是非平凡的并且有几乎完美匹配，另一个有完美匹配 定理2 1 如果g 和日中有一个是导出匹配可扩的，那么g 明是导出匹配可扩的。 定理2 2 如果g 和日都有完美匹配，那么c h 】是导出匹配可扩的。 定理2 , 3 如果g 有完美匹配，h 是非平凡的并且有几乎完美匹配，那么g i n l 是导 出匹配可扩的。 定理2 4 如果g 是非平凡的并且有几乎完美匹配，日有完美匹配，那么c h 是导 出匹配可扩的 3 2 n 个点3 n - 1 条边的导出匹配可扩性的刻划 图t 和日的乘积图t h 的点集为v ( t ) y ( 日) ，其中( “， ) 和u ，相邻的充分必 要条件是u = z ，v y e ( h ) 或者口= y ，n 。e ( t ) 。 如果h = j 如，t j 幻定义为 v ( t 尬) = x i ：x v ( t ) ，i = l ，2 ) 并且 e ( t xk 2 ) = x l x 2 ：ze y 【t ) ) u g z i y i ：x y e ( t ) ， = i ，2 ) 对于待1 ，2 ，由 砧：z v ( t ) ) 导出的图t k 2 的子图，记为正，称为t 的第i 个拷 贝。x i 表示噩中的点，它对应于t 中的点z 具有2 n 个点3 n 一1 条边的图被称为是( 2 n ，3 n 一1 ) 优的，如果日同构于t 鲍+ e 其中t 是任意一棵有n 个顶点的树，e 是t k 2 中的一条连接t 的两个不同拷贝且距 离为3 的边k f 3 表示从甄3 删去一边得到的图。 在 3 3 】中，原晋江老师证明了2 n 个点的连通的导出匹配可扩图至少有3 n 一2 条边，并 且具有2 n 个点3 n 一2 条边的导出匹配可扩图只能是t k 2 ，其中? 是任意一个n 顶点 2 的树。在这一部分，证明了2 n 6 个点3 n 一2 条边的导出匹配可扩图只能是t 憨+ e ， 其中t 是任意一个有n 3 个顶点的树，e 是t k 2 中一条连接t 的两个不同拷贝且 距离为3 的边。 命题31 每一个有6 个点，8 条边的导出匹配可扩图都同构于j 3 命题3 2 如果g 是一个有2 n 6 个顶点3 n 一1 条边的连通的导出匹配可扩图，那么 g 是( 2 n ，3 n 1 ) 一优的 命题3 3 假设g 是( 2 n ，3 n 1 ) 优的，那么g 是导出匹配可扩的 定理3 4 假设g 是一个有2 n 个顶点3 n 一1 条边的连通图，那么g 导出匹配可扩的 充分必要条件是g 是( 2 n ，3 n 1 ) 一优的 4 2 n 个点3 n 条边的霉出区配可扩性的刻划 假设g 是一个连通图，q 是g 的一个导出子图，g l ，g 2 ，研是g v ( q ) 的连通 分支。如果g 满足以下两条件，则我们称g 是一个q 一关节图： ( 1 ) g v ( q ) 的每一个分支g i 是一棵树，不妨设为巩，和鲍的乘积图，也就是说， g t = t k k 2 ( 2 ) 对g v ( q ) 的任一个分支g 女，有两个相邻的顶点z ( m ，g v ( q ) 和z ( ) v ( t k ) ( 2 r 。e ( g t ) ) 满足z 似) z i ，y ( k ) z 5 k e ( g ) 连接g 女和q 的所有的边。 进一步，我们用g 2 表示有点集v ( c ) u z ( m ，( ) 导出的图g 的一个导出子图，也就 是说，g 2 = a v ( a k ) u z ( m ，( ) ) 】。显然，g z 型k 2 ，其中是由t k 在z ( ) 增加 一个悬挂点得到的我们称。( ，g ( ) 为g k 到q 的接触点g k 到q 的接触点集表示为 c ( a k ，国，也就是说，c ( g k ，q ) = z g ( 埘) 。 定理4 。l 假设g 是一个有2 n 个顶点3 n 条边的连通的导出匹配可扩图那么或者图g 同构于d 或e ，或者g 有下面的结构之一t ( i ) k 4 一关节图； ( i i ) a 一关节图并且g ( g 。，a ) = a 1 ，口2 ，1s sr ，其中口l ，0 2 如a 所定义； ( i i i ) b 一关节图并且g ( 虢，b ) = 0 2 ，l i r ，其中a l ，0 2 如b 所定义； ( i v ) c 一关节图并且c ( a 。，c ) = 虮，n 2 ，1 i r ，其中a 1 ，0 2 如c 所定义； ( v ) g = t k 2 + e ，) ，其中e 和厂以下面的方式加到t k 2 上： ( 1 ) e = 1 v 】，= z 2 2 ，z ，yev ( t ) ，x y 掣届( t ) ； ( 2 ) e = z l y 2 ，厂= x 2 y l ，z ，v ( t ) ； ( 3 ) e = a l c 3 一。，= l j n 3 叶疋= a b c ，t i = i r n n 是t 的两条长度为的路；其中，图且， b ，g ，d 和曰在文中有具体的定义。 3 5 ，掰的平方圈的导出匹配可扩性的刻剿 图g 的k 次方，记为g ，它的顶点集为v ( g ) ，其中两顶点相邻的充分必要条件是它 们在g 中的距离不超过k 如果图g 的任意一个支撑母图都是导出匹配可扩的，我们称 图g 为导出匹配可扩的。 钱建国老师在 3 2 证明了如果连通图g 是局部连通的，则g 2 是强导出匹配可扩性 的原晋江老师在【3 6 】证明了如果连通图g 没有独立点割，则g 2 是强导出匹配可扩性 的。 在这一部分别给出树的平方图是导出匹配可扩性的和强导出匹配可扩性的充分必要 条件 定理5 1 假设t 有偶数 y ( 霸 个顶点的树，那么t 2 导出匹配可扩的充分必要条件是 t 没有偶度顶点且t 的直径不大于4 。 定瑾5 2 假设t 有偶数i v ( t ) 1 个顶点的树，那么t 2 强导出匹配可扩的充分必要条件 是t 没有偶度顶点且t 的直径不大于4 。 本文常厕t 己号 g h 】：图g 和图日的结合图 g ht 图g 和图日的乘积图 萨：g 的k 次幂 o ( e ) ：g 图的奇分支数 6 ( g ) ：g 图的最小度 如( “，”) ：“和。两点间的距离 g ( ) ：点的邻点集 g ( ”) ：与点”的距离为2 的点的集合 4 a b s t r a c t g r a p h s c o i l s i d e r e di nt h i sp a p e ra r ef i n i t e ，u n d i r e c t e da n ds i m p l er o u g h l ys p e a k i n g ， t h ep r o b l e m sc o n c e r n e di nt h i st h e s i sa r em a i n l ya sf o l l o w s ： 1t h ei n d u c e dm a t c h i n ge x t e n d a b i l i t yo fc l a w f r e eg r a p h so fd i a m e t e r2 2 t h ei n d u c e dm a t c h i n ge x t e n d a b i l i t yo ft h ec o r n p o s i t i o no ft w og r a p h s ， 3c h a r a c t e r i z a t i o no ft h ei n d u c e dm a t c h i n ge x t e n d a b l eg r a p h sw i t h2 nv e r t i c e sa n d 3 n 一1e d g e s 4 ( 7 t i a ja ( t c i i z a t i o no ft h ei n d u c e dm a t c h i n ge x t e n d a b l eg r a p l i sw i t h2 n v c it i c e sa n d 3 ne d g e s 5 c h a r a c t e r i z a t i o no ft h ei n d u c e dm a t c h i n ge x t e n d a b i l i t yo ft h es q u a r eo ft r e e s as e to fe d g e sm e ( c ) i sc a l l e dam a i c h i n 9o fg i f1 1 0t w oo ft h e ms h a r eac o l n n l o g e n d p o i n t am a t c h i n g i sp e r f e c t 1 i fi tc o v e r sa l lv e r t i c e so fg a1 1 1 3 1 c h i n gm i si n d u c e d 【2 】i fe ( 1 ，( m ) ) = m w es a yt h a tag r a p hg i si n d u c e dm a t c h i n ge z t e n d a b l ef 3 3 1 ，s h o r t l y , i m e z t e n d a b l e i fe v e r yi n d u c e dm a t c h i n gm 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 1 i n d u c e dm a t c h i n ge x t e n d a b i l i t yo fc l a w f r e eg r a p h so fd i a m e t e r2 a g r a p hg i sc l a w - f r e e ，i fi td o e sn o tc o n t a i nk 1 ，3a sa ni n d u c e ds u b g r a p h i f v e ir i c e s 扎a n d 廿a r ec o n n e c t e di ng ，t h ed i s t a n c eb e t w e e n a n dui ng ，d e n o t e db yd c ( n ，口) ， i s t h e , l e n g t ho fas h o r t e s t ，f ) 一p a t h i ng w e s a yag r a p hg i so fd i a m e t e rri ft h e m a x i m u md i s t a n c eb e t w e e nt w ov e r t i c e so fg i sr 。 i nt h i ss e c t i o nt h es u f f i c i e n c ya n dn e c e s s i t yc o n d i t i o nf o rac l a w f l e eg r a p ho f d i a m e t e r 2i sc h a t a c t e r i z e d a n dc o r r e s p o n d i n g l yap o l y n o m i a l t i m ea l g o i 。i t h mt , od e c i d ew h e t h e ra c l a w f r e eg r a p ho fd i a m e t e r2i si m e x t e n d a b l el sg i v e n t h e o r e m1 1 s u p p o s et h a tg i sac l a w f r e e g r a p h o fd i a m e t e i2i fm2 “1 u l ，? 2 2 u 2 ，a m y m ) i sa n i n d u c e dm a t c h i n go fgs u c ht h a tg v 7 ( m ) i sd i s c o n n e c t e d ， t h e ni m 曼3 t h e o r e m1 2ac l a w f r e eg r a p hgo fd i a m e t e r2i si m e x t e n d a b l ei fa n do n l yl f f o ra n yi n d u c e dm a t c h i n gm w i t h m 3 o fg ，g 一1 7 ( m ) h a sf i oo d dc o m p o n e n t a l g o r i t h m1 3i m e x t e n d a b i l i t yo fc l a 、r f r e eg 【a p h so fd i a l n e t e l 2 s t e p 1f o re a c hm e r a ) w i t hi m i 茎3 ，c h e c k w h e t h e rmi sa ni n d u c e dm a t c h i n g o fgo rn o t ，a n ds i m u l t a n e o u s l yg e n e i a t et h es e t m = m e ( c ) i mi sa ni n d u c e dm a t c h i n go f gw i t hi m i 3 ) s t e p2 i fm = 0 ，t h e ns t o p ；gi si m e x t e u d a b l e o t h e r w i s e ，g ot os t e p3 s t e p3 p i c km 朋a r b i t r a r i l ya n df o r mg p ( m ) s t e p4 i fg v ( m 1h a sa no d dc o m p o n e n t ，t h e ns t e p ；gi sn o ti m e x t e n d a b l e o t h e r w i s e ，i e ，g v ( m ) h a sn oo d dc o m p o n e n t s ，s e t m ：= m m ) a n dt u r nt os t e p2 t h e o r e m1 4f o rag i v e nc l a w - f r e eg r a p hg o fd i a m e t e r2 ，t h ea l g o r i t h ma b o v ec a n d e t e r m i n ew h e t h e ri ti si m e x t e n d a b l ei no ( n e 3 ) t i m e ，w h e r e 礼= i v ( a ) ia n d = e ( g ) l 2 i n d u c e dm a t c h i n ge x t e n d a b i l i t yo ft h ec o m p o s i t i o no ft w og r a p h s t h e c o m p o s i t i o no fs i m p l eg r a p h sg a n d 日i st h es i m p l eg r a p hc h 1w i t hv e r t e xs e t v ( g ) v ( 日) ，i nw h i c h ( “， ) i sa d j a c e n tt o ( 7 ，u ) i fa n do n l yi fe i t h e ru “e ( c ) o r “= 札a n dv v 7 e ( h 1 i nt h i ss e c t i o n ，t h ei n d u c e dm a t c h i n ge x t e n d a b i l i t yo ft h ec o m p o s i t i o no ft w og r a p h s i ss t u d i e d i ti ss h o w nt h a tg f h li si m e x t e n d a b l e 、i fb o t hga n d 日a r en e n t r i v i a l ，gi s c o n n e c t e d ，a n dga n dhs a t i s f ye n eo ft h ef o l l o w i n gc o n d i t i o n s ： ( 1 ) o n eo fg a n dhi si m e x t e n d a b l e l ( 2 ) b o t hg a n dhh a v ep e r f e c tm a t c h i n g s ； ( 3 ) o n eo fg a n dhh a sap e r f e c tm a t c h i n ga n dt h eo t h e rh a san e a rp e r f e c tm a t c h i n g t h e o r e m2 。1i fo n eo fga n d 日i si m e x t e n d a b l e 、t h e nc h ii si m e x t e n d a b l e t h e o r e m2 2i fb o t hga n dhc o n t a i np e r f e c tm a t c h i n g s ，t h e ng f 1 i si m e x t e n d a b l e t h e o r e m2 3i fgh a sap e r f e c tm a t c h i n ga n dhi sn o n t r i v i a la n dh a sai l e a l p e r f e c tm a t c h i n g ，t h e ng 【日 i si m e x t e n d a b l e t h e o r e m2 4i fgi san o n t r i v i a lc o n n e c t e dg r a p ha n dh a san e a rp e r f e c tm a t c h i n g 扎t jl ih a sat ) m f e e tn i a i ，t h i n gt h e l lc h ji si m e x lc n d a l ) h 3 c h a r a c t e r i z a t i o no ft h ei n d u c e dm a t c h i n ge x t e n d a b l eg r a p h sw i t h2 n v e r t i c e sa n d3 n 一1e d g e s 6 t h ep r o d u c to ft w og r a p h sta n dh ，d e n o t e db yt h ，i st h eg r a p hw i t hv e r t e xs e t v ( t ) xv ( h ) = 扣，u ) ：u y ( 丁) ，v v ( h ) s u c ht h a tt w ov e r t i c e s ( “，u ) ，( 。，y ) v ( t ) xv ( h ) a r ea d j a c e n t ，i nt hi fa n do n l yi f e i t h e rf 姓= 。a n dv y e ( 且) 】o r 移= ya n d 牡z e ( 丁) 】 a g r a p h1 1w i t h2 nv e r t i c e sa n d3 n 一1e d g e si ss a i dt ob e ( 2 n 3 n 一1 ) 一o p t i m a li fh i si s o m o r p h i ct ot k 2 + e ，w h e r eti sa na r b i t r a r yt r e eo nnv e r ti c ( 嗡a n dci sa n y e d g e c o n n e c t i n gt w ov e r t i c e st h a t1 i ei nd i f i e r e n tc o p i e so ft a n dh a sd i s t a n c e3b e t w e e nt h e m i ntxk 2 d e n o t eb y 甑3t h eg r a p ho b t a i n e df r o mk a 。3 b yd e l e t i n ga l la r b i t r a r ye d g e i i l 1 3 3 i ，y u a np r o v e dt h a tac o n n e c t e di m e x t e n d a b l eg r a p ho n2 nv e r t i c e sh a sa t l e a s t3 n 一2 e d g e s ，a n dt h eo n l yi m e x t e n d a b l eg r a p hw i t h2 nv e r t i c e sa n d3 n 一2e d g e s i st k 2 ，w h e r eti sa na r b i t r a r yt r e eo n7 lv e r t i c e s w es h o , n ri nt h i ss e c t i o nt h a tt h e o n l yi m e x t e n d a b l eg r a p hw i t h2 n 6v e r t i c e sa n d3 n 一1e d g e si st k 2 + e ，w h e r e 7 1i sa na r b i t r a r yt r e eo nnv e r t i c e sa n dei s a n ye d g ec o n n e c t i n gt w ov e r t i c e st h a tl i ei n d i f i e r e n t ，c o p i e so ft a n dh a v ed i s t a n c e3b e t w e e nt h e mi nt k p r o p o s i t i o n3 1 i fgi sac o n n e c t e d1 m e x t e n d a b l eg r a p hw i t h2 n 6 v e r t i c e s a n ( i3 n 一1e d g e s ，t h e ng i s ( 2 n ，3 竹一1 ) 一o p t i m a l p r o p o s i t i o n3 2s u p p o s eg=t xk 2 十8 ，w h e r e ? 1i sa na r b i t r a r yt r e eo nn 3 v e r t i c e sa n dei s a n ye d g ec o n n e c t i n gt w o v e r t i c e st h a tl i e1 1 1d i f i e l e n tc o p i e s ( i fta n dh a v e d i s t a n c e3b e t w e e nt h e mi nt 施t h e ng i si m e x t e n d a b l e t h e o r e m3 3 s u p p o s et h a tg i sac o n n e c t e dg r a p hw i t h2 礼6v e r t i c e sa n d3 n 一1 e d g e s t h e ngi si m e x t e n d a b l ei fa n do n l yi fg i si s o m o r p h i ct ot k 2 + e w h e r et i s at r e ew i t hnv e r t i c e sa n dei sa n y e d g ec o n n e c t i n gt w ov e r t i c e st h a t1 i ei nd i f i e r e n tc o p i e s o f ta n dh a v ed i s t a n c e3b e t w e e nt h e mi nt xk 2 4 c h a r a c t e r i z a t i o no ft h ei n d u c e dm a t c h i n ge x t e n d a b l eg r a p h sw i t h2 n v e r t i c e sa n d3 ne d g e s s e t t h ep r o d u c to ft w og r a p b st a n dh ，d e n o t e db ytxh ，i st h eg r a p hw i t hv e r t e x v ( t ) v ( h ) = ( u ，v ) ：“y ( 丁) ， y ( h ) s u c ht h a tt w ov e r t i c e s ( “，刘) ，( z ，y ) v ( t ) v ( h ) a r ea d j a c e n ti nt h i fa n do n l yi f e i t h e rl = za n dv y e ( 月) ! o r 【口= ya n d ? z x e ( 丁) w h e nh = k 2 ，。，屯c a nb e d e f i n e db 3 s e t t i n g v ( t k 2 ) = x i ：z v ( 丁) ，i = 1 ，2 l e ( r k 2 ) ： z l x 2 石y ( t ) ) u 岛执，2 ，f ( 丁) 。i = 1 ，2 f b r 。= l 2 t h es u b g r a p h 正t ，ft k 2i n d u c e db y 了：z 、( t ) ) i s ( ：a l l e dt h ei - t hc o p y ( i fri nt h i s1 ) a p e i 、，甄d e n o t e st h ev e r t e xo f z ( o r r e s p o n d i n gt o 、fi 】1 丁 7 s u p p o s e t h a tgi sac o n n e c t e d g r a p h ，q i sa ni n d u c e d s u b g r a p h o fga n d g i ，g 2 ，g r a r et h ea l lc o m p o n e n t so fg 矿( q ) w ec a l lg aq - j o i n tg r a p hi fb o t ho ft h ef o l l o w i n g c o n d i t i o n sa r es a t i s f i e d ： ( 1 ) e a c hc o m p o n e n tg ko fg v ( q ) i s t h ep r o d u c to fat r e e ，s a y 疋，a n dk 2 ，i e ， g k = 疋k 2 ( 2 ) f o re a c hc o m p o n e n tg ko fg y ( q ) ，t h e r ea r et w oa d j a c e n t v e r t i c e sz 【，( v ( q ) a n dz ( ) v ( t 0 ( a n ds oz 。) 。垆e ( a t ) ) s u c ht h a tz ( 。) j “( 2 ) z 扩e ( g ) a r e t h eo n l ye d g e sj o i n i n gg kt oq f u r t h e r m o r e ，w ew i l l d e n o t eb yg 2t h es u b g r a p ho fgi n d u c e db yt h ev e r t e xs u b s e t v ( g k ) u z ( ，y 【) ，i e ，g ：g y ( g ) u 石( m ，掣( 2 ) i ti se a s yt os c et h a tg 2 型咒k 2 ， w h e r e 瓦i s at r e eo b t a i n e df r o m 疋b ya d d i n gap e n d e n tv e r t e xa d j a c e n tt oz w e c a l l z o “，p ( 。t h ec o n t a c tv e r t i c e so fg 女t o0 t h e s e to fc o n t a c tv e r t i c e so f g tt oq i sd e n o t e b yc ( a k ，q ) ，i ec ( g k ，q ) = z ( 刖，( 2 ) t h e o r e m4 1 s u p p o s et h a tg i sac o n n e c t e di m e x t e n d a b l eg r a p hw i t h2 nv e r t i c e s a n d3 ne d g e s t h e n e i t h e rgi s i s o m o r p h i ct oo n eo fd a n dfo rgh a so l l eo ft h e f o l l o w i n gs t r u c t u r e s ： ( i ) ak 4 一j o i n tg r a p h ； ( i i ) a na j o i n t , g r a p hw i t hc ( g ，a ) = 8 1 ，2 ，l i 墨r 、w h e r en l ，a 2a r ea sd e f i n e d i ng i a p t ij 4 ( i i i ) ab - j o i n tg r a p hw i t hc ( g i ，b ) = 口1 ，。2 ) ，1s is 扎w h e r e a l ，8 2a r ea sd e f i n e d i ng r a p h 凹： ( i v ) ac j o i n tg r a p hw i t hc l ( g ，a ) = n l ，n 2 ) ，1 i 7 、，w h e r ea l ，a 2a r ea sd e f i n e d i ng r a p hc ： ( v ) g = t k 2 + e ，) ，w h e r e ea n d ，a r ea d d e dt ot k 2i no n eo f t h e f o l l o w i n g w a y s ： ( 1 ) e = x l y l ，= x 2 y 2 ，z ，y y ( t ) ，x y 掣e ( t ) ； ( 2 ) e = x l y 2 ，= x 2 y l ，x ，y y ( t ) ； ( 3 ) e = g i c 3 f = 白心一，w h e r e 瓦= a b e ，乃= l m n a r et w o3 - p a t h so f r ； w h e r ea b ，c ，da n de a r es p e c i f i c a l l yd e f i n e d 5 c h a r a c t e r i z a t i o no ft h ei n d u c e dm a t c h i n ge x t e n d a b i l i t yo ft h es q u a r eo f n e e s t 1 l ck - t hp ( ) 1 u c ro fa g r a p hg ，d e n o t e db yg ，】st h eg r a p hw 9 hv e l t t xs c l 、( ( j ) i n w h i c ht w ov e lt i c e sa r ea d j a c e n ti fa n do n l yi ft h ed i s t a n c eb e t w e e nt h e mi ng i sa tm o s t k 8 i n 3 2 q i a n s h o w e dt h a ti fc o n n e c t e dg r a p hgi sl o c a l l yc o n n e c t e d ，t h e ng 2i ss t r o n g l y i m e x t e n d a b l e i n 【3 5 ，3 6 】y u a np r o v e dt h a t i fc o n n e c t e dg r a p hgo ne v e nv e r t i c e sh a s n oi n d e p e n d e n tc u t ，t h e ng 2i ss t r o n g l yi m e x t e n d a b l e i nt h i ss e c t i o n ，w eg i v et h es u f f i c i e n c ya n d n e c e s s i t yc o n d i t i o n sf o rt h es q u a r eo ft r e e s t ob ei m e x t e n d a b l ea n ds t r o n g l yi m e x t e n d a b l e ，r e s p e c t i v e l y t h e o r e m5 1s u p p o s et h a tti sat r e ew i t h1 v ( 丁) je v e n ，t h e nt 2i si m e x t e n d a b l e i fa n d o n l yi ft h e r ei sn o v e r t e xo fe v e nd e g r e ei nta n dt h ed i a m e t e ro ft i sn om o r et h a n 4 t h e o r e m5 2 s u p p o s et h a tt i sat r e ew i t h i v ( t ) le v e n t h e nt 2i ss t r o n g l y i m e x t e n d a b l ei fa n do n l yi ft h e r ei sn ov e r t e xo fe v e nd e g r e ei nta n dt h ed i a m e t e ro ft i sn om o r et i t a n4 9 1i n t r o d u c t i o na n dn o t a t i o n s 1 1 1t h i sc h a p t e r w ep r e s e n tag e n e r a li n t r o d u c t i o nt ot h et h e s i s s e c t i o n1 1 g i v e sa b r i e fi n t r o d u c t i o nt om a t c h i n g t h e o r y i ns e c t i o n12 ，w el i s tn o t a t i o n s a n dd e f i n i t i o n su s e d i nt h i st h e s i s i ns e c t i o n1 3 ，w es u r v e yt h em a i nr e s u l t so ni 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 e c t i o n1 4g i v e st h em a i nr e s u l t so ft h et h e s i s 9 1 1i n t r o d u c t i o nt om a t c h i n gt h e o r y m a t c h i n gt h e o r y i sac e n t e rp a r to f g r a p ht h e o r y 、n o to n l yb e c a u s e o f1 t sa p p l i c a ti o n s ， b u ta l s ob e e a n s ei t i st h es o u r c eo fm a n yi m p o r t a n ti d e a sd e v e l o p e dd u r i n gt h er a p i d g r o w t ho fc o m b i n a t o r i c sd u r i n gt h el a s ts e v e r a ld e c a d e s m a t c h i n gt h e o r y ，a sw e l l a st h ea s s i g n m e n tp r o b l e mi nl i n e a rp r o g r a m m i n g ，h a sa w i d er a n g eo fa p p l i c a t i o ni nt h et h e o r ya n dp r a c t i c eo fo p e r a t i o n sr e s e a r c h b 3 。s o m e p r a c t i c a lm o t i v a t i o n s ，e g ，f o rf i n d i n ga l lo p t i m a ls o l u t i o n s ，p e o p l ew a n tt o k n o wt h e s t