《两类图的最小直径定向》由会员分享，可在线阅读，更多相关《两类图的最小直径定向（27页珍藏版）》请在金锄头文库上搜索。
1、山西大学硕士学位论文两类图的最小直径定向姓名：李艳军申请学位级别：硕士专业：应用数学指导教师：杨爱民20070601两类图的最小直径定向A B S T R A C TT h ea r t i c l ei sd i v i d e di n t ot w oc h a p t e r s W e 出i e 毋s t u d yt h ep r o b l e mo ni n i l l i i n u n ld i a m e t e ro r i e n t a t i o n so fag r a p h I ti st h eo n e - w a ya n dg o s s i pp
2、r o b l e m sw h i c hl e a dt oi n t r o d u c el l l i n l m l E md i a m e t e ro r i e n t a t i o n so fag r a p h ，n a m e l yh o wt oc h a n g eo n e - w a ys t r e e tf o re v e r ys t r e e to fat r a 伍cs y s t e m ，w h i c he v e r yt w ov e r t i c e sa r em u t u a l l yr e a c h a b l e
3、a n dt h eq u a n t i t yo ft h el o n g e s tr o u t e si sm i n i n l u l n B e c a u s eo ft h ew i d ea p p l i c a t i o nb a c k g r o u n d b o t hp r o b l e m sa r ec o n c e r n e da n da l s op o p u l a rt o d a y A no r i e n t a t i o no fag r a p hGi sad i g r a p ho b t a i n e df r
4、o mGb ya s s i g n i n gt oe a c he d g ei nGad i r e c t i o n A no r i e n t a t i o nDo fGi ss t r o n gi fe v e r yt w ov e r t i c e si nDa r em u t u a l l yr e a c h a b l ei nD A ne d g eei nac o n n e c t e dg r a p hGi sab r i d g ef fG ei sd i s c o n n e c t e d R o b b i n s c e l e b r
5、 a t e do n e - w a ys t r e e tt h e o r e ms t a t e st h a tac o n n e c t e dg r a p hGh a sas t r o n go r i e n t a t i o ni fa n do n l yi fn oe d g eo fGi sab r i d g e 1 T h ed i a m e t e ro fag r a p hGi sf i n i t ew h e ni th a sas t r o n go r i e n t a t i o n H o wt oo r i e n tGs u
6、c ht h a tt h ed i a m e t e rr e a c h e sm i n i m u mi sm i n i m u md i a m e t e ro r i e n t a t i o n sp r o b l e m F o rab r i d g e l e s sc o n n e c t e dg r a p hG ，l e tv ( G ) b et h ef a m i l yo fs t r o n go r i e n t a -t i o n so fG ，a n df o ra n yD D ( G ) ，w ed e n o t eb yd (
7、 D ) ( r e s p ，d ( G ) ) t h ed i a m e t e ro fD ( r e s p ，G ) D e f i n ed ( G ) = m i n d ( D ) fD D ( G ) ) a ( s 1 ，s 2 ，一，8 n ) ( t h i sn o t a t i o nc o m e sf r o m 2 】) i saGv e r t e x - m u l t i p l i c a t i o nf o ra n yc o n n e c t e dg r a p hGo fo r d e r 几3a n df o ra n ys e q
8、 u e n c es iw i t h8 i 2 ，l = 1 ，2 ，- 一，住K o ha n dT a yi nt h e i rp a p e l 2 】g i v eai n e q u M i t ya sf o l l o w s ：d ( C ) Sd ( G ( s l ，8 2 ，s 。) ) d ( a ) + 2A l lg r a p h so ft h ef o r mG ( s l ，8 2 ，8 n ) a r et h u sd i v i d e di n t ot h ef o l i o w i n gt h r e ec l a s s e s ：也
9、= G ( s l ，8 2 ，s , t ) I d ( G ( s l ，8 2 ，) ) = d ( a ) + 日，i = 0 ，1 ，2A tt h es a m et i m eK o ha n dT a ya l s og i v es u c hac o n j e c t u r e 2 ：i fGi sag r a p hs u c ht h a td ( a ) 23 ，t h e nG ( s l ，8 2 ，) 也，( 8 1 2 ，i = 1 ，2 ，一，竹) I ti sv e r yd i f f i c u l tt og i v eac o u n t e
10、r e x a m p l eo rap r o o f I nt h ef i r s tc h a p t e rw eg e tt w op r o p e r t i e so ft h eo p t i m a lo r i e n t a t i o n sd i g r a p hf o rt r e e2 - v e r t e xm u l t i p l i c a t i o n s ，a n dam e t h o dc o m p u t i n gt h ed i a m e t e ro f1 - c y c l eg r a p h A tl a s tw e
11、1 1v e r i f yt h a tt h i sc o n j e c t u r ei st r u ef o r1 - c y c l ev e r t e xm u l t i p h c a t i o n s ，n a m e l yi ti st r u ew h e nGi sa1 - c y c l eg r a p h I nc h a p t e r2 ，w ed e a lw i t hm i n i l n u i nd i a m e t e ro r i e n t a t i o n so fs t r o n gp r o d u c t so ft w
12、 op a t h s K o ha n d r a yh a ss t u d i e dm i n i m u md i a m e t e ro r i e n t a t i o n so fp r o d u c t so fp a t h ，c y c l e ，c o m p l e t eg r a p ha n ds oo n T h i sc h a p t e rg i v e 8i n i m l n u md i a m e t e ro r i e n t a -t i o n so fs t r o n gp r o d u c t so ft w op a t
13、h s K e yw o r d s ：1 - c y c l eg r a p h ；M i n i m u md i a m e t e ro r i e n t a t i o n s ；V e r t e xm u l t i -p l i c a t i o n s ；P a t h ；S t r o n gp r o d u c tC L C ：0 1 5 7 5承诺书本人郑重声明：所呈交的学位论文，是在导师指导下独立完成的，学位论文的知识产权属于山西大学。如果今后以其他单位名义发表与在读期间学位论文相关的内容，将承担法律责任。除文中已经注明引用的文献资料外，本学位论文不包括任何其
14、他个人或集体已经发表或撰写过的成果。学2 位0 0 鬻, E l 髫：甜包军7 年S；日。绪论绪论图论作为离散数学的一个重要分支，已有两百余年的历史在它的发展历史上，包括E u l e r H a m i l t o n 、C a y l e y 等数学大家都作出过杰出贡献图论也是一门应用十分广泛的数学分支，应用图论解决运筹学、物理，化学、生物，计算机科学网络理论、信息论社会科学以及管理科学等方面的问题都有其独特的优越性现代计算机和网络技术的发展不仅为图论提供了广阔的应用背景，也刺激了图论和算法的发展，使得以前不可能解决的问题变成了可能，比如寻找最短路如何将图嵌入平面中，寻找最小生成树等同题都
15、有了好的算法反过来，图论及算法的发展也为计算机网络的发展提供了理论依据图论的研究最初是从无向图开始的，但由于近年来许多新的问题和猜想的不断提出，无向图已经不能满足需要，更多的情况下需要的图理论模型是有向图，甚至是超图，混合图，从而使得无向图和有向图的相互转化成为必要本篇论文研究的关于无向图的优化定向问题中的最小直径定向问题就是其中的一例最小直径定向问题是在对单行街和流言等的实际问题的研究中首次提出来的，随后在通讯网络及计算机网络中得到了应用由于它们具有强大的应用背景，故该问题受到了诸多图论学者的重视，而且这两个问题目前仍为热点对于一般的图类研究它的最小直径定向问题是难的，人们往往从两方面着手，
16、一方面寻找有效的算法；另一方面从特殊的图类入手在研究这个问题的过程中，K o h和T a y 已有如下结果：d ( a ) d ( G ( s l ，8 2 ，s 。) ) d ( a ) + 2 ，其中G ( s l ，S 2 ，s 。)为连通无向图G 的顶点扩张图进一步，K o h 和 r a y 提出了一个猜想t 如果无向图G 的直径大于或者等于3 ，则G 的顶点扩张图G ( s 1 ，s 2 ，) 的最小直径定向满足下列不等式，a ( C ) d ( G ( 8 1 ，s 2 ，s 。) ) Sd ( G ) + 1 对于满足条件的的路，圈，以及树的顶点扩张囹，此猜想已被验证是正确的本文第一章主要研究单圈图的顶点扩张图的最小直径定向问题另外，R o b b i n s 的著名的单行街定理【1 j 中说到：一个连通的无向图G 有一个强定向当且仅当G 无桥对一个连通的无桥无向图G ，
