圖論在算法設(shè)計中的應用.pdf

1、西安電子科技大學碩士學位論文圖論在算法設(shè)計中的應用姓名：王麗申請學位級別：碩士專業(yè)：應用數(shù)學指導教師：劉紅衛(wèi)20100410A b s t r a c tG r a p h t h e o r y i sa r l a n c i e n td i s c i p l i n e ，a n di t s b i r t hC a nb et r a c e db a c kt o 17 3 6 ．I nt h ef i e l do f

2、d i s c r e t em a t h e m a t i c s ，g r a p ht h e o r yh a s a d o m i n a n tp o s i t i o n ．G r a p ht h e o r yh a si n t u i t i v e ，c l e a r , p r o b l e m - s o l v i n gc h a r a c t e r i s t i c sa n d m

3、o r ei m p o r t a n t l y ' t h ep r ￡l C t i c eo Im a n y p r a c t i c a lp r o b l e m sC a l l b ec l a s s i f i e di n t oe q u i v a l e n t g r a p h t h e o r yp r o b l e m s ．S oG r a p ht h e o r y h a

4、s aw i d er a n g eo fa p p l i c a t i o n s ，i t C a l l b e a v a r i e t yo fc o m p l e xe n g i n e e r i n gs y s t e m sa n d m a n a g e m e n tp r o b l e m sw i t ht h e ”m a p ”t od e s c r i b e ，a n dt h e

5、nm a t h e m a t i c a l l y o b t a i no p t i m a lr e s u l t s ．S t u d i e di ng r a p h t h e o r y , ·' m a p ”i sd e t e r m i n e db va n u m b e r o f p o i n t s ( c a l l e dv e r t i c e s ，V e r t

6、e x ) a n da n u m b e r o f l i n es e g m e n t sl i n k i n gt h et w o v e r t i c e s ( c a l l e de d g e s ，E d g e ) f o r m ．V e r t i c e sa r e u s u a l l yu s e dt oe x p r e s st h i n g sa 1 1 de d g e s u

7、 s e d t o i n d i c a t e t h er e l a t i o n s h i p b e t w e e nt h e s e t h i n g s ．V e r t e x p o s i t i o n ，e d g el e n g t hi si r r e l e v a n t , w h e n t h ee d g e s C a n b es e td i f f e r e n tw

8、e i g h t st oi n d i c a t et h es t r e n g t ho f t h er e l a t i o n s h i pb e t w e e nv e r t i c e s ．G r a p ht h e o r yt os o l v em a n y e n g i n e e r i n gp r o b l e m si n a l g o r i t h m d e s i g n

9、 a n e f f e c t i v e m a t h e m a t i c a l m o d e l t o f a c i l i t a t e c a l c u l a t i o n a n da n a l y s i s ，a n d c o m p u t e rs t o r a g e ．A l g o r i t h mi s as e r i e so fs t e p sp r o b l e m

10、- s o l v i n gc o l l e c t i o n s ．T h e r e f o r e ．a(chǎn) l g o r i t h md e s i g n a n da n a l y s i s f o rp r o b l e ms o l v i n gi s c r u c i a l ．A st h e D i s c r e t e M a t h e m a t i c s ’si m p o r t a

11、n t c o m p o n e n t s ，g r a p h t h e o r y h a s b e c o m e a n i m p o r t a n t c o n t e n t o fa l g o r i t h m - d e s i g n e d ．B e c a u s eG r a p hT h e o r ya n da l g o r i t h mi s s u eh a sc l o s er

12、 e l a t i o n s h i p '”m a p ”f o rs o m ea l g o r i t h m sp r o v i d e da l li n t u i t i v em a t h e m a t i c a lp l a t f o r m ，g r a p ht h e o r ya l s op r o v i d ea t h e o r e t i c a lb a s i sf o

13、rt h e s e A l g o r i t h m ．I nf a c t ，m a n ya l g o r i t h m sp r o b l e m sd i r e c t l y o r i n d i r e c t l y h a v e s o m e t h i n g t o d o w i t h f i g u r er e l a t e d ．F o r e x a m p l e ．N Pc o m

14、 p l e t ep r o b l e mh a v ea c o n s i d e r a b l eg r a p h t h e o r yi s s u e so rw i t h ”f i g u r e ”r e l e v a n ti np a r t ．B a s e do n t h ea b o v e - m e n t i o n e d a d v a n t a g e s o f g r a p h

15、 t h e o r y , t h u st h er e l a t e dt h e o r i e so f g r a p h t h e o r yC a n b ea r e f e r e n c et ot h ea l g o r i t h m —d e s i g n e d ．A tt h ef i r s t ，w ei n 昀d u c es o m e g r a p h t h e o r y , t

16、h e t h e o r y a n dt h e i r a p p l i c a t i o n s a s w e l l ，t h e n a n a l y z e d a n ds u m m a r i z e d t h e i rs t r e n g t h sa n d w e a k n e s s e s ，t ou s e i nc l u s t e r ．a(chǎn) n d p r o p o s e s o

17、 m e w a y s t oi m p r o v ef i n a l l yK e y w o r d ：g r a p h t h e o r y a l g o r i t h m d e s i g nm i n i m u m s p a n n i n g t r e em o d i f i e dc l u s t e r i n g m i n i m u m s p a n n i n g t r e ea l