（应用数学专业论文）笛卡尔乘积图与直接乘积图的限制边连通性.pdf

五邑大学硕士学位论文 摘要 本文研究正则图的笛卡尔乘积图与直接乘积图的限制边连通性设g 是任意连通图， 邻( g ) = r a i ni ：sce ( g ) 且g s 是个偶图 图g 的一个边割s 称为m 限制边割，如 果g s 不包含阶数小于m 的连通分支图g 的最小m 限制边割的边数五。( g ) 称为它的m 限 制边连通度用岛( g ) 表示只有一个端点在任意给定的m 阶点导出予图中的最小边集的边 数已知，当g n 3 j | g 含m 限制边割时，有a 。( g ) 靠( g ) 若厶( g ) = 岛( g ) ，则称图g 是极 大m 限制边连通的：若每一个最小m 限制边割都分离出一个m 阶连通分支，则称图g 是超 级m 限制边连通的用g 1 口g 2 ，g lxg 2 分别表示图g 1 与g 2 的笛卡尔乘积图，直接乘积图 在本论文中，我们得到了如下的结果： 定理2 1 7 设g f 是极大边连通k f 正则图且k i 2 ，f = 1 ，2 则g 1 口g 2 是超级限制边连通 的当且仅当g 1 口g 2 箬羁口g 定理2 2 9 设g f 是极大边连通岛正则图且岛3 ，江1 ，2 ，g ( g 1 g 2 ) = 3 则g 】v g 2 是超 级3 限制边连通的当且仅当g 1 日g 2 箬k 口g ，其中g 是3 正则图 定理2 3 i 设g f 是极大边连通k f 正则图且足i23 ，g ( g 。) 4 ，i = l ，2 贝, 1 g 1 1 - l g 2 是超 级3 限制边连通的 定理3 1 5 设g j 是极大边连通非偶图，且筇( g f ) 6 i , i = 1 ，2 则g 】g 2 是超级边连通 定理3 2 2 设g f 是正则非偶图，且k f 3 ，i = l ，2 若g f 是超级限制边连通的且帮( g f ) 3 岛一2 n g l g 2 是超级限制边连通的 关键词：笛卡尔乘积图；直接乘积图；m 限制边连通性；正则图 五邑大学硕士学位论文 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 fc a r t e s i a np r o d u c ta n dd i r e c t p r o d u c t o fr e g u l a rg r a p h s f o ra n yc o n n e c t e dg r a p hg ，l e tf l ( g ) = m 2 n l sl ：sce ( g ) a n dg - s i sa b i p a r t i t eg r a p h 】a ne d g e c u tso fgi sc 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 r , a p o n e n t s o fo r d e rl e s st h a nm t h es i z em ( 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 d i t sm r 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 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 h e x a c t l yo n ee n di 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 rm i ti sk n o w nt h a t w h e nm 3 ， n ( g ) 南( g ) h o l d sf o rg r a p h gt h a tc o n t a i n sm r e s t r i c t e de d g ec u t s g r a p hg i 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 m ( g ) = 靠。( g ) ，a n ds u p e rm - r e s t r i c t e de d g e c 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 ec u ts e p a r a t e sac o m p o n e n to fo r d e r ，7 z l e tg iv i g 2 a n dg 】xg 2d e n o t et h ec a r t e s i a n p r o d u c ta n ds t r o n gp r o d u c to fg r a h p sg 1a n dg 2 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 m2 1 7i tg ib ea m a x i m a l l ye d g ec o n n e c t e dk i - r e g u l a rg r a p hw i t hk i 2 ，i = 1 ，2 t h e ng i 口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 di fa n do n l yi fi ti sn o ti s o m o r p h i ct o 疋口c 小 t h e o r e m2 2 9l e tg ib eam a x i m a l l ye d g ec o n n e c t e dk i r e g u l a rg r a p h sw i t hk i 3 ，i = 1 ，2a n dg ( gll - - i g 2 ) = 3 t h e ng ai - 1 g 2i ss u p e r3 - r e s t r i c t e de d g ec o n n e c t e di fa n do n l yi fi ti s n o ti s o m o r p h i ct o e 3 g ，w h e r egi s3 - r e g u l a r t h e o r e m2 3 1l e tg ib eam a x i m a l l ye d g ec o n n e c t e d 足f - r e g u l a rg r a p hw i t hk i 3a n d g ( g i ) 4 1i = 1 ，2 t h e ng 1v i g 2i ss u p e r3 - r 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 m3 1 5l e tg ib eas u p e re d g ec o n n e c t e dn o n b i p a r t i t eg a p hw i t h2 f 3 ( g i ) 6 i ，i = 1 ，2 t h e ng 1xg 2i ss u p e re d g ec o n n e c t e d t h e o r e m3 2 2l e tg ib eak i r e g u l a rn o n b i p a r t i t eg r a p hw i t hk i 3 ，i = 1 ，2 i fg ii ss u p e r r e s t r i c t e de d g ec o n n e c t e da n d2 f l ( g i ) 3 k i 一2 ，t h e ng 1x 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 y w o r d s ：c a r t e s i a np r o d u c tg r a p h s ；d i r e c tp r o d u c tg r a p h s ；m r 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 i 五邑人学硕士学位沦文 本人声明 本人郑重声明：所呈交的学位论文及其研究工作由本人在导师指导下独立完成，完 成论文所用的一切资料均已在参考文献中列出。 作者：余碧新 签专会物 2 0 0 9 年霸笳f ， 五邑人学硕士学位论文 c h a p t e r1 g r a p h sa n dp r o d u c t g r a p h s 1 1 e d g ec o n n e c t i v i t y a l lg r a p h sa p p e a r i n gi 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 f o rg 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 sn o ts p e c i f i e di nt h i st h e i s ，w ef o l l o wt h a to f 【l 】l e t gb eac o n n e c t e du n d i r e c t e dg r a p hw i t hm i n i m u md e g r e e6 ( g ) i ti sw e l l k n o w nt h a ti t se e c o n n e c t i v i t ya ( g ) 吠g ) d e f i n i t i o n1 1 1a g r a p hg i ss a i dt ob em a x i m a l l ye ec o n n e c t e do rs i m p l ym a x 一1 ，i fi t s e d g ec o n n e c t i v i t y ( g ) = 6 ( g ) d e f i n i t i o n1 1 2a g r a p hg i sc a l l e ds u p e re d g ec o n n e c t e do rs u p e r 一五i fe v e r ym i n i m u m e d g ec u ts e p a r a t e sav e r t e xf r o mg i ti sn o td i f f i c u l tt o 。s 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 w h e nm o d e l l i n gr e l i a b i l i t yo fc o m m u n i c a t i o nn e t w o r k s ，o n eo f t e na s s u m et h e i rn o d e s n e v e rf a i lb u te d g e sf a i li n d e p e n d e n t l yo fe a c ho t h e rw i t he q u a lp r o b a b i l i t y t h i sk i n do fn e t w o r k m o d e l sa r en o wc a l l e dm o o r e - s h a n n o no n e s 【3 8 - 3 9 l e tmb eam o o r e s h a n n o nn e t w o r k m o d e lw i t hs i z eea n d e d g ef a i l u r ep r o b a b i l i t yp i fd e n o t eb yc ht h en u m b e ro fi t se d g ec u t so f s i z eh ，t h e ni t sr e l i a b i l i t y , n a m e l yt h ep r o b a b i l i t yi tr e m a i n sc o r m e c t e d n e s s ? c a nb ee x p r e s s e da s 尺( m p ) = 1 一c h p “( 1 - p ) 蹦 矗= l i fo n ec a nd e t e r m i n ea l lt h ec o e f f i c i e n t sc h ，h ed e t e r m i n e st h er e l i a b i l i t y b u t ，u n f o r t u n a t e l y , p r o v a n p r o v e di n 4 】t h a ti ti sn p h a r dt od e t e r m i n ea l lt h e s ec o e f f i c i e n t s e m p l o y i n g s u p e re d g ec o n n e c t n i t y ，b a u e r 【5 c a l c u l a t e st h ef i r s ta c o e f f i c i e n t sc h ，w h e r e i st h ee d g ec o n n e c t i v i t yo fm t oe s t i m a t et h er e l i a b i l i t ym o r ep r e c i s e l y , e s f a h a n i a ni n t r o d u c e st h ec o n c e p t s o fr e s t r i c t e de d g ec u ta n dr e s t r i c t e de d g ec o n n e c t i v i t yi n 6 d e f i n i t i o n1 1 3ar e s t r i c t e de ec u ti sa l le d g ec u to fac o n n e c t e dg r a p hw h i c hs e p a r a t e s t 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 yi st h es i z eo f am i n i m u mr e s t r i c t e de d g ec u t 五邑人学硕士学位论文 w i t ht h ep r o p e r t i e so fr e s t r i c t e de d g ec u ta n dr e s t r i c t e de d g ec o n n e c t i v i t y , l id e t e r m i n e s t h ef i r s ta 2 1c o e f f i c i e n t sc ho fc f f c u l a n tg r a p h si n 【7 ，w h e r ea 2d e n o t e st h er e s t r i c t e de d g e c o n n e c t i v i t y a sw a sp o i n t e do u tb ye s f a h a n i a n ，t h er e s t r i c t e de d g ec u ti sa l s oau s e f u lt o o lf o r f a u l t t o l e r a n c ea n a l y s i s b u tt h e i rr e s u l t sa r ef a i r l ya p p r o x i m a t e f o rm o r ea c c u r a t er e s u l t s ，t h e o ug e n e r a l i z e st h e s ec o n c e p t si n 【8 ，4 0 d e f i n i t i o n1 1 4a nm r e s t r i c t e de d g ec u t ，o rs i m p l ya n 如e d g ec u t ，i sa ne d g ec u to fa c o n n e c t e dg 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 se a c hh a v i n go r d e ra tl e a s tt n t h e s i z eo fam i n i m u mm r e s t r i c t e de d g ec u to fag r a p hi sc a l l e di t sr n 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 eb y 厶( g ) t h em r e s t r i c t e de d g ec o n n e c t i v i t yo fag r a p hg c l e a r l y , 1 - r e s t r i c t e d e d g ec o n n e c t i v i t yi st h et r a d i t i o n a le d g ec o n n e c t i v i t y ，a n d2 - r e s t r i c t e de d g ec o n n e c t i v i t yi st h e s o c a l l e dr e s t r i c t e de d g ec o n n e c t i v i t y s i n c er m e d g ec u ta n dc o n n e c t i v i t ya r ei m p o r t a n ti n t h e i ro w n r i g h ti nt h ea n a l y s i so fr e l i a b i l i t ya n df a u l t t o l e r a n c e ，t h e yd r a wal o to fa t t e n t i o n ，t h e r e a d e r sa r es u g g e s t e dt or e f e r st o ( 9 - 1 0 】f o re x a m p l e f o rt h ee x i s t e n c eo fa nr ，z e d g ec u t ，t h e a u t h o rp r e s e n t sas u f f i c i e n ta n dn e c e s s a r yc o n d i t i o ni n 4 0 】 l e txb eas u b s e to fv ( g ) o ra s u b g r a p ho fg r a p hg t h e ng xd e n o t e st h eg r a p ho b t a i n e d b yr e m o v i n gt h ev e r t i c e si nxf r o mg l e ta ( d e n o t e st h en u m b e ro fe d g e sw i t ho n ee n di n xa n dt h eo t h e ri ng x l e t 南( g ) = m i n a ( 的：xi sac 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 f o r d e rm ) i ti sp r o v e dt h a t 1 2 ( g ) 邑( g ) a n d 允3 ( g ) 螽( g ) i n 1 2 - 1 3 d e f i n i t i o n1 1 5a g r a p hg i sc a l l e dm a x i m a l l y3 - r e s t r i c t e de ec o n n e c t e do rm a x i m a l l y r 3 一e d g ec o n n e c t e di f 1 3 ( g ) = 岛( g ) a n ds u p e r3 - r e s t r i c t e de d g ec o n n e c t e do rs u p e rr 3 - e d g e c o n n e c t e di fe v e r ym i n i m u m r 3 - e d g ec u ts e p a r a t e sac o m p o n e n to f o r d e r3 1 a d y m 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 da n ds u p e rr e s t r i c t e de d g ec o n n e c t e di sd e f i n e ds i m i f o ra n ym i n i m u m r m e d g ec u tso fg ，g sc o n t a i n se x a c t l yt w oc o m p o n e n t s ，b o t ha r e c a l l e dt h er m f r a g m e n t so rs i m p l yf r a g m e n t sc o r r e s p o n d i n gt os f r a g m e n t sw i t hm i n i m u m c a r d i n a l i t ya r ec a l l e da t o m s t h el e n g t ho ft h es h o r t e s tc y c l eo fg r a p hg ，d e n o t e db yg ( g ) ，i s c a h e di t sg i r t l l ，w h i l et h el o n g e s to n e ，d e n o t e db yc ( g ) ，i sc a l l e di t sc i r c u m f e r e n c e 1 2 c a r t e s i a na n d d i r e c tp r o d u c tg r a p h s c a r t e s i a np r o d u c ta n dd i r e c tp r o d u c tg r a p h sa r et w oi m p o r t a n tc l a s s e so fp r o d u c tg r a p h s ， t h er e a d e r sc a nr e f e rt o 1 4 】f o rm o r ed e t a i l s f o rc o n v e n i e n c e ，w ei n t r o d u c es o m eb a s i cp r o p - 2 五邑人学硕士学位论文 _。，-i_-_-_。_-_，_-_-_-_-_-。-_。”。_。_。_-。_。_。_。-。_。_一-， e r t i e sa n dk n o w nr e s u l t so nt h e m 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 sw i t hv e r t e x s e t sk ，v 2a n de d g e s e t se l ，e 2 r e s p e c t i v e l y d e n o t e db yi v i l = ? l ia n di e i l = e i i = 1 2 d e f i n i t i o n1 2 1t h ec a r t e s i a n p r o d u c tg 1 g 2h a sv e r t e x s e t t w ov e r t i c e s ( w 1 ，u 2 ) a n d ( v 1 ，v 2 ) o fg 1d g 2 a r ea d j a c e n to t h e ri fa n do n l yi fe i t h e ru l2i ) 1a n dm 2 v 2 e 2o ru 2 = v 2 a n du l v l e t c l e a r l y , 6 ( g 】z i g 2 ) = 5 ( ga ) + 6 ( g 2 ) a n ds ( g id g 2 ) = r i l e 2 + ，z 2 s 1 f o ra n yv e r t e xi 2 也， 1 e tg ? d e n o t et h ev e r t e x i n d u c e ds u b g r a p ho fg an g 2w i t hv e r t e x s e t _ 2 = ( i x ，i 2 ) ：i l v lj a n de d g e s e te ? = ( f l ，i 2 ) ( j l ，i 2 ) ：i l j l e 1 f o ra n yv e r t e xi i v 2 ，w ed e f i n eg ；s i m i l a r l y i t i sc l e a rt h a tg ? 兰g 1a n dg ：兰g 2 a c c o r d i n gt oa b o v es y m b o l s ，w eh a v et h a t ( i ) g ? ng j 2 = 妒f o ri 2 j z ；i 2 ，2 v j ； ( i i ) g ! nq 1 = 、f o ri l j l ；i l ，_ 1 y l ： ( i i i ) g 7ng ! = 【( i l ，i 2 ) f o ri l v 1 ，i 2 耽； ( i v ) e ! ne ；1 = 妒f o ri l j l ；i i ，1 v i ； ( v ) e ? ne j 2 = 妒f o ri 2 止；i z ，止v 2 ； ( v i ) g i g 2 = ( u i 2 v 2 0 ? ) u ( u i l e y l g ：) d e f i n i t i o n1 2 2t h ed i r e c tp r o d u c tg 1 g 2h a sv e r t e x s e tv 1 h t w ov e r t i c e s ( u l ，u 2 ) a n d ( v 1 ，v 2 ) o fg 1 g 2a r ea d j a c e n ti fa n do n l yi fu l v l e 1a n du 2 v 2 e 2 c l e a r l y , 6 ( g lxg 2 ) = 5 ( g 1 ) 占( g 2 ) a n d ( g lxg 2 ) = 2 1 s 2 f o ra n yv e r t e xi 2 圪，l e tg ? d e n o t et h ev e r t e x i n d u c e ds u b g r a p ho fg 】g 2w i t hv e r t e x - s e tw 2 = ( f 】，i 2 ) ：i l uj i nf a c t ， g ? i sa l le m p t yg r a p h f o ra n yv e r t e xi l v 1 ，g ：i sd e f i n e ds i m i l a r l y t h ec o n c e p to fc a r t e s i a np r o d u c tg r a p h sw a sf i r s t l yp r o p o s e db ys a b i d u s s ia b o u ti n19 5 7 15 ，16 i n1912 ，w h i t e h e a da n dr u s s e l lg i v et h ed e f i n i t i o no fd i r e c tp r o d u c tg r a p h s 【17 1 o t h e rn a m e sf o rt h ed i r e c tp r o d u c ta r et e n s o rp r o d u c t ，c a t e g o r i c a lp r o d u c t ，k r o n e c k e rp r o d u c t ， c a r d i n a lp r o d u c t ，r e l a t i o n a lp r o d u c ta n dw e a kd i r e c tp r o d u c t 1 4 ，p a g e1 6 2 1 m a n ya t t e n t i o na r ep a i df o rt h es t u d yo f t h ep r o p e r t i e so ft h e s et w ok i n d so fp r o d c u tg r a p h s 【14 i nt h i sp a p e r , w ec o n s i d e rt h ee d g ec o n n e c t i v i t yo f c a r t e s i a np r o d u c ta n dd i r e c tp r o d u c t g r a p h s a sar e s u l t ，s u f f i c i e n tc o n d i t i o n sf o rt h e mt ob es u p e rr e s t r i c t e de d g ec o n n e c t e d o rs u p e r 3 - r e s t r i c t e de d g ec o n n e c t e da r ep r e s e n t e d 五邑人! 学硕士学位论文 c h a p t e r2e d g ec o n n e c t i v i t yo fc a r t e s i a np r o d u c tg r a p h s f o rc o n v e n i e n c e ，i ti sa s s u m e di nt h i sc h a p t e rt h a tg ii sam a x i m a l l ye d g ec o n n e c t e dk i r e g u l a rg r a p hw i t hv e r t e x s e t = l i l i = 1 ，2 ：，f t i a n dk i 2i fn o ts p e c i f i e d 2 1r 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 a 2 1 1 2 9 i f 毛一r e g u l a rg r a p hg ih a sm a x i m u me d g ec o n n e c t i v i t y ，( i = 1 ，2 ) ，t h e n g 1 g 2a l s oh a sm a x i m u me d g ec o n n e c t i v i t yk j + k 2 l e m m a2 1 2l e tsb eam i n i m u mr e s t r i c t e de d g ec u to fg 1d g 2a n dfb eaf r a g m e n tc o r - r e s p o n d i n gt os i fg =g 1f g 2i 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 ni f i 七1 + 乜 p r o o fs i n c egi 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 ，i tf o l l o w st h a ti sl k l + k 2 一l ，a n ds ol f l k l + 也口 l e m m a 2 1 3l e tfb ear e s t r i c t e df r a g m e n to fg 1 - g 2 i fg = g i q g 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 da n dk l ，k 2 2 ，t h e nf 譬g ia n df 譬g ；，f o ra n yi a n d - 屹 p r o o fl e tsb et h em i n i m u mr e s t r i c t e de d g ec u to fgc o r r e s p o n d i n gt of s i n c egi sn o t m 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 ，i tf o l l o w sf r o ml e m m a2 1 1t h a tk l + k 2 i s f ( g ) t h i sc o n t r a d i c t i o ns h o w st h a tf 垡g i a n dt h es e c o n d f o r m u l af o l l o w ss i m i l a r l y 口 l e m m a2 1 4i fg ii sam a x i m a l l ye d g ec o n n e c t e dk i - r e g u l a rg r a p hw i t h 2 ，i = 1 ，2 ， t h e na 2 ( g 1v g 2 ) = f ( g 】v q g 2 ) 4 五邑人学硕士学位论文 p r o o fs u p p o s eb yc o n t r a d i c t i o nt h a tg = g 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 ec o n n e c t e d l e tsb eam i n i m u mr e s t r i c t e de d g ec u to fga n df ，fb et h ec o r r e s p o n d i n gr e s t r i c t e d f r a g m e n t s t h e ni sl = 1 2 ( g ji - - g 2 ) 孝( g l 口g 2 ) t h i sc o n t r a d i c t i o nc o n f i r m sc l a i m1 b yc l a i m1 ，w em a ya 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 ；1 i sc o n n e c t e d a n ds o g ：f c l a i m2 f o rs o m ev e i t e xy 亡v 2 ，g ；i sc o n n e c t e d i fc l a i m2i sn o tt r u e ，t h e n 2 ( k l + k 2 ) 一2 = ，手( g 1 口g 2 ) ya ( g j ) = k l i g 2 z 一 拒屹 2 ( k 2 1 ) 寻2 k 2 2 k l ( 1 g 2 i 一2 ) b u tt h i si n e q u a l i t yc a n n o tb et r u e ，s i n c ek l 2a n dk 2 i g 2 i 一1 a n ds o ，c l a i m2f o l l o w s i nc o n c l u s i o n ，t h e r ea r et w ov e r t i c e s 工a n dy v 2w i t ht h ep r o p e r t yt h a tg ；ug j f ，一，一 b ys y m m e t r yo ff a n df ，w ea l s oh a v et w ov e r t i c e s “v 1a n dv v 2s u c ht h a tg 2u 砭户 a n ds o g si ss t i l lc o n n e c t e d l e m m a2 1 4f 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 1 5l 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 hw i t hk 2 ( i ) i fk g i 2 ，t h e nk 2 3 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 ； ( i i ) i fk l g i 2 ，t h e n2 2 ( 膨口g ) = l g i p r o o fl e ta ，bb et h et w ov e r t e x i n d u c e ds u b g r a p h so fk 2 3 gt h a ta r ei s o m o r p h i ct og l e tfb ea na t o mo fk 2 口ga n dsb et h ec o r r e s p o n d i n gm i n i m u mr e s t r i c t e de d g ec u t s i n c ei f i i k 2 d g i 2 = m i = i b i ，i tf o l l o w st h a te i t h e rfi sap r o p e rs u b g r a p ho fao r b ，o rf=a o rb ，o rfna 0 fnba n da f 0 b f n o t i c i n gt h a t 只a f c o r r e s p o n d st oa ne d g ec u to f g w h e nf n a o a f ，w eh a v et h a tl s l 1 ( g ) + i f i ，l si = l g i o ri sl l i fr 、a ，a f 】i + i i fnb ，8 f l 2 2 ( g ) = 2 k = f ( k 2 口g ) ，r e s p e c t i v e l yi nt h ep r e v i o u s t h r e ec a s e s 5 五邑人学硕士学位论文 w h e nk i g i 2 ，w ec l a i mt h a ti s