（应用数学专业论文）关于图的边添加和边减少问题研究.pdf

摘要 我们用图g 来作为互连网络拓扑结构的模型图g 的直径是网络延迟和通 信有效性的重要度量在实时系统中，信息传输延迟被限制在某个日寸间内、超出这 个时问接收到的信息是无效的一种减小传输延迟的办法是给网络增加连线、使 得信息传输时间限制在给定范围内前人已经证明在任意一个直径为d 的图中添 加t 条边后得到的变更圈的直径不会小于一条长为d 的路添加条边后所得图的 直径 本文研究的是“加边问题”和“减边问题”确定了以下参数值的范围和某些 精确值 用p ( t ，d ) 和c ( t ，d ) 分别表示在n 阶无向路和n 阶无向圈中添加t 条边后得 到的变更图的最小可能直径 用昂( p ，d ) 和( p ，d ) 分别表示在n 阶无向路和n 阶无向圈中至少需要添加 的边数，使得变更图的可能直径不大于p 用，( t ，d ) 表示在直径为d 的连通图中去掉t 条边后得到的连通图的最大可能 直径 在第二章中，我们对某些满足与k 相关条件的t 和d 证明了p ( ，d ) 2 k 或p ( t ，d ) 茎2 k + 1 主定理证明中用到了不等式的上界 在第三章中，我们得到以下结果： 1 当t 4 ：d 3 时，有智 墨p ( ，d ) 曼i d 玎- 2 + 1 ；对4 和某些d 值 有p ( ，d ) = 胬1 + 1 2 当t23 ；d22 时有p ( f ，d ) 2f i d 万- 1 1 ，并且列某些特殊的z 和d 值不等式 i 义等号对某些t 和d 值也得到了c ( t ，d ) 的最优界 o nt h ee d g ea d d i t i o na n dd e l e t i o no fg r a p h s 3 当p24 ；r i 1 2 j 1 ：有；d 1 _ i 觜1 + 1 机4 时有等 _ 【 有d 一7s ，j ( 3 ，d ) sd 一3 t ，- ( 3 ，d ) = d s ，_ ( p ：“) 曼1 等j l 1当尸( t ，d ) = 。 t p ( p f ) 纠箸_ 1 当d 1 1 时 8 其中后者是c r i g o j c s c l 】的猜想 4 对于三3 ，d 三3 ；当p ( t ，d ) = 舞1 + 1 时有f ( t ，d ) 2 ( + 1 ) d t + 1 ；其它 情形有，( t ，d ) ( t + 1 ) d + 对某些t 和d 值证明了s c h o o y t e 等人的猜想_ 厂( ，d ) 苎 f t + 1 ) d t + l 关键词直径；加边问题；减边问题：变更图 a b s t r a c t t h eu n d e r l y i n gt o p o l o g yo fa ni n t e r c o n n e c t i o nn e t w o r ko fa s y s t e mi sm o d e l l e db yag r a p hg t h ed i a m e t e ro fg i sa ni m p o r t a n t m e a s u r ef o rc o m m u n i c a t i o ne f l i c i e n c ya n dd e l a yo ft h es y s t e m i n ar e a l t i m es y s t e m t h ed e l a ym u s tb el i m i t e dw i t h i nag i v e np e r i o d s i n c ea n ym e s s a g eo b t a i n e db e y o n dt h eb o u n dm a yb ew o r t h l e s s i f t h em e s s a g ed e l a ye x c e e d sag i v e nt i m e _ b o u n di nan e t w o r k ，o n eo f t e n a d d ss o m el i n k st ot h en e t w o r kt oe n s u r et h er e a c ho fam e s s a g ec a n b ew i t h i nar e q u i r e dt i m e i th a sb e e np r o v e dt h a tt h em i n i m u md i a m e t e ro fa na l t e r e d g r a p ho b t a i n e df r o mag r a p hw i t hd i a m e t e rdb ya d d i n gte x t r ae d g e s i se q u a lt ot h em i n i m u md i a m e t e ro fa na l t e r e dg r a p ho b t a i n e df r o m ap a t hw i t hd i a m e t e rdb ya d d i n gte x t r ae d g e s t h i st h e s i sa t t e m p t st os t u d y “t h ee d g e a d d i t i o np r o b l e m ” a n d “t h ee d g e d e l e t i o np r o b l e m ：d e t e r m i n et h em i n i m u md i a m e t e r p ( t ，d ) ( r e s p c ( t ，d ) ) o fac o n n e c t e dg r a p ho b t a i n e df r o mas i n g l e p a t h ( r e s p c y c l e ) o f 荡擞dp l u ste x t r ae d g e s ；t h em i n i m u m n u m b e r ：r e ( p ，d ) ( r e s p j 它( p ，d ) ) o fe d g e st h a th a v et ob ea d d e dt oa p a t h ( r e s p c y c l e ) o fl e n g t hdt ot r a n s f o r mi tt oag r a p ho fd i a m e t e r a tm o s tp ；：a n dt h em a x i m u md i a m e t e r ( t ，d ) o fac o n n e c t e dg r a p h e b t a i n e da f t e rd e l e t i n gte d g e sf r o mac o n n e c t e dg r a p ho fd i a m e t e r d i nc h a p t e rt w o ，w ep r o v ep ( ，d ) 2 ko r2 k + 1w h e nto rd s a t i s f i e ss o m ec o n d i t i o n so na ni n t e g e rk t h e s eu p p e rb o u n d sa r e u s e di no u rt h ep r o o f so fo u rm a i nr e s u l t s i nc h a p t e rt h r e e ，w eo b t a i nt h em a i nr e s u l t si nt h i st h e s i sa s f o l l o w s 锄 一 dd肌 一 b 以+ 咖s借删 型激 p l 一十 矧曙 ，= 以 o nt h ee d g ea d d i t i o na n dd e l e t i o no fg r a p h s 2 c ( t ，d ) 五d - 忑 f o rt 3a n dd 2 ，w h i c hi st i g h tf o is o m e a n dd t h eb e s tb o u n d sa n dt h ee x a c tv a l u e so fc ( t ，d ) a r ea l s o o b t a i n e df o rs o m eta n dd 3 ；d 一1 t p ( p ，d ) 一 l p d 一- 。7 j 一1 f o rp 4a n dd 1 2 ，a n di n p a r t i c u l f 两d2 卜1 昂( p ，d ) l 箬j 1 w h e n p ( t ，d ) = 丽d - 2 + 1 a n dt 三4 d 一7s 丁鼻( 3 ，d ) 墨d 一3f o rd21 1a n dt c ( 3 ，d ) = d 一8 ， t h el a t t e ri st h ec o n j e c t u r eo fg r i g o r e s c u 4 f o rt 3a n dd 3 ，f ( t ，d ) ( t + 1 ) d f 等 + i ，a n df ( t ，d ) 之( t + 1 ) d + to t h e r w i s e s c h o o n ee ta lf ( t ，d ) 善( t + 1 ) d t + 1i sp r o v e d t + 1i fp ( t ，d ) = t h e1 2 0 n j e c t u r eo f f o rs o m eta n dd k e y w o r d s ：d i a m e t e r ；t h ee d g e - a d d i t i o np r o b l e m ；t h ee d g e d e l e t i o n p r o b l e m ；a l t e r e dg r a p h s ；s c h o o n ee ta l se o n j e c t u r e a c k n o w l e d g e m e n t s p r a i s eb e l o n g st o g o d “a l l a h ，t h e r ei si l og o db u ti f e ，b e b o l d e r s ，e y e sf a l l s h o r to fs e e i n gh i m ! ，d e s c r i b e r s li m a g i n a t i o n sa r en o ta b l et od e p i c th i m ! ，h o w c a n i8 c h i e v et h a n k s g i v i n g ? f o rm y t h a n k i n gt h e er e q u i r e st h a n k s g i v i n g w h e n e v e ri 5 a y ，t ot h e eb e l o n g sp r a i s e17 ，i tb e c o m e st h e b yi n c u m b e n t u p o nm et os a y ，c t o t h e eb e l o n g sp r a i s e ! o ha l l a h ! m a k eu s e f u lf o rm ew h a ty o uh a v et a u 曲tm e a n dt e a c hm ek n o w l e d g et h a tw i l lb eu s e f u lt om e 1w o u l dl i k et ot h a n kp r o f e s s o rx nj u n m i n g ，m y s u p e r v i s o rw h oi n t r o d u c e d m 。t o 吼u d yt h i st o p i c ，f o rh i se x t e n s i v ec o o p e r a t i o n ，m a n ys u g g e s t i o n sa n de n c o u 卜 a g e m e n tw i t h o u th i sc o n s t a n ts u p p o r tt h i sw o r kw o u l dn o th a v eb e e nd o s s i b l e m yd e e p e s tt h a n k sg ot om yw i f ee y l a fa n dd a u g h t e rz a h r a ；w i t h o u tt h e m m yl i f ew a , sb o r i n gd u r i n gm yp h dp r o g r a m m e ic o u l d n th a y e d o n et h a tw i t h o u t t h 。1 。c o o p e r a t i o n ia mp r o f o u n d l yg r a t e f u lt om yp a r e n t s ，b r o t h e r s ( e s p e c i a i l v a s s i s r a n tp r o f e s s o rs a f a ) ) s i s t e r s ，f r i e n d s ( e s p e c i a l l ya s s i s t a n tp r o f e s r s h u s a m p a l 州a n dm yw i f e sf a m i l yf o rt h e i rc o t m t a n te n q o n r a g e m e n ta n ds u p p o r td u r i n g t h ey e a r s a l s 。it h a n k sm yc h i n e s ef r i e n d sz h a oh u i ，w a n g ，d uz h e n g z h 。n 昏h u m a o b i n ，z h um i n g f nf o rt h e mh e l pa n df r i e n d s h i p ih a dt h ep l e a s u r eo f m e e t i n gt h es t a f fo fm a t h e m a t i c sd e p a r t h l e n to fu s t c t h e ya r ew o n d e r n lp e o p l ea n dt h e i rs u p p o r tr e s e a r c hl i k et h i s p o s s i b l c t h e c h i n e s es c h o l a r s h i pc o u l l c i lw h i c hw a s a r d e dt on l ef o rt h ep e r i o d2 0 0 2 2 0 0 6 w a sc r u c i a lt ot h es n c c e s s f l l lc o m p l e t i o nt ot h i sp r o j e c t a l a aa n a j i m a p r i l2 0 0 6 c h a p t e r1 i n t r o d u c t i o n 1 1b a c k g r o u n d 1 1 1w h a ti sag r a p h h o wc a nw el a yc a b l ea tm i n i m u mc o s tt om a k ee v e r yt e l e p h o n e r e a c h a b l ef r o me v e r yo t h e r ? w h a ti st h ef a s t e s tr o u t ef r o mt h eh a - t i o n a lc a p i t a lt oe a c hs t a t ec a p i t a l ? h o wc a nnj o b sb ef i l l e db yn p e o p l ew i t hm a x i m u mt o t a lu t i l i t y ? w h a ti st h em a x i m u m f l o wp e r u n i tt i m ef r o ms o u r c et os i n ki nan e t w o r ko fp i p e s ? h o wm a n yl a y - e r ed o e sac o m p u t e rc h i pn e e ds ot h a tw i r e si nt h es a m el a y e rd o n t c r o s s ? h o wc a nt h es e a s o no fas p o r t sl e a g u eb es c h e d u l e di n t ot h e m i n i m u mn u m b e ro fw e e k s ? i nw h a to r d e rs h o u l dat r a v e l l i n gs a l e s m a nv i s i tc i t i e st om i n i m u mt r a v e lt i m e ? c a nw ec o l o rt h er e g i o n s o fe v e r ym a pu s i n gf o u rc o l o r ss ot h a tn e i g h b o r i n gr e g i o n sr e c e i v e d j f f e r e n tc o l o r s ? t h e s ea n dm a n yo t h e rp r a c t i c a lp r o b l e m si n v o l v eg r a p ht h e o r y g r a p ht h e o r yi sa f u n d a m e n t a la n dp o w e r f u lm a t h e m a t i c a lt o o l f o rd e s i g n i n ga n da n a l y z i n gi n t e r c o n n e c t i o nn e t w o r k ，s i n c et h et o p o l o g i c a ls t r u c t u r eo fi n t e r c o n n e c t i o nn e t w o r kc a nb em o d e l l e db ya g r a p hw h o s e v e r t i c e sr e p r e s e n tc o m p o n e n t so ft h en e t w o r ka n dw h o s e e d g e sr e p r e s e n tp h y s i c a lc o m m u n i c a t i o nl i n k s f o re x a m p l e , s e e b o o k sb yx u 3 0 a n dl e i g h t o n 【1 9 ，t h es p e c i a li s s u e sb yd ua n d h s umf r a n ka n df r i s c h 1 2 jh w a n ga n db r i g g s 1 7 ，b e r m o n d 【2 a n dh s u 【1 5 c o n v e r s e l y a n 3 , ag r a p hc a na l s ob ec o n s i d e r e da sat o p o l o g i c a l s t r r t u r eo fs o m ej n t e r c o n n e c t i o nn e t w o r k t h ep r o b l e mt h a to f t e ns a i dt oh a v eb e e nt h eb i r t ho fg r a p h t h e o iyw i l ls u g g e s to u rb a s i cd e f i n i t i o no fg r a p h o n2 6a u g u s t17 3 5l e o n h a r de u l e rp r e s e n t e dap a p e ro r l t h e s o l u t i o no fap r o b l e mr e l a t i n gt ot h eg e o m e t r yo fp o s i t i o n t ot h e o nt h ee d g ea d d i t i o na n dd e l e t i o no fg r a p h s ( o ) f i g u r e1 1 ：t h eb r i d g e so fk 6 n i g s b e r g 龇1 dt h e i rg r a p h a c a d e m yo fs c i e n c e so fs t p r t e r s b u r g ，r u s s i a ，p r o v i n gt h a tt h e r e i sn os u c hc o n t i n u o u sw a l ka c r o s st s e v e nb r i d g e s i n17 3 6e u l e r1 0 ls e n th i ss o l u t i o no ft h ep r o b l e mt oc o m m e n t a r i ia c a d e m i i s c i e n t i a r u mi m p e r i a l i sp e t r o d o l i t a n a eu n d e rt h et i t l e ”s o l u t i op r o b l e m a t i sa dg e o m e t r i a ma dg e o m e t r i a ms i t u sp e r t i n e n t i s ”a l t h o u g h d a t e d1 7 3 6 ，i th a sn o ta p p e a r e du n t i l1 7 4 1 a n di tw a s1 a t e rr e p u b l i s h e di nt h en e we d i t i o no ft h ec o m m e n t a r i ii n1 7 5 2 t h i sp r o b l e m d e t e r m i n e di nt h ee a r l i e s tk n o w n p a p e ro ng r a p ht h e o r yf o rp r o f e s s o r l e o n h a r de u l e r ( 1 7 0 7 1 7 8 3 ) 1 0 ，h es h o w e dt h a ti tw a si m p o s s i b l e t oc r o s se a c ho ft h a ts e v e nb r i d g e so fk s n i g s b e r ga n dt h er i v e rp r e g e l e u l e rd i dn o td r a wag r a p hi no r d e rt os o l v et h ep r o b l e m b u t h er e f o r m u l a t e dt h ep r o b l e ma so n eo ft r y i n gas e q u e n c eo fe i g h t l e t t e r sa ，b ，c ，o rd ( t h el a n da r e a ) s u c ht h a tt h ep a i r sa ba n da c a r ea d j a c e n tt w i c e ( c o r r e s p o n d i n gt ot h et w ob r i d g e sb e t w e e naa n d ba n db e t w e e naa n dc 1 ，a n dt h ep a i r sa d ，b d ，a n dc da r ea d j a c e n t j u s to n c e h es h o w e db yac o u n t i n ga r g u m e n tt h a tn os u c hs e q u e n c e e x i s t s ，t h e r e b yp r o v i n gt h a tt h ek s n i g s b e l l gb r i d g ep r o b l e mh a sn o s 0 1 u t i o n i nd i s c u s s i n gt h eg e n e r a lp r o b l e m ，e u l e ro b s e iv e dt h a tt h ei l u n b e ro fb r i d g e sw r i t t e nn e x tt ot h el e t l _ e 1 sa ，b ，c ，e t c t o g e t h e ra d d l l pt ot w i c et h en u m b e lo fb li d g e s t h i si st h ef i r s ta p p e a r a n c eo f w h a ts o m eg r a p h t h e o r i s t sn o wc a l lt h e ：h a n d s h a k i n gl e m m a ”，t h a t 3 t h es u l r lo ft h ev e r t e x d e g r e ei na g r a ，p hi se q u a lt ot w i c et h en l _ l n l b e r o fe d g e s r ，o u s ew w 【2 6 1s e e r n st oh a v eb e e nt h ef i r s tt , ou s et h eg r a p h i nf i g u r et os o l v et h ep r o b l e m d e f i n i t i o n1 1 1 a g r a p hi s a no r d e r e dt r i p l e ( v ( c ) ，e ( g ) ，妒g ) c o n s i s t i n go fa f jn o n e m p t ys e tv ( c ) o fv e r t i c e s ，as e te ( a ) o fe d 5 f e s a n dam a p p i n g 砂g ：e ( g ) 一v ( c ) v ( g ) ，c a l l e da ni n c i d e n c e f u n c t i o n ，w h i c hm a p sa ne d g ei n t oap a i r o fv e r t i c e sc a l l e de n d v e r t i c e so ft h ee d g e t h ee n d v e r t i c e so fa ne d g ea r es a i dt ob e i n c i d e n tw i t ht h ee d g e ，a n dv i c ev e r s a t w ov e r t i c e sw h i c ha r ei n c i d e n tw i t hac o m m o ne d g ea r ea d j a c e n t ，a sa r et w oe d g e sw h i c ha r e i n c i d e n tw i t hac o m m o nv e r t e x l e te ( g ) a n d ( g ) b et h en u r h b e ro ft h ee d g e sa n dv e r t i c e si n g ，r e s p e c t i v e l y i f ( g ) = 1t h e ng i sc a l l e dt r i v i a l i fe ( g ) = 0t h e n g 选c a l l e de m p t y ag r a p hgi sc a l l e df i n i t ei tb o t he ( g ) a n d ( g ) a r ef i n i t e ： d e f i n i t i o n1 1 2 t h et w oe d g e sa r ec a l l e dp a r a l l e le d g e 8i ft h e ya r e m a p p e di n t oo n ee l e m e n ti nv ( c ) v ( c ) u n d e rt h em a p p i n g 吵g i ti sa l s op o s s i b l et h a tt w oe n d v e r t i c e so fa ne d g ea r ei d e n t i c a l ，s u c h a ne d g ei sc a l l e dal o o p ag r a p hi ss a i dt ob es i m p l ei fi tc o n t a i n s n e i t h e rp a r a l l e le d g e sn o il o o p s ，a n dag r a p hi ss a i dl q q p l c s sf i l i s n o tc o n t a i nl o o p s 4o nt h ee d g ea d d i t i o na n dd e l e t i o no fg r a p h s d e f i n i t i o n1 1 3 t h ec o m p l e m e n tgo fas i m p l eg r a p hgi st h e s i m p l eg r a p hw i t hv e r t e xs e tv ( o ) d e f i n e db yu u z ( c ) i fa n do n l y i f “u e ( c 1 a ni n d e p e n d e n ts e ti nag r a p hi sa ，s e to fp a i r w i s e n o n a d j a c e n tv e r t i c e s d e f i n i t i o n1 1 4 t h ec h r o m a t i cn u m b e ro fg r a p hg ，w r i t t e nx ( g ) i st h em i n i m u mn u m b e ro fc o l o r sn e e d e dt ol a b e lt h ev e r t i c e ss ot h a t ； a d j g c e n tv e r t i c e sr e c e i v ed i f f e r e n tc o l o r s ag r a p hgi s 七一p a r t i t ei f gc a nb ee x p r e s s e da su n i o no f 忌( p o s s i b l ee m p t y ) i n d e p e n d e n ts e t d e f i n i t i o n1 。1 5 a8 z t b g r a p ho fag r a p hgi sag r a p hhs u c ht h a t v ( h ) v ( g ) a n de ( h ) e ( c ) a n dt h ea s s i g n m e n to fe n d p o i n t s t oe d g e si n 月i ss a m ea nl ng i fv ( c ) v ( c ) i sc o n s i d e r e da sas e to fu n o r d e r e d ( r e s p o r d e r e d ) p a i r s ，t h e nt h eg r a p hg i sc a l l e da nu n d i r e c t e d ( r e s p ad i r e c t e d ) g r a p h n o ww ei n t r o d u c es o m es p e c i a lc l a s s e so fg r a p h s t h eg r a p hs h o w ni nf i g u r e12i sc a l l e dp e t e r s e ng r a p h ab i p a r t i t eg r a p h1 so n ew h o s ev e r t e x - s e tc a nb ep a r t i t i o ni n t o t w os u b s e t sxa n dy s oe a c he d g eh a so n ee n d v e r t e xi nxa n d a n o t h e ri ny ，s u c ht h a tap a r t i t i o n x ，y i sc a l l e dab i p a r t i t i o no f t h eg r a p h t h eb i p a r t i t eg r a p hd e n o t e db yc ( xuy 1e ) ac o m p l e t eg r a p hi sag r a p hi nw h i c he a c ho r d e r e dp a i ro fd i s t i n c tv e r t i c e si sl i n k e db ye x a c t l yo n ee d g e s o ，t h e r ei sj u s to n e c o m p l e t eg r a p ho i luv e r t i c e s ，d e n o t e db yk w 1 1 b a c k g r o u n d 。 f i g u r e12 ：p e t e r s e ng r a p h l e m m a1 1 1 ( 删) 蚓= 慨l ：，篡篡甜 ac o m p l e t eb i p a r t i t e9 r a p hi sab i p a r t i t eg r a p hg ( xuy ) e ) i nw h i c he a c hv e r t e xo fxi sj o i n t e db ya ne d g et ov e r t e xo fy i f i x e | = ma n dl y2 = 咒t h e nt h ec o m p l e t eb i p a r t i t eu n d i r e c t e dg r a p h d e n o t e db yk m 。 1 1 2a d j a c e n c ya n di n c i d e n c em a t r i c e s d e f i n i t i o n1 1 6 l e tgb eal o o p l e s sg r a p hw i t hv e r t i c e ss e tv ( g 1 ) a n de d g es e tz ( g ) = e l ，e 2 ，e n t h ea d j a c e n c y m a t r i zo fg ，w r i t t e na ( g ) ，i st h en b y nm a t r i xe n t e r yn i ：，i st h e n u m b e ro fe d g e si ngw i t he n d p o i n t s ( v j ) t h ei n c i d e n c e ? t z a 6o nt h ee d g ea d d i t i o na n dd e l e t i o no t g r a p h s t r i xm ( c ) i st h e7 1 - b y 埘lm a t r i xi nw h i c he n t e r y 7 ) 3 , i j i s1 i f 忱i sa n e n d p o i n to fe ja n do t h e r w i s ei s0 e x a m p l e1 1 1 f r o mt h eg r a p hi nf i 9 1 【i r e11 bw eh a v e o111 l010 11o1 10l0 m ( g ) 111110 o l1oo o1o 0 o oo111 00110 01 i fv e r t e x i sa ne n d p o i n to fe d g ee t h e n a n dea r ei n c i d e n t t h ed e g r e eo fv e r t e x 口( i na l o o p l e s sg r a p h ) ，d e n o t e db yd g ( z ) ，i st h e n u n b e ro fe d g e si n c i d e n tw i t hz ，e a c hl o o pc o u n t i n ga st w oe d g e s av e r t e xo fd e g r e edi sc a l l e dad - d e g r e ev e r t e xao - d e g r e ev e r t e x i sc a l l e da ni s o l a t e dv e r t e x av e r t e xi sc a l l e dt ob eo d do re v e ni f i t s 、d e g r e ei so d do re v e n ，r e s p e c t i v e l y ag r a p hg i s k - r e g u l a ri f d d z ) = 后f o re a c hz y ( g ) ，a n dgi sr e g u l a ri fi t i sk - r e g u l a r f o rs o m ek ，a n dki sc a l l e dt h er e g u l a r i t yo fg f o ri n s t a n c e ，t h e c o m p l e t eg r a p hk si s ( n 一1 ) 一r e g u l a r ，t h ec o m p l e t eb i p a r t i t eg r a p h ni sn r e g u l a ra n dp e t e r s e ng r a p hi s3 - r e g u l a r t h ep a r a m e t e r s a ( c ) = m a x d a ( x ) d ( g ) 一m i n d g ( x ) z v ( c ) ) ，a n d z v ( g ) ) a r et h em a x i m u ma n dm i n i m u md e g r e eo fg ，r e s p e c t i v e i yf o rz y e ( g ) ：t h ep a r a m e t e r g ( x y ) = d e ( x ) + d a ( y ) 一2 i st h ed e g r e eo ft h e e d g ex y ，a n dt h ep a r a m e t e r ( g ) = m i n c ( x y ) ；x y z ( c ) ) i st h em i n i m u me d g e d e g r e eo fgi ti sc l e a rt h a t ( g ) ( g ) + 6 ( g ) 一2 a nu n d i r e c t e dg r a p hgi sc a l l e dt ob ee d g e r e g u l a ri f ( e ) = ( g ) f o ra n ye d g eeo fgt h eo u t d e