代數(shù)圖論中的兩個(gè)問題--Cayley圖和緊圖.pdf

1、中國科學(xué)技術(shù)大學(xué)博士學(xué)位論文代數(shù)圖論中的兩個(gè)問題--Cayley圖和緊圖姓名：王平申請學(xué)位級別：博士專業(yè)：應(yīng)用數(shù)學(xué)指導(dǎo)教師：李炯生2000.3.1A b s t r a c tI n o u rp a p e r ，w em a i n l yd i s c u s st w op r o b l e m si n a l g e b r ag r a p ht h e o r y ：t h en o r m a l i t yo fC

2、 a y l e yd i g r a p h so f d e g r e e2a n dt h ec o n l p & c te r a p h s ．I nC h a p t e r1 1 w e i n t r o d u c et i l er e c e n ts i t u a t i o n sa n d o u rr e s e a r c hr e s u l t sa b o u tt h en o r

3、m a l i t yo fC a y l e yd i g r a p h sa n dc o l n p a c tg r a p h s ．1 1 1 C h a p t e r2 ，w eC o n c e n t r a t e O i l d e c i d i n g t l l e n o r t o n l i t y o fC a y l e yd i g r a p h so fd e g r e e2 ．L e

4、tGb e an o n a b e l i a n f i n i t e g r o u pa n dSa2 - e l e m e n tg e u e r a t i n gs u b s e t u o tc o n t a i n i n gt h ei d e n t i t y 1 ．D e n o t e dt i l e c o r r e s p o n d i n gC a y l e yd i g r a p

5、hb yF = C a y ( a ，s ) ．I l ls e c t i o n2 ．1 ，w ed i s c u s st h ec a s ew h e nG i s o fo d do r d e ra n dn o l t a b e l i a u ．A tf i r s t ，i ns e c t i o n2 ．1 ．1 ，w ed e f i n eal t e wd i g r a p hA ( F ) a n

6、du s ei t t op r o v et h a ti fG i so fo d do r d e ra n d F i sl l O n u o r m a l ，t i l ea u t o m o r p h i s m g r o u p A u t ( r )o fFi ss o l v a b l e ．F u r t h e r ，w ep r o v et h a ti fI G l = p t ?p 擘w h e

7、 r ef t S 2a n dP i ’s a r eo d dp r i m e s ，F(xiàn)i sn o r m a l ．L e tN b ea n o n t r i v i a lm i n i m a ln o r m a ls u b g r o u p o fA u t ( r ) ．I ns e c t i o n2 ．1 ．2 ．w e u s eag r a p hP Nd e f i n e db yC ．H ．L

8、 ia n do n eo fh i sl e n i m a st oa b b r e v i a t et h en o n n o r m a lC a y l e yd i g r a p h Fi n t o t i l e c a s ew h e nF Ni s ad i c y c l e ．W h e nF Ni s ad i c y c l e ，w eg i v et i l e s u f f i c i e

9、n ta n dn e c e s s a r yc o n d i t i o n sf o r Ft ob en o n n o r m a la n dt i l es t r u c t u r eo ft i l ec o r r e s p o n d i n ga u t o m o r p h i s m g r o u pA u t ( F ) ．I ns e c t i o n2 ．2 ，w ed i s c u s

10、 st l l e c a s ew h e uJ G f i s e v e ua n dp r o v et h a tw h e nf G f = 2 p q ，F(xiàn)i s n o r m a l ，w h e r e P ，q a r ed i s t i n c to d dp r i m e s ．1 1 1 C h a p t e r 3 ，w ec o n c e n t r a t e0 1 1 c h a r a c

11、t e r i z i n gt h ec o m p a c tg l ’a p h s ．W h e nar e g u l a rg r a p h i sc o n ：p a c t ，i ti sv e r t e x - t r a n s i t i v e ．S o jw e g a l lu s et i l ec o n c l u s i o n sf r o ma s s o c i a t i o ns c h

12、 e m e ．L e tA u t ( G ) b e t h ea u t o m o r p h i s mg r o u po fac o m p a c t g r a p hG ．I ns e c t i o n3 ．1 ，a c c o r d i n gt o o n e o f C ．D ．G o d s i l ’St h e o r e m s ，t l l ep e r m u t a t i o n c h a

13、 r a c t e ro fA u t ( G ) i sm u l t i p l i c i t y - f r e e ，a n d t i l e a s s o c i a t i o n s c h e m ew h i c h c o n s i s t s o f t i l ec o r r e s p o n d i n go r b i t a lg r a p h si sc o m m u t a t i v

14、 ea n ds y m m e t r i c ．T h e n ，t i l ea d j a c e n c ym a t r i c e so fo r b i t a lg r a p h sa r et i l e n o n n e g a t i v el i n e a rs u m so fp e r m u t a t i o nm a t r i c e si n A u t ( G ) ．W i t ht i

15、l e k n o w l e d g ef r o mc o m b i n a t o r i a lm a t r i xt h e o r y ，w ec h a r a c t e r i z et h er e g u l a rc o m p a c tg r a p h so fd e g r e e3o r 4 。I l ls e c t i o n3 , 2 ，w eg i v et w ow a y st oc o

16、 n s t r u c ti r r e g u l a l ’c o m p a c tg r a p h s ．I nC h a p t e r4 ，w em a i n l yg i v es o m eb a s i cc o n c e p t sa n df a c t si n a b s t r a c tg r o u pt h e o r ya n dg r o u pr e p r e s e n t a t i

17、 o nt h e o r y ，p e r m u t a t i o i lg r o u pt h e o r ya n da s s o c i a t i o ns c h e m e ．M o r e o v e r ，w ea l s oi n t r o d u c ts o m ed e f i n i t i o n sa n dr e s u l t sr e l a t e dt oC a ) ．1 c vd i