（运筹学与控制论专业论文）关于图的导出匹配问题的若干结果.pdf

a c k n o w l e d g e m e n t f i r s to fa l l ，1w i l le x p r e s sm yg r a t i t u d et om ya d v i s o rp r o f y u a nj i n j i a n g d u r i n g t h i st h e s i s c h o s e na n dw r i t t e n ，p r o f y u a nc a r e f u l l yr e f e r e e di t w i t h o u th i sg u i d a n c e ， a l lt h e s ew o u l dn o tc o m et oe x i s t e n c e a tt h es a m et i m e ，p r o f l i ny i x u ng a v em e m a n y u s e f u la d v i c e s it h a n kf o rt h e i rp a t i e n ti n s t r u c t i o n st om y s t u d y ir e s p e c tm y t w o a d v i s o r s p r u d e n tl e a r n i n ga t t i t u d e ，p r o f o u n dk n o w l e d g ea n dn o b l ee t h i c s s e c o n d l y 【w o u l dl i k et ot h a n ka l lm yt e a c h e r sa n dm yc l a s s m a t e sf o rt h e i rh e l p - f u ls u g g e s t i o n s a tl a s t ia 4 ng r a t e f u lt om yf a m i l i e sf o r b e i n gs ou n d e r s t a n d i n ga n d s u p p o r t i n g n o t a t i o n s i nt h i sd i s s e r t a t i o n ，w ec o n s i d e rf i n i t ea n ds h n p l eg r a p h s f o ra g r a p he l e tv ( g ) a n de ( g ) d e n o t ei t sv e r t e xs e ta n d e d g es e t ，r e s p e c t i v e l y d ( a ) d e n o t e st h ed e g r e eo fg 6 ( g ) d e n o t e st h em i n i m u md e g r e eo fg a ( a ) d e n o t e st h em a x i m u md e g r e eo fg g h d e n o t e s t h e p r o d u c to f ga n d h g o hd e n o t e s t h e s t r o n gp r o d u c to f g a n dh i m ( g ) d e n o t e st h ei n d u c e dm a t c h i n gn u m b e ro fg c h ( g ) d e n o t e st h ec h r o m a t i cn u m b e ro fg s q ( g ) d e n o t e st h es t r o n gc h r o m a t i ci n d e xo fg z ( a ) d e n o t e st h ei n d e p e n d e n tn u m b e ro fg t e r m i n o l o g ya n dn o t a t i o nn o td e f i n e dh e r ec a l lb ef o u n d i n ( 1 】 中文摘要 本文所考虑的图均为连通的、有限的无向简单图设g 是个给定的图图g 的匹 配是g 的一个边集，其中任两条边没有公共点而图g 的导出匹配m 是图g 的一个匹 配，v ( m ) 的导出图是它本身图g 的导出匹配数，记为i m ( g ) ，是g 的最大导出匹 配的边数我们说图g 是导出匹配可扩图，如果g 的任一个导出匹配均可扩充为一个完 美的匹配图g 的f ，着色是一个映射妒：烈研一 l ，2 ，0 。蓠图g 的强扛着色是 这样的一个t - 着色，着同色的边形成一个导出匹配。具有强t - 着色的最小值t 称为图g 的强着色数，记为8 q ( g ) 平面格子图是记为p m x r ，是，m 和p 竹的乘积图本文主 要结果是t ( 1 ) 如果r n 与n 中有一个为偶数，则有i m ( p m r ) = 芈 ( 2 ) 如果m 是奇数，则有 i m ( p m x p a ) = r 竿1 ： 半 一岫d 4 ) ， 4 【3 等t - - 1 ，m 兰3 ( m o d4 ) ( 3 ) 如果圈g 的最大度为3 ，且3 度顶点在一个独立集中，贝有。g ( g ) = 7 ( 4 ) 如果圈g 是3 正则导出匹配可扩图。除了j b xk 2 ，饶( 1 ，3 ) 和c s ( 1 ，4 ) ，均有 s q ( g ) 8 ( 5 ) i m g 9 恐) 鄙( ( 6 ) 本文构造了3 一正则图的两个无穷类。使得其中的任一图均有s q ( g ) = 1 0 从而解 决了文献【4 】中作者提出的个问题 关键词：导出匹配。导出匹配数。强边着色 a b s t r a c ti ne n g l i s h l e tgb eas i m p l e ，c o n n e c t e d ，u n d i r e c t e da n df i n i t eg r a p h am a t c h i n gi ngi sas e t o fe d g e s ，n ot w oo fw h i c ha r ei n c i d e n t a ni n d u c e dm a t c h i n gm i ngi sam a t c h i n gs u c h t h a tn ot w oe d g e so fma r ej o i n e db ya ne d g eo fg ；t h a ti s ，a ni n d u c e dm a t c h i n gi sa m a t c h i n g w h i c hf o r m 8a i n d u c e ds u b g r a p h w e s a yg i 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 yi m - e x 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 go fg i si n c l u d e di nap e r f e c tm a t c h i n go fg t h ei n d u c e dm a t c h i n gn u m b e ro fg i s d e f i n e d 酷i m ( c ) = m a ) ( i m f ： mi sa ni n d u c e dm a t c h i n go fg ) w er e p r e s e n tc o l o r so ft h ee d g e so fg b yp o s i t i v ei n t e - g e t s f o r m a l l y , at - c o l o r i n go fag r a p hg i sam a p 妒：e ( g ) 一 1 ，2 ，n ) a s t r o n g t - c o l o r i n go fag r a p hg i sat - c o l o r i n gs u c ht h a tt h ee d g e sw i t ht h es a l n ec o l o rf o r ma n i n d u c e dm a t c h i n go fg t h em i n i n l n mn u m b e ro fas t r o n gt - c o l o r i n g ，d e n o t e db ys q ( g ) ， i sc a l l e dt h es t r o n gc h r o m a t i ci n d e x t h e p l a n eg r i dg r a p h xr i st h ep r o d u c to fp m a u d 只t h em a i nr e s u l t so ft h ep a p e ra r e 踞f o l l o w s ： ( 1 ) i f a t l e a s to n eo f ma n dni se v e n ，t h e ni m ( p m r ) = 警 ( 2 ) i f m i so d d ，t h e n i m ( p m p 3 r 竿o m m 1 、= 摹： ) = 尸广1 = 一 m 三1 ( m o d4 ) ， m 三3 ( r o o d4 ) ( 3 ) l e t gb e8 g r a p hw i t h ( g ) = 3 ，s u c ht h a t3 一d e g r e ev e r t i c e sf o r mi n d e p e n d e n t s e t t h e ns q ( g ) = 7 ( 4 ) i f gi s3 - r e g u l a rc 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 ，n o ti n c l u d i n gk s 尬，g ( 1 ，3 ) a n d g ( 1 ，4 ) ，t h e ns q ( g ) 8 。 ( 5 ) i m ( g k 2 ) = 卢( g ) ( 6 ) t w o i n f i n i t ef a m i l i e so f3 - r e g u l a rg r a p h sa r ec o n s t r u c t e d ，s u c ht h a te a c hg r a p h gi nt h e s ef a m i l i e sh a ss q ( q = 加t h i ss o l v e sa n o p e np r o b l e mp o s e di n 6 k e y w o r d s ：i n d u c e dm a t c h i n g ，i n d u c e dm a t c h i n gn u m b e r ，s t r o n ge d g e - c o l o r i n g 3 1 i n t r o d u c t i o na n dn o t a t i o n s i nt 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 gt h e o r y i ns e c t i o n1 2 骶l i s ta l ln o t i o n sa n dd e f i n i t i o n s i nt h i st h e s i s i ns e c t i o n1 3w es u r v e ym a i nr e s u l t sa b o u ti n d u c e dm a t c h i n ga n ds t r o n g c h r o m a t i ci n d e xo fag r a p h 4 1 1 i n t r o d u c t i o nt om a t c h i n gt h e o r y i tn e e d st ob ep o i n t e do u tt h a tm a t c h i n gt h e o r yi s ac e n t r a lp a r to fg r a p ht h e o r y , n o to n l yb e c a u s eo fi t sa p p l i c a t i o n s ，b u ta l s oi 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 s d e v e l o p e dd u r i n gt h er a p i dg r o w t ho f c o m b i n a t o r i c sd u r i n gt h el a s ts e r v a ld e c a d e s w ek n o wt h a ts o m ep r a c t i c a lp r o b l e m sc a l lb ec o n v e r t e di n t om a t c h i n gp r o b l e m s s u p p o s et h a tt h e r ea r e 礼j o b sp r o c e s s e d o nt w om a c h i n e s w ea s s u m et h a ta n yj o bc a n b ep r o c e s s e do i le i t h e rm a c h i n ea n dt h em a c h i n e sa r ei d e n t i c a l l e tu ss u p p o s et h a tn j o b sa r ep a r t i a l l yo r d e r e di nt h es e n s et h a tf o ra n y t w o j o b s 五a n d 以， j ki f 五m u s t b ec o m p l e t e db e f o r e 以c a nb es t a r t e d i fa l lj o b sr e q u i r ea ne q u a lp r o c e s s i n gt i m e ，w h a t i st h em i n i m u m c o m p l e t e dt i m eo f a l lj o b s ? l e tu sm o d e lt h i ss i t u a t i o nu s i n ga g r a p hg a sf o l l o w s l e tt h ev e r t i c e so fgb et h ej o b sj l ，也，厶，a n d a n dj ka r ea d j a c e n ti f a n di fo n l yi ft h e ya r ei n c o m p a r a b l ei nt h ep a r t i a lo r d e r n o t et h a tt w o j o b sp r o c e s s e db y t w om a c h i n e sa tt h ew e et i m ec a nb ec o n s i d e r e dt ob em a t c h e d s ot h i sp r o b l e mb e l o n g s t ot h ec l a s so fm a x i m u mm a t c h i n gp r o b l e m f o rt h ef a m o u sm a r r i a g ep r o b l e m ，s u p p o s e t h e r ea r e 住w o m e na n d 礼m e n 。w ew i s ht oa r r a n g e 铝m a r r i a g e s m o r e o v e rs u p p o s et h a tw e w i s ht om a r r yo n l yw o m e na n dm e nw h oa r ea c q u a i n t e dw i t he a c ho t h e r w ec a nm o d e l t h i ss i t u a t i o nu s i n gab i p a r t i t eg r a p hg = ( u v ) a sf o l l o w s l e tub et h es e to ft h e s en w o m e na n dvb et h es e to f t h e s e 礼m e n av e r t e xi nua n do n ei nva r ea d j a c e n tt oi f a n d o n l yi ft h e ya r ea c q u a i n t e d t h e nt h i sp r o b l e mb e l o n g st ot h ec l a s so fp e r f e c tm a t c h i n g p r o b h m f o r b e n i u sg a v et h em a r r i a g et h e o r e m w h i c hs t a t e st h a tt h i si sp o s s i b l ei fa n d i fo n l yf o re a c hk ，1 k n ，e a c ho fkw o m e n c o l l e c t i v e l yk n o w sa tl e a s t m e n t h em a r r i a g et h e o r e mw a sf o r e r u n n e ro ft h ef a m o u sh a l l s t h e o r e m 1 2 h a l l s t h e o r e ms t a t e st h a tab i p a r t i t eg r a p hg = ( u ，y ) h a s p e r f e c tm a t c h i n g si fa n di fo n l y f o ra n ys u b s e tso fu ，i ( s ) i i s l h a l l st h e o r e mg i v e sa n e c e s s a r ya n das u f f i c i e n t c o n d i t i o nf o rab i p a r t i t eg r a p ht oh a v eap e r f e c tm a t c h i n g f o r g e n e r a lg r a p h ，t u t t ea n d l o v d s z ( 【1 2 】，【9 1 ) p r o v e dat h e o r e mc h a r a c t e r i z i n gt h ee x i s t e n c eo fp e r f e c tm a t c h i n g a c o n n e c t e dg r a p hh a sap e r f e c tm a t c h i n gi fa n di fo n l yo ( c s ) i s i ，f o ra l ls c v ( g ) ， w h e r e o ( a ) d e n o t e st h en u m b e r o fo d d c o m p o n e n t so fg 5 k u h na n dh a l lp r e s e n t e dt h ef i r s tf o r m a lp r o c e d u r e sf o rf i n d i n gap e r f e c tm a t c h i n g i nab i p a r t i t eg r a p h a ta l m o s tt h es a m et i m e ，f o r da n df u l k e r s o np u b l i s h e dt h ef i r s t p a p e ro nt h et h e o r yo fn e t w o r kf l o w s 。f l o wt h e o r yi m m e d i a t e l yb e c a m e as u b s t a n t i a l n e wt o o li nc o m b i n a t o r i a la p p l i c a t i o n so fa l lk i n d sw h i c hi su s e dt ob i p a r t i t em a t c h i n g i nt h el i n e a rp r o g r a m m i n g j u d i ne ta 1 u s et h es oc a l l e de l l i p s o i dm e t h o dt ot u r na p o l y h e d r a ld e s c r i p t i o no ft h ec o n v e x h u l lo fm a t c h i n g si n t oap o l y n o m i a l t i m ea l g o r i t h m f o rm a x i m u mm a t c h i n gi na b i p a r t i t eg r a p ha p p e a r e d f o rn o n b i p a r t i t eg r a p h ，e d m o n d s i n1 9 6 5g a v et h ef i r s tp o l y n o m i a l - t i m em a t c h i n ga l g o r i t h m i n d u c e dm a t c h i n g sw e r ei n t r o d u c e db yc a m e r o n 【2 1 ，w h op r o v e dt h a tf i n d i n gam a x - i m u mi n d u c e dm a t c h i n gi sn p c o m p e t e 【2 】2f o rb i p a r t i t eg r a p h s i n d u c e dm a t c h i n g sa r e o ft h e o r e t i c a li m p o r t a n c e t h e r ei sa ni m m e d i a t ec o n n e c t i o nb e t w e e nt h es i z eo fa ni n 。 d u c e dm a t c h i n ga n di r r e d u n d a n c yn u m b e ro fag r a p h 【5 】o nt h ep r a c t i c a ls i d e ，i n d u c e d m a t c h i n g sh a v et h ef o l l o w i n ga p p l i c a t i o n sf o rs e c u r ec o m m u n i c a t i o nc h a n n e l s c o n s i d e r ab i p a r t i t eg r a p hg = ( 玑k e ) w h e r ee d g e sr e p r e s e n tc o m m u n i c a t i o nc a p a b i l i t i e sb e t w e e nb r o a d c a s t e rn o d e si nua n dr e c e i v e r sn o d e si nv w ew a n tt os e l e c tke d g e s e i ( i = 1 ，2 ，k ) s u c ht h a tm e s s a g e so nc h a n n e liw i l lb ep a s s e df r o mb r o a d c a s t e rv ( e i ) t or e c e i v e ry ( e ) s ot h a ti ti si m p o s s i b l ef o ram e s s a g eb r o a d c a s to nc h a n n e l t ob el e a k e d o ri n t e r c e p t e d s i m i l a ra p p l i c a t i o n se x i s tf o rv l s ia n dn e t w o r kf l o wp r o b l e m s i nt h e c a s e o fa r b i t r a r yu n d i r e c t e dg r a p h s ，w em i g h t i n t e r p r e te a c hv e r t e xo fag r a p ha sr e p r e s e n t i n g as p yw i t he d g e sb e t w e e ns p i e sw h ok n o we a c ho t h e r h e r ew ew a n tt os e l e c tkp a i r s o f s p i e st ow o r kt o g e t h e r ( t h em a t c h e de d g e s ) s u c ht h a tn oa c t i v es p yk n o w sa n yo t h e r b e s i d e st h ep a r t n e r u n l e s sp = p ，i n d u c e dm a t c h i n gp r o b l e md o e sn o th a v e ”g o o dc h a r a c t e r i z a t i o n ” k oa n ds h e p h e r 8 】p r o v e dt h en p c o m p l e t e n e s so fi n d u c e dm a t c h i n gp r o b l e mf o r 3 一 r e g u l a rp l a n e rg r a p h s y u a na n dy a n g 【1 4 s h o w e dt h a tt h em a x i m u mi n d u c e dm a t c h i n g p r o b l e mi ss t i l ln p - h a r df o rg r a p h so fd i a m e t e r2 ，b i p a r t i t eg r a p h so fd i a m e t e r3a n d c l a w - f r e eg r a p h s p l u m m e rf 11 】i n t r o d u c e dt h ef o l l o w i n gd e f i n i t i o n ag r a p hg i sn e x t e n d a b l ei fg h a sam a t c h i n go fs i z e 礼a n de v e r ys u c h m a t c h i n ge x t e n d st oap e r f e c tm a t c h i n gi n 6 g f u r t h e r ，y u a nf 1 3 】r a i s e dt h ep r o b l e mo fi 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 ，a g r a p hg i si n d u c e dm a t c h i n ge x t e n d a b l ei fe v e r yi n d u c e dm a t c h i n ge x t e n d st oap e r f e c t m a t c h i n g 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 fg r a p hc a nb et h o u g h ta sav a r i a t i o n o f n - e x t e n d a b i l i t y t h ep r o b l e m d e t e r m i n ew h e t h e rag i v e ng r a p hi si m e x t e n d a b l e ”i s c o - n p c o m p l e t ef o rg r a p h sw i t hd i a m e t e r2a n db i p a r t i t eg r a p h sw i t hd i a m e t e r3 w e s t u d yt h ei n d u c e dm a t c h i n gn u m b e ro ft h ep l a n eg r i dg r a p h ，s t r o n ge d g e c o l o r i n g o fs p e c i a lg r a 曲s i na d d i t i o n ，w es t u d yt h es t r o n ge d g e c o l o r i n go f3 - r e g u l a ri n d u c e d m a t c h i n ge x t e n d a b i l i t y 1 2 c o n c e p t sa n dt e r m i n o l o g y i nt h i ss e c t i o n ，w er e p r o d u c es o m en o t i o n sa n dd e f i n i t i o n s f o rd e t a i l s ，s e e ( 1 ，( 2 】1a n d 【1 0 1 a l lg r a p h su n d e r c o n s i d e r a t i o na r es i m p l e ，c o n n e c t e d ，f i n i t ea n du n d i r e c t e d f o ra g r a p hg i t sv e r t e xs e ta n de d g es e ta r ed e n o t e db yv ( c ) a n d 嚣( g ) ，r e s p e c t i v e l y f o rs c y ( 回，s e t e ( s ) = 伽e ( g ) ：钍，t j s 1 f u r m e ( g ) ，s e t v ( m ) = y ( g ) ：t h e r e i sz v ( g ) ，s u c ht h a t 盯z m ) f o ra n ye d g ee e ( g ) ，v ( e ) ) i sw r i t t e ni ns h o r t e rf o r ma s1 ，( e ) m 四( g ) i sa m a t c h i n g o fg ，i fv ( e ) n v ( ) = 瓯f o re v e r yt w o d i s t i n c te d g e se ，m a m a t c h i n gm o fgi sa p e r f e c tm a t c h i n g 【l o ，i fv ( m ) = y ( g ) w es a yt h a tam a t c h i n gm o fgi sa n i n d u c e dm a t c h i n g 2 】i f e ( y ( m ) ) = m ，i e ，v ( m ) i n d u c e sa1 - r e g u l a rs u b g r a p ho fg as e to fv e r t i c e si si n d e p e n d e n ti fn ov e r t i c e sa r ea d j a c e n t t h en u m b e ro f v e r t i c e si n am a x i m u mv e r t e x i n d e p e n d e n t s e to fgi sd e n o t e d b y ) ( ( g ) t h en e i g h b o rs e to f as u b s e t x 垦y ( g ) ，d e n o t e db yn a ( x ) ，i sa s e to fv e r t i c e si nv ( g ) xe a c ho fw h i c hi sa d j a c e n t t oa t e a s t ev e r t e xi nx t h e s u b g r a p ho fgi n d u c e db yas e tx v ( g ) i sd e n o t e d 7 b y g 1 t h ec a r t e s i a np r o d u c to fg r a p hga n dh ，d e n o t e db yg h ，i sag r a p hw i t h v ( g h ) = v ( g ) y ( 口) ，a n d t w ov e r t i c e s 钍= ( 钍l ，u 2 ) a n d 锄= ( v l ，v 2 ) a r ea d j a c e n t i nt h ec a r t e s i a np r o d u c tw h e n e v e ru 1 = 1a n du 2 v 2 e ( g 2 ) o rs y m m e t r i c a l l yi fu 22 v 2 a n d 让l l e ( g 1 ) t h es t r o n gp r o d u c t o fg r a p h sg a n d 日，d e n o t e db yg oh ，i sa g r a p hw i t hv ( g o 日) = v ( c ) xy ( 日) ，a n dt w ov e r t i c e s = ( u l ，u 2 ) a n d = ( v l ，v 2 ) a r e a d j a c e n ti nt h es t r o n gp r o d u c tw h e n e v e ru l = v l a n dt 2 w 2 e ( g 2 ) o rs y m m e t r i c a l l yi f “2 = 口2a n d l i u l e ( g 1 ) o r 1 钉l e ( g 1 ) a n d 钍2 u 2 e ( g 2 ) ac o n n e c t e dg r a p hi ss a i dt ob en e x t e n d a b l e1 1 1 1 ，i fy ( g ) 2 n + 2 ，gh a sap e r f e c t m a t c h i n g ，a n d f o re v e r ym a t c h i n gmo fgw i t hi m l = 忆，t h e r ei sa p e r f e c tm a t c h i n gm 7 o f g ，s u c ht h a tm m 7 g i si n d u c e dm a t c h i n g e x t e n d a b l e 1 3 ，i fe v e r yi n d u c e dm 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 ，f o rc o n v e n i e n c e ，s a yi m e x t e n d a b l e w ec o n s i d e rc o l o r i n go ft h ee d g e so fag r a p hw i t hp o s i t i v ei n t e g e r at - c o l o r i n go fa g r a p hg = ( v e ) i s am a p 妒： 斗 l ，2 ，礼) at - c o l o r i n gi sp r o p e ri f 妒( e ) = 妒( ，) a n de ，i m p l yt h a tt h ee d g e sea n dfh a v en oc o m m o ne n d p o i n t s o fc o u r s e ，t h e c h r o m a t i ci n d e xo fag r a p hgi st h el e a s ttf o rw h i c hgh a sap r o p e rt - c o l o r i n g n o t e t h a tw h e n e v e r 妒i sap r o p e rt - c o l o r i n go fag r a p hg = ( y ，e ) a n d 理 1 ，2 ，- 一，0 ，t h e n t h ee d g e s i n m = e e ：妒( e ) = 口) f o r m a m a t c h i n g i n g a s t r o n gt c o l o r i n go fag r a p hg i sap r o p e rt - c o l o r i n gs u c ht h a te d g e sw i t ht h e s a m ec o l o rf o r mn i li n d u c e dm a t c h i n go fg t h es t r o n gc h r o m a t i ci n d e x ，凹( g ) ，i st h e l e a s ttf o rw h i c hgh a sas t r o n gt c o l o r i n g f o rc o n v e n i e n c e ，t w oe d g e so fagw i l l b ec a l l e dn e i g h b o r si ngi ft h e yd on o tf o r ma l li n d u c e dm a t c h i n g ，i e ，i fe i t h e rt h e ya x e i n c i d e n t ( s h a r ea ne n dp o i n t ) ，o rt h e ya r ej o i n e db ya ne d g e ， a tas e m i n a ri np r a g u ea tt h ee n do f 1 9 8 5 ，e r d s sa n dn e s e t r i lf o r m u l a t e dt h ef o l l o w i n g v i s i n g - t y p ep r o b l e m ：g i v e na nu p p e rb o u n d f o rs q ( g ) i nt e r m so f ( g ) ，t h em a x i m u m d e g r e eo fg 。t h e ya l s oc o n j e c t u r e d ( s e ef 3 】) t h a t 凹( g ) ；2 ( g ) b yp - h o r i ke ta lf 6 】，i f gi sag r a p hw i t ha ( g ) s3 ，t h e ns q ( g ) = 1 0 8 1 3 s o m er e s u l t so i li n d u c e dm a t c h i n g i nt h i ss e c t i o n ，w el i s ts o m e r e s u l t ，s o i li n d u c e dm a t c h i n g so fag r a p h t h e o r e m1 ( c a m e r o n ，【2 1 ) t h ei n d u c e dm a t c h i n gp r o b l