歐幾里德距離下的最短2-連通Steiner網(wǎng)絡(luò).pdf

1、西北工業(yè)大學(xué)碩士學(xué)位論文歐幾里德距離下的最短2-連通Steiner網(wǎng)絡(luò)姓名：彭書英申請(qǐng)學(xué)位級(jí)別：碩士專業(yè)：應(yīng)用數(shù)學(xué)指導(dǎo)教師：張勝貴20050301Ab s t r a c tAbs t r a c tL e t P b e a f i n i t e s e t o f p o i n t s . A n e t w o r k N=( 認(rèn)E ) i s c a l l e d a S t e i n e r

2、n e t w o r k o n P i f P C V , a n d p a r t i c u l a r l y a s p a n n i n g n e t w o r k o n P i f P=V .F o r a S t e i n e r n e t w o r k N o n P , p o i n t s i n P a r e c a l l e d r

3、e g u l a r p o i n t s , w h i l e p o i n t si n V\ P a r e c a l l e d S t e i n e r p o i n t s . T h e l e n g t h o f a n e t w o r k i s d e f i n e d t o b et h e t o t a l l e n g t h o f a l

4、 l i t s e d g e s . G i v e n a f i n i t e s e t P o f p o i n t s i n t h e E u c l i d e a np l a n e , t h e E u c l i d e a n 2 - c o n n e c t e d S t e i n e r n e t w o r k p r o b l e m i s

5、t o f i n d t h e s h o r t e s t2 - c o n n e c t e d S t e i n e r n e t w o r k o n P , w h e r e t h e l e n g t h o f a n e d g e p q i s d e f i n i e da s t h e E u c l i d e a n d i s t a n c e

6、 b e t w e e n t h e p o i n t s p a n d q , a n d s o m e e x t r a p o i n t sn o t i n P m a y n e e d . T h i s p r o b l e m h a s i m p o r t a n t a p p l i c a t i o n s i n t h e d e s i g

7、n o fe c o n o mi c a l a n d r e l i a b l e c o mmu n i c a t i o n n e t w o r k s .L u e b k e a n d P r o v a n p r o v e d t h a t t h e E u c l i d e a n 2 - c o n n e c t e d S t e i n e r n e t w o

8、 r kp r o b l e m i s N P - h a r d , w h i c h m e a n s t h a t t h e r e a r e f e w p o s s i b i l i t i e s o f e x i s t i n g ap o l y n o m i a l t i m e a l g o r i t h m f o r a g e n e r a l

9、 f i n i t e s e t P o f p o i n t s i n t h e E u c l i d e a np l a n e . I n 1 9 9 8 , H s u a n d H u i n t r o d u c e d t h e c o n c e p t o f b a s i c 2 - c o n n e c t e d S t e i n e rn e t

10、w o r k s , a n d g a v e s o m e s t r u c t u r a l p r o p e r t i e s o f ( b a s i c ) s h o r t e s t 2 - c o n n e c t e dS t e i n e r n e t w o r k s a n d t w o p o l y n o m i a l l y - s o l v a

11、b l e c a s e s . L i M e i l i , i n h e r t h e s i ss h o w e d s e v e r a l s t r u c t u r a l p r o p e r t i e s o f ( b a s i c ) s h o r t e s t 2 - c o n n e c t e d S t e i n e r n e t -w o r k

12、s b y u s i n g b l o c k g r a p h s a s t o o l s a n d g a v e a c l e a r p r o o f o f a r e s u l t o f H s ua n d H u . I n t h i s t h e s i s , w e g i v e a f u r t h e r r e s e a r c

13、h o n t h e E u c l i d e a n 2 - c o n n e c t e dS t e i n e r n e t w o r k p r o b l e mI n C h a p t e r 1 , a f t e r a n i n t r o d u c t i o n o n t e r m i n o l o g y a n d n o t a t i o n s ,

14、w e g i v ea s u r v e y o n t h e E u c l i d e a n 2 - c o n n e c t e d S t e i n e r n e t w o r k p r o b l e m a n d a g e n e r a li n t r o d u c t i o n o f t h e ma i n r e s u l t s o f t h e

15、 t h e s i s .I n C h a p t e r 2 , w i t h a p r o p e r t y o f 2 - c o n n e c t e d n e t w o r k s g i v e n 飾 M o n m a e t a l . ,w e g i v e s e v e r a l n e w s t r u c t u r a l p r o p e r t

16、i e s o f ( b a s i c ) s h o r t e s t 2 - c o n n e c t e d s t e i n e r( o r s p a n n i n g ) n e t w o r k s , a n d m o r e s i m p l e a n d c l e a r p r o o f s o f t h r e e p r o p e r t i e s

17、 o f( b a s i c ) s h o r t e s t 2 - c o n n e c t e d S t e i n e r n e t w o r k s p r e s e n t e d b y L i M e i l iI n C h a p t e r 3 , w e m a i n l y d i s c u s s t h e r e l a t i o n s h i p

18、a m o n g t h e s h o r t e s t 2 -c o n n e c t e d S t e i n e r n e t w o r k o n P , t h e s h o r t e s t 2 - c o n n e c t e d s p a n n i n g n e t w o r k o nP a n d i t s s h o r t e s t H a m i