完全多部圖的DRC圈覆蓋.pdf

1、河北師范大學(xué)碩士學(xué)位論文完全多部圖的DRC圈覆蓋姓名：謝春麗申請(qǐng)學(xué)位級(jí)別：碩士專業(yè)：基礎(chǔ)數(shù)學(xué)指導(dǎo)教師：梁志和20090407A b s t r a c tT h i sp a p e r c o n s i d e r st h ec y c l ec o v e r i n go f c o m p l e t eg r a p h sm o t i v a t e d b y t h ed e s i g no fs u r v i

2、 v a b l e w D M n e t w o r k s 。w h e r e t h e r e q u e s t sa r e r o u t e do n s u b —n e t w o r k s w h i c h a r e p r o t e c t e di n d e p e n d e n t l yf r o m e a c h o t h e r ．T h ep r o b l e m C a l l

3、b e s t a t e da sf o l l o w s ：f o r ag i v e n g r a p h G ，f i n da c y c l ec o v e t i n go f t h e e d g es e t o f A 甄( n ) ，w h e r e y ( A K ( n ) ) = V ( G ) ，s u c h t h a t e a c hc y c l ei n t h ec o v e r

4、 i n gs a t i s f i e st h ed i s j o i n tr o u t i n gc o n s t r a i n t ( D R C ) ，r e l a t i v e l y t oG ．I no t h e rw o r d s ：t oe a c h e d g eo f 入致( 托) w ea s s o c i a t ei n G ap a t ha n d a l lt h e p a

5、t h sa s s o c i a t e dt ot h ee d g e so f ac y c l eo f t h ec o v e r i n gm u s t b e v e r t e xd i s j o i n t ．W e w a n t t o m i n i m i z e t h en u m b e r o f c y c l e si nt h ec o v e r i n g ．I n [ 1 6 ]

6、，B e r m o n dr i s e dt w o p r o b l e m s ：w h e n w ec o n s i d e rt h ec a s ew h e r eG = G ，ar i n go f s i z en a n d l o g i c a lg r a p h i sA ‰0 r 入‰㈨h o w m a n y c y c l e s a l en e e d e d a tl e a s t ?

7、 F o r t h et w o p r o b l e m s ，L i a n g Z h i h e a n dH a n N a 【1 8 ] g a v eo p t i m a l s o l u t i o n sa sw e l la sf o rv a r i a t i o n so ft h ep r o b l e m ，n a m e l y , i t sd i r e c t e dv e r s i o

8、 n ．I nt h i sp a p e rw eg i v eo p t i m a ls o l u t i o n so n t h ec y c l ec o v e r i n go f A ％( 禮) m 蘭l ( m o d 2 ) ，m 1 ( m o d 2 ) ，A e z ) ，t h a te a c hc y c l ei nt h ec o v e r i n gs a t i s f i e st h e