網(wǎng)格圖的多重L(2，1)-標號.pdf

1、東南大學碩士學位論文網(wǎng)格圖的多重L（2，1）-標號姓名：張璞申請學位級別：碩士專業(yè)：運籌學與控制論指導教師：林文松20081220A b s t r a c tT h e L ( 2 ，1 ) 一l a b e l i n go f ag r a p h w a s m o t i v a t e db y a s p c c i a lk i n d o fc h a n n e l a s s i g n m e n tp r o

2、b l e m ．T h e r eh a v eb c c nm a n y r e s e a r c hr e s u l t so nL ( 2 ，1 ) 一l a b e l i n go f g r a p h si nr e c e n t l yy e a r s ，a n d t h ec o n c e p to fL ( 2 ，1 ) 一l a b e l i n gh a sb e e n g r e a t l

3、 ye x t e n d e d ．W cc o n s i d e rt h ec h a n n e la s s i g n m e n tm o d e l a sf o l l o w s w h i c hl e a d st oo u rq u e s t i o n s ．S u p p o s en a n dda r ep o s i t i v e i n t e g e r s ，i f t h e r ea

4、r cm a n yb r o a d c a s t i n gs t a t i o n si n a na r e a ，e a c hs t a t i o n n c e dt ou s en d i f f e r e n t c h a n n e l s ．T oa v o i di n t e r f e r e ，t w oc h a n n e l so ft w op r e t t yc l o s e s t

5、 a t i o n sn e e dt ob ea tl e a s td a p a r t ，a n dt w oc h a n n e l so ft w oc l o s es t a t i o n ss h o u l db ed i f f e r e n t ．T h i sp r o b l e m c a nb cf o r m u l a t e dg u sn —f o l dL ( d ，1 ) 一l a b

6、 e l i n go f ag r a p h ．D e f i n et h ed i s t a n c eb e t w e e nt w oa r b i t r a r yi n t e g e rs e t s I a n dJa s ：d ( I ，J ) = m i n { [ i —J I ：i ∈I ，J ∈J 】．．T h en - f o l dL ( d ，1 ) 一l a b e l i n go f ag

7、 r a p hG i s af u n c t i o nf f r o mv ( a ) t o t h es e tc o n s i s t i n go f a l ln —s u b s e t so ft h es e to fn o n n e g a t i v e i n t e g e r ss a t i s f y i n gt h ef o l l o w i n gt w o c o n d i t i o

8、 n s ：( 1 ) d ( ，( u ) ，，( 口) ) ≥d ，i fU V ∈E ( G ) ；( 2 ) d ( ，( 釷) ，．廠( u ) ) ≥1 ，i ft h ed i s t a n c eb e t w e e nua n d Vi s 2 ．T h e n —f o l dL ( d ，1 ) 一l a b e l i n gn u m b e r o f g r a p h G i sd e f i n e

9、 da s 入Z 1 ( G ) = m i n I m a x f ( V 1 ) Uf ( v 2 ) U ?U f ( v 。) ，w h e r ef i st a k e n o v e ra l l n —f o l dL ( d ，1 ) 一l a b e l i n g so f G ．I f w e w a n t t o c o v e rt h ep l a n ew i t hr e g u l a r p o

10、l y g o n s ，o n l yr e g u l a rt r i a n g l e ，r e g u l a rh e x a g o n ，a n dm u l t i d i m e n —s i o n a ls q u a r e l a t t i c ea r cp o s s i b l e ．I nc h a p t e rt w o ，w ei n v e s t i g a t e t h en —f

11、o l dL ( d ，1 ) 一l a b e l i n ga n d n —f o l dL ( d ，1 ) 一c i r c u l a rl a b e l i n go ft h et h r e el a t t i c c 溜．W eo b t a i nt h eu p p e ra n dl o w e rb o u n d s f o rt h en —f o l dL ( d ，1 ) 一l a b e l i

12、 n gn u m b e ra n d n —f o l dL ( d ，1 ) 一c i r c u l a rl a b e l i n gn u m b e rb yc i r c u l a r l ya s s i g n i n gl a b e ls e t s t ov e r t i c e s ．W h e nd = 2 ，w e c o m p l e t e l yd e t e r m i n et h e扎

13、一f o l dL ( d ，1 ) 一l a b e l i n gn u m b e r s a n d n —f o l dL ( d ，1 ) 一c i r c u l a rl a b e l i n gn u m b c r so ft h et h r e el a t t i c e s ．I nc h a p t e rt h r e e ，w eg of u r t h e rt oi n v e s t i g a

14、 t et h e7 “ ／一f o l d d - s e p a r a t e dL ( d ，1 1 一l a b e l i n go f ag r a p h ．D e n o t et h ec o m p l e t eg r a p ho nn v e r t i c e s b y ％．A nn —f o l d d - s e p a r a t e dL ( d ，1 ) ·l a b e l i n

15、go f G i s i n d e e da nL ( d ，1 ) 一l a b e l i n go f t h ec o m p o s i t i o ng r a p h G 【％】，a n da n幾一f o l dL ( d ，1 ) 一l a b e l i n go fG i se q u i v a l e n tt oa nL ( d ，1 ) ·l a b e l i n go ft h ec o m

16、 p o s i t i o n g r a p hG [ K I ] ．W h e nd = 2 ，w e o b t a i nt h er a n g eo fn —f o l d2 - s e p a r a t e dL ( 2 ，1 ) 一l a b e l i n gn u m b e ro fr e g u l a rt r i a n g l e ，a n dw ec o m p l e t e l yd e t e

17、r m i n et h en - f o l d 2 一s e p a r a t e dL ( 2 ，1 ) 一l a b e l i n gn u m b e r so fr e g u l a rh e x a g o n a n dm u l t i d i m e n s i o n a ls q u a r el a t t i c e ．K e y w o r d ：c h a n n e l a s s i g n m