（应用数学专业论文）强乘积图与字典乘积图的限制边连通性.pdf

五邑大学硕士学位论文 摘要 本文研究正则图的强乘积图和字典乘积图的限制边连通性。连通图g 的边割s 被称为坍限制边割，如果g s 的每个连通分支至少包含m 个顶点。最小的m 限制边 割所含的边数屯( g ) 称为g 的m 限制边连通度。用专。( g ) 表示只有一个端点在给定 的扰阶连通点导出子图的边集所含的边数。已经知道，当m 3 时，对于所有含m 限制 边割的图g ，都有丸( g ) 考。( g ) 。如果九( g ) = 考。( g ) ，则图g 被称作极大m 限制边 连通图；如果图g 的任意最小m 限制边割一定分离出一个m 阶连通分支，那么图g 被称作超级m 限制边连通图。 在本文中，我们主要得出以下结果： 定理2 1 7 如果g ，和g ，是两个度不小于2 的超级边连通正则图，则它们的强乘 积图g ，0 g ，是超级边连通的 定理2 2 3 如果g 和g ：是两个度不小于2 的极大边连通正则图，则它们的强乘 积图g 0 g ，是超级限制边连通的 定理3 2 1 设g ，是k ，正则图，k ，2 ，江1 , 2 如果z ( a ，) = k l ，x ( 6 2 ) = k 2 - 1 ，那 么字典序乘积图g 1o g ，极大限制边连通的 定理3 3 3 设g ，和g ，是两个度至少为2 的正则图如果它们是极大边连通的， 那么字典序乘积图g o g ，是超级限制边连通的 关键词：强乘积图；字典乘积图；极大限制边连通性；超级限制边连通性；正则图 五邑大学硕士学位论文 a b s t r a c t i nt h i sa r t i c l e ，w es t u d yt h er e s t r i c t e de d g ec o n n e c t i v i t yo fs t r o n gp r o d u c ta n d l e x i c o g r a p h i cp r o d u c to fr e g u l a rg r a p h s a ne d g ec u tso fac o n n e c t e dg r a p hgi s c a l l e dm - r e s t r i c t e di fg sc o n t a i n sn oc o m p o n e n t so fo r d e rl e s st h a nm t h es i z e 丸( g ) o fm i n i m u mm r e s t r i c t e de d g ec u t so fg r a p hgi sc a l l e di t s m r e s t r i c t e de d g e c o n n e c t i v i t y l e t 、孝。( g ) d e n o t et h em i n i m u ms i z eo fs e t so fe d g e sw i t he x a c t l yo n ee n d i na n yg i v e nc o n n e c t e dv e r t e x i n d u c e ds u b g r a p ho fo r d e r m i ti sk n o w nt h a tw h e n m 3 ，丸( g ) 毒。( g ) h o l d sf o rg r a p hgt h a tc o n t a i n s m r e s t r i c t e de d g ec u t s g r a p h gi sc a l l e dm a x i m a l l ym - r e s t r i c t e de d g ec o n n e c t e di f 丸( g ) = 孝，( g ) ，a n ds u p e r m r e s t r i c t e d e d g ec o n n e c t e di fa n ym i n i m u mm r e s t r i c t e de d g e c u ts e p a r a t e sa c o m p o n e n to fo r d e r m i nt h i st h e s i s ，w eo b t a i nt h ef o l l o w i n gr e s u l t s t h e o r e m 2 1 7 i f g la n dg 2a r es u p e re d g ec o n n e c t e dr e g u l a rg r a p h sw i t h d e g r e ea tl e a s tt w o ，t h e ng l g 2i ss u p p e r - 2 t h e o r e m 2 2 3i f g l a n dg 2a r em a x i m a l l ye d g ec o n n e c t e dr e g u l a rg r a p h s w i t hd e g r e ea tl e a s tt w o ，t h e n g log 2 i ss u p p e rr e s t r i c t e de d g ec o n n e c t e d t h e o r e m 3 2 1l e tg fb e k ，一r e g u l a rg r a p h sw i t hk ，2 ，i = 1 , 2 i fa ( g 1 ) = k 1 a n da ( g 2 ) = 如一1 ，t h e ng log 2i sm a x i m a lr e s t r i c t e de d g ec o n n e c t e d 。 t h e o r e m 3 3 3l e tg la n dg 2b et w or e g u l a rg r a p h sw i t hd e g r e ea tl e a s tt w o i ft h e ya r em a x i m a l l ye d g ec o n n e c t e d ，t h e ng l 。g 2i ss u p e rr e s t r i c t e de d g ec o n n e c t e d k e yw o r d s ：s t r o n gp r o d u c tg r a p h s ；l e x i c o g r a p hi cp r o d u c tg r a p h s ；m a x i m a lr e s t r i c t e de d g ec o n n e c t i v i t y ；s u p e rr e s t r i c t e de d g ec o n n e c t i v i t y ；r e g u l a rg r a p h s i i 本人声明 我声明，本论文及其研究工作由本人在导师指导下独立完成，完成论文所用的 一切资料均已在参考文献中列出。 作者：黄兰芝 签字：遗影 k 一 2 0 0 9 年4 月5 日 c h a p t e r1 g r a p h sa n dp r o d u c tg r a p h s 1 1e d g ec o n n e c t i v i t y a l lg r a p h sc o n s i d e r e di nt h i st h e s i sa r es i m p l e ，u n d i r e c t e da n dc o n n e c t e d i fn o ts p e c i f i e d ，a l lg r a p h t h e o r e t i c a lt e r m i n o l o g i e sa n dn o t a t i o n sa p p e a r i n g i nt h i st h e s i sf o l l o wt h a to f 1 l e ta ( g ) d e n o t et h ee d g ec o n n e c t i v i t yo fa g r a p hg i ti sw e l l - k n o w nt h a t 入( g ) 6 ( g ) c o n n e c t i v i t yi so n eo ft h em o s tb a s i ca n di m p o r t a n ti n v a r i a n t so fg r a p h s i ni n t e r c o n n e c t i o nn e t w o r k s ，c o n n e c t i v i t y ，e d g e - c o n n e c t i v i t y t o g e t h e rw i t h o t h e rc o n c e p tr e l a t e dt ot h ec o n n e c t i v i t y , s u c ha sm a x i m a l l yc o n n e c t e da n d s u p e rc o n n e c t e d ，a r cu s e f u lp a r a m e t e r st om e a s u r et h er e l i a b i l i t ya n df a u l t t o l e r a n c eo fi n t e r c o n n e c t i o nn e t w o r k s f o rm o s ti n t e r c o n n e c t i o nn e t w o r k s t h a ta r eu s e di np r a c t i c e ，t h e i ru n d e r l y i n gt o p o l o g i c a ls t r u c t u r ec a nb cd c - f i n e du s i n gp r o d u c tg r a p h s t h u s ：t h es t u d yo fc o n n e c t i v i t yo fp r o d u c tg r a p h s i sn o to n l yf u n d a m e n t a li nt h et h e o r yo fp r o d u c tg r a p h s ，b u ta l s oh a sa p p l i c a t i o ni ni n t e r c o n n e c t i o nn e t w o r k s d e f i n i t i o n1 1 1ag r a p hg i sm a x i m a l l ye d g ec o n n e c t e do rs i m p l ym a x - a ，i f 入( g ) = 6 ( g ) d e f i n i t i o n1 1 2ag r a p hg i ss u p e re d g ec o n n e c t e do rs u p e r - k ，i fe v e r y m i n i m u me d g ec u ts e p a r a t e sa ni s o l a t e dv e r t e x i ti sn o td i f f i c u l tt os e et h a tas u p e re d g ec o n n e c t e dg r a p hi sa l s om a x i - m a l l ye d g ec o n n e c t e d ，b u tt h ec o n v e r s ei sn o tt r u e d e f i n i t i o n1 1 3ar e s t r i c t e de d g ec u ti sa ne d g ec u to fac o n n e c t e d g r a p hw h i c hs e p a r a t e st h i sg r a p hi n t oc o m p o n e n t sw i t h o u ti s o l a t e dv e r t i c e s r e s t r i c t e de d g ec o n n e c t i v i t y ，d e n o t e db ya 2 ，i st h es i z eo fa m i n i m u mr e s t r i c t e d e d g ec u t 五邑大学硕士学位论文 d e f i n i t i o n1 1 4ag r a p hgi ss u p e rr e s t r i c t e de d g ec o n n e c t e di fe v e r y m i n i m u mr e s t r i c t e de d g ec u ts e p a r a t e sa ni s o l a t e de d g e s u p e re d g ec o n n e c t i v i t ya n dr e s t r i c t e de d g ec o n n e c t i v i t ya r eu s e f u lt o o l s f o ro p t i m i z i n gr e l i a b i l i t yo ft e l e c o m m u n i c a t i o nn e t w o r k s ，a n dd r a wal o to f a t t e n t i o n s 2 ，3 ，4 j 1 2s t r o n ga n dl e x i c o g r a p h i cp r o d u c tg r a p h s r e c e n t l y , t h es t u d yo fp r o d u c tg r a p h sh a sb e e na na c t i v ea r e ao fg r a d h t h e o r y e l e g a n ta n ds y s t e m a t i ct h e o r yh a sb e e nb u i l to nt h es t r u c t u r ea n d r e c o g n i t i o na l g o r i t h m so ff o u ，rk i n d so fs t a n d a r dp r o d u c t so fg r a p h s ( t h ec a r t e - s l a np r o d u c t ，t h es t r o n gp r o d u c t ，t h el e x i c o g r a p h i ep r o d u c ta n dt h ed i r e c t p r o d u c t ) m o r e o v e r ，t h es u b j e c to fp r o d u c tg r a p h sa n di n v a r i a n t si sa l w a y s as u b j e c tt h a ti sf u l lo fc h a l l e n g i n gp r o b l e m s i nt h ey e a r2 0 0 0 i m r i c ha n d kl a v 三, a rw r o t eam o n o g r a p hp r o d u c tg r a p h s 1 4 w h i c hs u m m a r i z e da l lt h e a b o v em e n t i o n e di n f o r m a t i o na b o u tp r o d u c tg r a p h s i nt h i ss e c t i o n ，w ei n t r o d u c et h ec o n c e p t sa n ds o m ek n o w nr e s u l t so f s t r o n ga n dl e x i c o g r a p h i cp r o d u c tg r a p h s l e tg 1a n dg 2b et w ov e r t e x - d i s j o i n tg r a p h st h a th a sv e r t e x - s e t s ， a n d e d g e s e t s 局，易，r e s p e c t i v e l y l e tm = i k ia n d 毛= l 易l ，i = 1 ，2 d e f i n i t i o n1 2 1s t r o n gp r o d u c tg 1 g 2o ft w og r a p h sg 1a n dg 2i s d e f i n e do nv e r t e x - s e tv ( g 1 ) v ( c 2 ) ，w h e r et w ov e r t i c e s u ，z ) ，( u ，y ) a r ea d j a c e n tt oe a c ho t h e ri fa n do n l yi f 札= a n dx y e ( g 2 ) ，o rz =ya n d u u e ( g 1 ) ，o ru u e ( g 1 ) a n dx y e ( c 2 ) i fv ( k 2 ) = a ，6 ) ，w ew r i t e 鲍o g = 托o g e ( 是1 k 2 + 岛+ 如。 s i m i l a r l y , w eh a v ea ( g 2 ) ( n 1 + 2 m 1 ) k 2 ( h + 1 + 2 k 1 ) k 2 k l + k 2 + k 1 口 f o ra n yv e r t e xu y ( g 1 ) ，l e tg ；d e n o t et h es u b g r a p ho fg 1o g 2i n d u c e d b y 1 0 y ( g 2 ) a n dg d e n o t e sas i m i l a rs u b g r a p hf o ra n yv e r t e x t v ( g 2 ) s u b g r a p hg ；i sc a l l e ds e p a r a t e db ys i fg ；nf da n dg ；n 亏毋l e tr d e n o t et h en u m b e ro fs u b g r a p h sg ；，u y ( g 1 ) ，t h a ta r es e p a r a t e db ys ，a n d 4 st h en u m b e ro fs u b g r a p h sg ， v ( c 1 ) =i ) 1 ，现，v n l a n d & w r i t es e = sn g ，g 翔 乱v ( c 2 ) ，t h a ta r es e p a r a t e db ys w r i t e = sng f o re v e r ye d g ee = x y e ( g 1 ) ， l e m m a2 1 5l e tsb ea l le d g ec u to fg log 2w i t hi s is ( g 1qg 2 ) i fg 1a n dg 2a r em a x i m a l l ye d g ec o n n e c t e d ，t h e nn l r ，s 1 p r o o f i fr ：0 ，t h e ng ；i sc o n n e c t e df o re v e r y 移y ( g 1 ) f o rs o m e f i x e dc o m p o n e n tco fg 1 圆g 2 一s ，l e tab et h es u b s e to fv ( g 1 ) s u c ht h a t g ；ci fa n do n l y i fx a t h e nu z 可，匈 g 耋，g ； s - f r o mt h em a x i m a l e d g ec o n n e c t i v i t yo fg l ，w ed e d u c et h a t s i 2 a ( g 1 ) ( 礼2 + 2 m 2 ) = k l ( ? 2 2 + n 2 k 2 ) k l ( ( + 1 ) + ( 2 + 1 ) k 2 ) 岛+ 2 k l 也七1 ，碚+ 2 k l + 2 k 2 2 ( k l k 2 + 七1 + 如) 一2 = ( g 1 qg 2 ) i fr ：礼1 ，t h e ng 蓦一si sd i s c o n n e c t e df o re v e r yu y ( g 1 ) c o m b i n i n gt h i s o b s e r v a t i o nw i t hl c m m a 2 1 2 。w eh a v e r 1 1 s l i & l + 倒 i = l e e e ( g 1 ) n 1 入( g 2 ) + 2 m l a ( g 2 ) = n l k l k 2 + n l k 2 ( g loc 2 ) t h el a s ti n e q u a l i t yh o l d ss i n c e 2a n d 佗t 3 ，i = 1 ，2 l e m m a2 1 5 f d l o w sf r o mt h e s et w oc o n t r a d i c t i o n sa n dt h es y m m e t r yo fg ia n dg 2i n g l g 2 口 l e m m a2 1 6 1 5 l e tgb eac o n n e c t e dg r a p h ，a n dd acy ( g ) t h e n i a i + f a ，a 】l 6 + l ，w i t he q u a l i t yh o l d i n gi fa n do n l yi fa i sar a i n l m u m 。 d e g r e ev e r t e x 5 五邑大学硕士学位论文 t h e o r e m2 1 7i fg 1a n dg 2a r es u p e re d g ec o n n e c t e dr e g u l a rg r a p h s w i t hd e g r e ea tl e a s tt w o ，t h e ng iog 2i ss u p p e r 一入 p r o o f l e ts = i f 同b eam i n i m u me d g ec u to fg=g1 og 2w i t h i f i ( 如+ 1 ) ( k 2 + 1 ) ( 忌1 + 1 ) ( k 2 + 1 ) k 1 + 如+ 七1 如 6 五邑大学硕士学位论文 w h e n a k l + k 2 + k l 七2 t h ea b o v et w oc o n t r a d i c t i o n ss h o wt h a tp = 1 h e n c e ，q 乜n o t i n g t h a tb n 一1a n da + e 惫l + 1 ，w eh a v e s ia q + 2 b q + p ( k s + 1 ) + ( c 一1 ) ( 乜+ 1 ) a k 2 + 2 ( a 一1 ) k 2 + c ( k 2 + 1 1 = ( a + c ) ( k s + 1 ) + 2 ( a 一1 ) 尼2 一a ( 七1 + 1 ) ( k 2 + 1 ) + ( a 一1 ) 一a = 七1 + 乜+ k l 忌2 h e n c e ，j s i = k l + k s + k l k sa n da l lt h ee q u a l i t i e sh o l di na b o v ef o r m u l a t h e r e f o r e ，a = 1 ，c = 七1 ，q = k s ，b = a 一1 ，s = s 1u & ，。ku ( u 。e s ：) ， i s i = q = 七2 ，i & 1 i = 七2 + l ，a n di & l = 七2 + 1f o re v e r ye e + h e n c e ，f i sa ni s o l a t e dv e r t e xi ng 1 岛一s 口 2 2s u p e rr e s t r i c t e de d g ec o n n e c t i v i t y i nt h i ss e c t i o n ，w es t u d yt h er e s t r i c t e de d g ec o n n e c t i v i t yo fs t r o n gp r o d u c to fr e g u l a rg r a p h s t h em a i nr e s u l to ft h es e c t i o ni st h e o r e m2 2 3 ：w h i c h p r e s e n t sas u f f i c i e n tc o n d i t i o no fs u p e rr e s t r i c t e de d g ec o n n e c t i v i t y l e m m a2 2 1i fg 1q g si sn o tm a x i m a l l yr e s t r i c t e de d g ec o n n e c t e d t h e nr 2 7 五邑大学硕士学位论文 p r o o f is u p p o s et ot h bc o n t r a r yt h a trs1 t h e nr = tb yl c m m a2 1 5 ， a n dfcg f o rs o m ev e r t e xv i v ( c 1 ) s i n c eg 1og 2i sn o tm a x i m a l l y r e s t r i c t e de d g ec o n n e c t e d ，i tf o l l o w st h a tf l 3 h e n c e ， i s t ( d e 。& g ：( 牡) 一嘞( 牡) ) + 蚓 u e v ( f ) 3 ( k l 也+ 七1 ) + 也 2 k l k 2 + 2 k l + 2 k 2 ( g 1og 2 ) t h el e m m af o l l o w sf r o mt h i sc o n t r a d i c t i o n 口 l e m m a2 2 2i fg 1a n dg 2a r em a x i m a l l ye d g ec o n n e c t e dr e g u l a rg r a p h s w i t hd e g r e ea tl e a s tt w o ，t h e ng 10g 2i sm a x i m a l l yr e s t r i c t e de d g ec o n n e c t e d p r o o f s u p p o s et ot h ec o n t r a r yt h a tg 10g 2i sn o tm a x i m a l l yr e s t r i c t e d e d g ec o n n e c t e d l e ts b eam i n i m u mr e s t r i c t e de d g ec u to fg 10g 2 ，fa n d fb et h et w oc o r r e s p o n d i n gc o m p o n e n t sw i t hi f i i f i b yl e m m a2 2 1 ， w eh a v er 2 a s s u m ew i t h o u tl o s so fg e n e r a l i t yt h a tg ；1a n dg ；2a r e d i s c o n n e c t e d t h e n ，i g ；1nfg ；1nf g ；2neq 2 nf i a ( g 2 ) w e s h a l ld i s c u s si nt w od i s t i n c ts i t u a t i o n s 7 c a s e 7 f o re v e r yv e r t e xz y ( g 1 ) 一v l ，忱) ，e i t h e r 哦cfo rf s u b c a s e f f a l ls u b g r a p h sg ，x y ( g 1 ) 一 u 1 ，v 2 ，a r ec o n t a i n e di n t h es a m ec o m p o n e n t 。s a yf s i n c eg 1 圆g 2i sn o tm a x i m a l l yr e s t r i c t e de d g e c o n n e c t e d ，i tf o l l o w st h a tf l 3 a n ds o ，g 1 1af o rg ；2nf ，s a yt h ef o r m e r ， c o n t a i n st w ov e r t i c e s ( y l ，磁) a n d ( u 1 ，吩) s i n c eg a n dg a r es e p a r a t e d ， i s n e ( c ) i ，l s n e ( g ：j ) i a ( g 1 ) f o re v e r ye d g ee = x y 哦1n f , g ；1n f ， b yl e m m a2 1 3w eh a v et h a ti sn v l ，z ) ，g 圳k l + 1 s i m i l a r l y , f o re v e r y e d g ee = u v 【g ；2neg ；2nf ，w eh a v et h a ti sn v 2 ，u ) ，g i 七1 + 1 c o n s e q u e n t l y , s l i sne ( g 剐+ l s ne ( g ) i + i sn ，z ) ，g 矧+ t 口f g ；2 n f , g ；2 n 同 2 a ( c i ) + k 2 ( k l ( g 1o c 2 ) 列【g ；1n t , a ；1n 同 s n fv 2 ，札) ，g 剐 - i - 1 ) + k 2 ( k l + 1 ) 22 k l + 2 k l k 2 + 2 k 2 8 ( 1 ) 五邑大学硕士学位论文 s u b c a s e _ f 2 t h e r ea r et w ov e r t i c e su i ，y ( g 1 ) 一i ) 1 ，v 2 s f i c ht h a t + g cfa n dg c 户i nt h i sc a s e ，g fi ss e p a r a t e df o re v e r yv e r t e xx v ( e 2 ) a n ds o ，f o r m u l a ( 1 ) i ss t i l lt r u ci f ( u 1 ，饥) i sav e r t e xo fg ；1nfa n d ( v l ，) i sav e r t e xo fg ；1nf c a s e2 t h e r ei sav e r t e xz v ( c 1 ) 一v l ，v 2 s u c ht h a tg ii sa l s o s e p a r a t e d e m p l o y i n gt h e m e t h o du s e di nd e d u c i n gt h el a s tt w op a r t so f f o r m u l a ( 1 ) ，w eh a v et h a t s i i sn ，z ) ，g ! j 】j + z v 【g ；1a f , g ；1n 司 i sn 【v 2 ，u ) ，g 剐+ t 口 g ；2nf ，g ；2n 司 l sn z ，u ) ，g 圳 t u 【g ；n f g n 同 3 a ( g 2 ) ( k l + 1 1 2 k 2 + 2 k l k 2 + 2 k l ( g 1og 2 ) l e m m a2 2 2f o l l o w sf r o mt h e s ec o n t r a d i c t i o n s 口 t h e o r e m2 2 3i fg aa n dg 2a r e g r a p h sw i t hd e g r e ea tl e a s tt w o ，t h e ng 1 n e c t e d m a x i m a l l ye d g ec o n n e c t e dr e g u l a r 0g 2i ss u p p e rr e s t r i c t e de d g ec o n - ，p r o o f l e ts = f ，f 】b eam i n i m u mr e s t r i c t e de d g ec u to fg 1o g 2 w i t hi f i 吲b yl e m m a2 2 2 ，i ts u f f i c e st os h o wi f i = 2 l e t7 d e n o t e t h en u m b e ro fv e r t i c e sz v ( g 1 ) s u c ht h a tg i ss e p a r a t e db ys ，a n dtt h e n u m b e ro fv e r t i c e sy v ( c 2 ) s u c ht h a tg i ss e p a r a t e db ys a si ss h o w n i nc a s e2o ft h ep r o o fo fl e m m a2 2 2 ，rs2a n dt 2 s i n c ei f i i f i22 ， i tf o l l o w st h a t7 = 2o rt = 2 b yt h es y m m e t r yo fg 1a n dg 2i ng 10g 2 ， w em a ya s s u m ew i t h o u tl o s s o fg e n e r a l i t yt h a t7 = 2 ，a n dt h a tq 1 ，g ；2a r e s e p a r a t e d i ft = 2 ，t h e nf o r m u l a ( 1 ) w o u l db es t i l lt r u e h e n c e ，t = 1a n df i sa ni s o l a t e de d g ei ng 1qg 2 一s 口 9 五邑大学硕士学位论文 2 3 m a x i m a lr e s t r i c t e de d g ec o n n e c t i v i t yo f 鲍0g i nt h i ss e c t i o n ，w et u r no u ra t t e n t i o nt ot h er e s t r i c t e de d g ec o n n e c t i v i t y 鲍0g t h em a i nr e s u l to ft h i ss e c t i o ni st h e o r e m2 3 2 w h i c hs h o w st h a t 鲍圆gi sm a x i m a l l yr e s t r i c t e de d g ec o n n e c t e d l e m m a2 3 1 虬o i ss u p e rr e s t r i c t e de d g ec o n n e c t i v i t y p r o o f s i n c e 七l = 1a n d 如= 1 ，g 10g 2 = 鲍0 = 致i ti s c l e a r l yt h a t 托i ss u p e rr e s t r i c t e de d g ec o n n e c t i v i t y h e n c e ，g l g 2i ss u p e r r e s t r i c t e de d g ec o n n e c t i v i t y 口 t h e o r e m2 3 2l e tgb eam a x i m a l l ye d g ec o n n e c t e dk - r e g u l a rg r a p h w i t hk 2 t h e nt h es t r o n gp r o d u c tg r a p h 鲍ogi sm a x i m a l l yr e s t r i c t e d e d g ec o n n e c t e d p r o o f l e ts = 只同b eam i n i m u mr e s t r i c t e de d g ec u to f 拖ogw i t h f i l 户1 s u p p o s et ot h ec o n t r a r yt h a t 施og i sn o tm a x i m a l l yr e s t r i c t e d e d g ec o n n e c t e d t h e ni s i ( 鲍 g ) ；f i n a l l y w ec o n s i d e rt h ec a s ew h e nf 亏qa n d 乒f q a s s u m ew i t h o u tl o s so fg e n e r a l i t yt h a t ( ( ，z ) ，( b ，z ) ) f f t h e ns = fu ( n ，z ) ，f ( n ，z ) ) ) a n ds = fu ( 6 ，z ) ) ，户 ( 6 ，z ) ) a r ea l s or e - s t r i c t e de d g ec u to f 拖og 1 0 f o re v e r yv e r t e x 可g a ( x ) ，v e r t e x - p a i r ( ( 口，可) ，( 6 ，可) ) f 户，( ( 口，可) ，( 匆，夕) ) 户f ，( ( 口，) ， ，) ) f fo r ( ( n ，) ，( 妇，可) ) f f i ne v e r yo ft h c s c f o u rc 嬲， d i s c u s s i o no nw h e t h e rt h et w oe d g e ( o ，z ) ( o ，y ) s ，( 6 ，z ) ( 6 ，y ) s 7o r ( a ，。) ( 玩z ) s 7l e a d st ot h ef o l l o w i n g s i = l s l - 2 ( c a c 4 ) _ 1 s i m i l a r l y ，i s ，l = i s l 一2 ( c 4 一c 3 ) - 1 h e n c el s i + l s l = 2 l s i 一2 t h e r e f o r e ，