完全3分圖和完全5分圖中的幾類一致最優(yōu)圖.pdf

1、學(xué)位 論 文完全3 分圖和完全5 分圖中的幾類一致最優(yōu)圖( 題 目)孫華娟( 作者姓名)指導(dǎo)教師 邵方明 教授申請學(xué)位級別 理學(xué)碩士專業(yè)名稱 應(yīng)用數(shù)學(xué)學(xué)位授予單位 大連海事大學(xué)2 0 0 5 年3 月A b s t r a c tT h i s t h e s i s i n v e s t i g a t e s t h e s y n t h e s i sp r o b l e mo fu n i f o r m l yo p t

2、 i m a l l y r e l i a b l en e t w o r kw h o s ee d g e sn e v e r f a i lb u tw h o s e v e r t i c e s b r e a k d o w ni n d e p e n d e n t l y o f e a c ho t h e r ( U O R ：U n i f o r m l y O p t i m a l l yR e l

3、 i a b l e ) ．N a m e l y , l e t f 2 ( n ，m ) b e t h ec l a s s o fa l lg r a p h sw i t h nn o d e sa n d 州e d g e s ，w ea R e m p tt of i n dt h em o s t r e l i a b l eg r a p h sG ( n ，m ) ，i nt h ec l a s so f t h

4、 eg r a p h st 2 ( n ，肼) ，f o ra l lc h o i c e so f p ．T h el a t e s tr e s e a r c hs h o w s t h a ts o m e c o m p l e t e t r i p a r t i t e g r a p h s a l eu n i f o r m l y o p t i m a l l y r e l i a b l ei ni

5、 t sc l a s s ，T h i s t h e s i sp r o v e st h a tan e w c o m p l e t et r i p a r t i t eg r a p hi s u n i f o r m l yb e s ti ni t sc l a s s ．F u r t h e r m o r e ，t h e r e 盯et w ok i n d so fu n i f o r m l yo

6、p t i m a l l yr e l i a b l e n e t w o r k s i n c o m p l e t e5 - p a r t i t eg r a p h s ．T h e c o n c l u s i o n s a r e a sf o l l o w s ：( 1 ) T h et h e s i sp r o v e st h e r ea l s oe x i s t san e w c l a

7、 s so f u n i f o r m l y o p t i m a l l y r e l i a b l en e t w o r k ．M o r e p r e c i s e l y ，i tp r o v e st h a tf o ra n yp o s i t i v ei n t e g e r b ( b ≥2 ) ，t h ec o m p l e t et r i p a r t i t e g r a p

8、 h K 6 ．6 + 2 D + 2 i s u n i f o r m l y o p t i m a l l y i n i t s c l a s sn ( 3 b + 4 , 3 b 2 + 8 b + 4 ) ，w h i l e t h e c o m p l e t et r i p a r t i t eg r a p h s K 6 ，m 肝J ( 』> 3 ) a r e n o tt h e u n i f

9、 o r m l y o p t i m a l l y i nt h e r e C l a s sQ ( 3 6 + 2 + J ，3 b 2 + 2 ( 2 + - ，) 6 + 2 j ) ．( 2 ) T h et h e s i s p r o v e s t h e r ea l s o e x i s tt w o n e wc l a s s e so fu n i f o r m l yo p t i m a l l

10、 yr e l i a b l e n e t w o r k s ．P r e c i s e l y , i t p r o v e s t h a t f o ra n yp o s i t i v e i n t e g e r b ( b ≥2 ) ' t h ec o m p l e t e 5 - p a r t i t e g r a p h 晚M ¨．¨舢2 i s u n i f o n

11、r d y o p t i m a l l y i n i t s c l a s sf ) ( 5 b + 5 ，1 0 b 2 + 2 0 b + 9 ) ，t h e c o m p l e t e 5 - p a l t i t e g r a p h K 6 ．6 + 1 ，矗+ l ，6 + 2 ，^ + 2i s u n i f o r m l yo p t i m a l l yi ni t s c l a s s Q

12、( 5 6 + 6 ，1 0 6 2 + 2 4 b + 1 3 ) ，w h i l et h ec o m p l e t e5 - p a r t i t e g r a p h sK 6 ．6 + 1 ，6 + 1 ．6 + 1 ．6 + ，( J > 2 ) a x e n o t t h e u n i f o r m l y o p t i m a l l y i n t h e r e c l a s sf 2 (