圖的加邊問題.pdf

1、中國科學技術大學碩士學位論文圖的加邊問題姓名：胡青申請學位級別：碩士專業(yè)：應用數(shù)學指導教師：徐俊明20080501A b s t r a c tG i v e n p o s i t i V ei n t e g e r s ￡a n dd ( ≥2 ) ，1 e tJ p ( ￡，d ) d e n o t et h e m i n i m u m d i a m e t e ro fa p a t h o b t a i n e d

2、b ya d d i n g ￡e x t r a e d g e s t o ap a t hw i t hd i a m e t e rd ．I nt h i sp a p e r ，w ep r o V et h a tf o rd ( ≥8 ) ，d = 7 ( 2 后一1 ) + ^ ：w h e n 七芝1a n d1 ≤^ ≤1 4 ，f ．號] ≤尸。6 ，回sf } 季{ + 2 ；；：三；【吲+ 1 o t l l

3、e r w i s ef 鼉1 冬尸c 7 ，d ，s {i fh = 1+ 2 i fh = 7 ．8+ 1 o t h e r w i s e『名1 ≤。。8 ，d ，≤{ } 耄{ + 2 { ；：三；，8 ，9 【吲+ 1 o t h e r w i s eG e n e r a l l y ’w h e nd = 1 ，2 ，3 ，?，幾+ 1 ， 1 冬尸( 幾，d ) ≤3 ； d ( ≥n + 2 ) ，d =( n +

4、 1 ) ( 2 七一1 ) + ^ ，w h e n 后≥1a n d1 ≤^ S ( 2 竹+ 2 ) ，∞㈤啦㈣i f h = 1+ 2 i f h = 7 ，8 ，．．．，n + 1+ l o t h e r w i s eT h i st h e s i s c o n s i s t so ff o u rc h a p t e r s ．I nt h ef i r s t 曲a p t e r ，w ei n t r o

5、d u c es o m ef 6 u n d a t i o n a l p r o p e r t i e so fg r a p h su s e di no u rd i s c u s s i o na n dw e l l —k n ( ) 、v r e s u l t so ft h ep r o b l e m s ． I n t h es e c o n d c h a p t e r ，w er e s e a r

6、c h 尸( ￡，d ) w h e n z = 6 ，7 ，8 ． I nt h et h i r de h a p t e r ，w e r e s e a r e h P ( ≠，d ) f o ra n yp o s i t ，i 、，e i n t e g 既 ≠．s o m ep r o b l e m st ob es t u d i e df U r t h e ra n dt h ei n n o V a t i o