《连通图群连通性度条件》由会员分享，可在线阅读，更多相关《连通图群连通性度条件（45页珍藏版）》请在金锄头文库上搜索。
1、山东大学硕士学位论文连通图群连通性的度条件庄勇振( 山东大学数学学院，济南，2 5 0 1 0 0 )( 指导教师：颜谨)中文摘要本文考虑的图均为有限图，但是图中可能包含重边，对于图G = G ( V 动，我们用V ( G ) 和E ( G ) 表示图的顶点集合与边集合对于图G 中的不相交顶点子集K ，定义e ( ，) 为端点分别在，K 中的边的集合特别的，当= X ，且= V ( G ) 一x 时，用a ( x ) 代替e ( x ，V ( G ) 一X ) 定义图G 上的方向D = D ( G ) ，若边e E ( G ) 的方向为由点u 到点移，则我们称t a i l ( e ) = u
2、 与k a d ( e ) = 秒并且对于图G 中的一个顶点“ y ( G ) ，定义正葛( t ，) = eEE ( D ) ：t ，= 扎“z ( e ) 与五；! 去( 移) = ( e E ( D ) ：t ，= e 口d ( e ) ) A 是非平凡的阿贝尔加法群，0 是它的加法单位元，记A = A 一0 表示A 中非零元素的集合，并定义函数F ( G ，A ) = ，：E ( G ) 一A 与P ( G ，A ) = ，：E ( G ) 一A 给定函数，F ( G ，A ) ，定义：v ( G ) 一A 如下：甜( t ，) = 你) 一你) c 砧扣)e 对于图G ，如果6 (
3、t ，) = 0 ，则称函数b ：V ( G ) 一A 为A 零值加畦v 。( 0 9 和函数这种函数的集合用z ( G ，A ) 表示，给定b z ( c ，A ) ，若存在函数，P ( G ，A ) 使得a y = b ，则称，为( A ，6 ) 一处处无零流若对于任意b Z ( G ，A ) ，图G 都存在( A ，6 ) 一处处无零流，则称图G 为A 连通的 作为解决图的染色问题的重要工具，处处无零流理论由T u t t e 在十九世纪五十年代提出经过半个世纪的研究与发展，其理论日益成熟和完善，并被一I 一山东大学硕士学位论文推广与扩展到群连通理论群连通理论作为处处无零流理论的延伸，不
4、仅是解决一系列理论问题的重要方法与工具，同时在通信网络设计、计算机科学等中都有非常重要的应用群连通理论研究的重心主要是在确定一般图的群连通度上本文主要讨论了满足一定度条件的一般图的群连通度问题全文共分三章，第一章简单介绍了图论的基本概念，群连通理论的历史与发展状况以及一些已有的相关结论第二章讨论了满足一定度条件的图的群连通度，证明了以下结论：定理2 1 1A 为满足l A I 4 的阿贝尔群，图G 为简单二边连通图，并且满足n = l y ( G ) I 2 1 如果对于任意t ，v ( c ) 且伽暑E ( C )都有m a x d ( u ) ，d ( t ，) n 5 ，则图G 为止连通
5、图，或者G 图集P 进 一步，若有G 鲍，5 ，配，4 ，K 2 a ，a ，则有A g ( G ) = 5 ；翻f f G * = G ，则 冒( G ) = 6 ；若有G + = 岛，则( G ) = 7 在第三章中我们还提出了一些问题，以待进一步研究关键字：群连通；阿贝尔群；, 4 - 连通一I I 山东大学硕士学位论文D e g r e eC o n d i t i o n sf o rG r o u pC o n n e c t i v i t yi n C o n n e c t e dG r a p h sY o n g z h e nZ h u a n g( S c h o o
6、 lo fM a t h e m a t i c s ，S h a n d o n gU n i v e r s i t y , J i n s n ，2 5 0 1 0 0 )( S u p e r v i s o r ：J i nY a h )A B S T R A C TA ng r a p h sc o n s i d e r e di nt h i sp a p e ra r ef i n i t ea n dm a yh a v em u l t i p l ee d g e s L e tG = ( y ( G ) ，E ( G ) ) b eag r a p h ，w h e
7、r eV ( G ) m u dE ( G ) d e n o t et h ev e r t e xs e ta n de d g es e t0 fG ，r e s p e c t i v e l y L e tK ，b et w os u b s e t so fV ( G ) s u c ht h a t Hn V 2 = 9 W ed e f i n ee ( ，V 2 ) 船t h en u m b e ro fe 衄留w i t ho n ee n dv e r t e xi n Ha n dt h eo t h e ro n ei n I np a r t i c u l a
8、r ，w h e nV t = Xa n d = V ( G ) 一X ，w eu s eo ( x ) i n s t e a do fe ( x ，V ( G ) 一x ) L e tD = D ( G ) b ea no r i e n t a t i o no fag r a p hG I fa ne d g ee E ( G ) i sd i r e c t e df T o mav e r t e xut oav e r t e xt ，t h e nl e tt a i l ( e ) = ua n dk 6 d ( e ) = “ F o rav e r t e x 移y (
9、G ) ，l e t互葛( 口) = e E ( D ) ：t ，= t a i l ( e ) a n d 砧 ) = e E ( D ) ：t ，= ，l e 以( e ) ) L e tAd e n o t ea na d d i t i v ea b e l i a ng r o u pw h e r et h ei d e n t i t yo fAi sd e n o t e db y0 L e t 岔d e n o t et h es e to fn o n z e r oe l e m e n t so fA W ed e f i n e ：F ( G ，A ) = ，：E (
10、 G ) 一A ) a n d F * ( C ，A ) = ，：E ( G ) 卜+ A ) G i v e naf u n c t i o n ，F ( G ，锄，d e f i n eo f ：V ( G ) 卜+ Ab ya m ) = f ( e ) - ，( e )e 砧( c E E 5 ( v )F o rag r a p hG ，af u n c t i o nb ：V ( G ) 一Ai sc a l l e da nA - v a l u e dz e r os l i mf u n c t i o no nGi f 6 ( “ ) = 0 T h es e to fa
11、l lA - v a l u e dz e r os u mf u n c t i o n so n管y ( G ) Gi sd e n o t e db yZ ( G ，A ) G i v e nb z ( c ，A ) ，af u n c t i o n ，P ( G ，A ) i sc a l l e dI I I 山东大学硕士学位论文a n ( A ，b ) - n o w h e r e - z e r of l o wf fGh a sa no r i e n t a t i o nD ( G ) s u c ht h a t 甜= hAg r a p hGi sA - c o n
12、 n e c t e di ff o ra n yb z ( a ，A ) ，Gh a s 柚( A ，b ) - n o w h e r e - z e r of l o w 眦t ei n1 9 5 0 Si n t r o d u c e dt h et h e o r yo fn o w h e r ez e r of l o w sa sat o o lt oi n v e s t i g a t et h ec o l o r i n gp r o b l e mo fm a p s T h ed i s c u s s i o ni sm a t u r ea n dp e r
13、f e c ti n c r e a s i n g l y T h e s eh a v eb e e ne x t e n d e dt og r o u pc o n n e c t i v i t yi n1 9 9 2 A n dg r o u pc o n n e c t i v i t yi si m p o r t a n ta p p l i c a t i o n st oc o m p u t e rs c i e n c ea n dn e t w o r k T h es t u d yo fg r o u pc o n n e c t i v i t ym o s
14、t l yf o c u so nt h eg r o u pc o n n e c t i v i t yo fn o r m a lg r a p h s T h ei n n o v a t i o no ft h i sp a p e ri sd i s c u s s i n gt h eg r o u pc o n n e c t i v i t yf o rt h eg r a p h ss a t i s f y i n g8 0 m ed e g r e ec o n d i t i o n s T h ep a p e ri sd i v i d e di n t ot h
15、 r e ec h a p t e r s I nC h a p t e r1 ，w ei n t r o d u c es o m eb a s i cn o t a t i o n sa n dg i v eac o n c i s es u r v e yo nt h eh i s t o r ya n dt h ep r o g r e s so nt h eg r o u pc o n n e c t i v i t y , a n ds o m ep r i m a r yr e s u l t sa b o u tt h ep a p e r I nC h a p t e r2
16、，w ei n v e s t i g a t et h eg r o u pc o n n e c t i v i t yf o rt h eg r a p h ss a t i s -研n gs o m ed e g r e ec o n d i t i o n sa n dp r o v et h ef o U o w i n gr e s u l t T h e o r e m2 1 1L e tAb ea na b e l i a ng r o u p 硒t hI A I 4 ，a n dGa2 _ e d g e -c o n n e c t e ds i m p l eg r a p h so nn = I y ( G ) l 2 1v e r t i c e s I ff o re v
