（应用数学专业论文）代数图论中的两个问题cayley图和紧图.pdf

摘要 本文主要讨论代数图论中的两个问题一2 度( 1 a y e y 有向图的正规性和紧 图 第一章概述正规c 2 a 5 ，l e 3 r 有向图和紧图的研究现状以及我们的研究进展 第二章集中讨论正规2 度c a 3 ，l e y 有向图的刻划问题( 设g 是一个非阿贝尔 有限群，s 是它的一个2 元生成子集记对应的c a y l e y 有向图为f = c a y ( g ，扎 第2 1 节讨论g 是奇阶群的情况首先，在第2 1 1 节中，我们定义一个新图 4 ( r ) 利用这个图，证明了当g 是奇阶群而且r 非正规时，r 的自同构群 a u t ( f ) 可解然后证明如果吲= p ；1 p 铲1 i 2 ，p l 是奇素数，i = 1 ，2 ，m ， 则r 是正规的在第2 1 2 节中，我们应用( 1 hl i 定义的一个图r n 、其中a 是a u t ( f ) 的一个非平凡极小正规子群，和他的一个引理，把对非正规c a y l e y 有向图r 的讨论简化到r 是一个有向圈的情况，进而决定了当r n 为有向圈 时，r 非正规的充要条件和a u t ( f ) 的结构在第2 2 节中，我们讨论g 是偶 阶群的情形，证明了当i g l = 2 p g 时，r 是正规的，这里p ，q 是不同奇素数夕 第三章集中讨论紧图的刻划问题挡一个正则图紧时，它是点可迁的因 此可以引用结合方案的有关结论设a u t ( g ) 是紧图g 的自同构群在第3l 节，根据c d g o d s i l 的定理，a n t ( ( ? ) 的置换特征标满足无重性条件，而且 轨道图组成的结合方案是可交换且对称的于是，轨道图的邻接矩阵可以表示 成a u t ( g ) 中置换矩阵的非负线性和借助于组合矩阵论的知识，我们刻划了 3 度和4 度正则紧图在第3 2 节给出了两种构造非正则紧图的方法j “ 第四章主要概述本文所涉及的有关地象联论和彗表示论，置换群理论以 及结合方案的基本概念和基本结果，以及与c a 3 r l e y 有向图和紧图有关的定义 和知识 a b s t r a c t i no 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 na l g e b r ag r a p ht h e o r y ：t h e n o r m a l i t yo fc a y l e yd i g r a p h so fd 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 1w ei 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 do u rr e s e a r c hr e s u l t sa b o u t t h en o r 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 gt l l en o r t o n l i t y o fc a y l e yd i g r a p h s o fd e g r e e2 l e tgb ean o n a b e l i a nf 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 g s u b s e tu o tc o n t a i n i n gt h ei d e n t i t y1 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 h b 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 so fo d do r d e ra n d n 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 du s ei tt o p r o v et h a ti fg i so fo d do r d e ra n dfi 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 pa 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 r ef t s2a n dp i s a r e o d dp r i m e s ，fi sn o r m a l l e tnb ean 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 po fa u t ( r ) i ns e c t i o n2 1 2 w eu s eag r a p hp nd e f i n e db yc h l ia n do n eo fh i sl e n i m a st o a 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 hfi n t ot i l ec a s ew h e nf ni sad i c y c l e w h e nf ni sad i c y c l e ，w eg i v et i l es u f f i c i e n ta n dn e c e s s a r yc o n d i t i o n sf o rft ob e n 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 n s e c t i o n2 2 ，w ed i s c u s st l l ec a s ew h e uj g fi se v e ua n dp r o v et h a tw h e nf g f = 2 p q ，f i sn o r m a l ，w h e r e p ，qa 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 r3 ，w ec o n c e n t r a t e0 1 1c h a r a c t e r i z i n gt h ec o m p a c tg l a p h s w h e na r 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 eg a l lu s et i l ec o n c l u s i o n sf r o m a s s o c i a t i o ns c h e m e l e ta u t ( g ) b et 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 oo n eo 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 nc h a r a c t e r o fa u t ( g ) i sm u l t i p l i c i t y - f r e e ，a n dt i l ea s s o c i a t i o ns c h e m ew h i c hc o n s i s t so ft i l e c 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 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 y m a t r i c e so fo r b i t a lg r a p h sa r et i l en 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 s i na u t ( g ) w i t ht i 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 e t 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 r4 。i l ls e c t i o n3 , 2 ，w eg i v et w ow a y st o c o 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 na b s t r a c tg r o u p t h e o r ya n dg r o u pr e p r e s e n t a t i 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 n s 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 v d i g r a p ha n dc o m p a c tg r a p h 第一章概述 自从二十世纪八十年代初有限单群分类问题解决以来，有限群的面目发 生了很大的变化，抽象群论和置换群论的一些问题获得了解决用群论的现有 成果和方法去研究组合结构，为组合数学注入了新的活力，正成为当今组合数 学研究的一个新趋势 本文主要讨论c a x ，l e 3 7 图的正规性和置换群论在刻划紧图问题上的一些应 用 1 1 正规c a y l e y 图 在第二章，我们讨论c a ) t l e 3 t 图的正规性c a y l e y 图是在抽象群上定义的 图，它是图论研究的重要领域之一早在t 8 8 7 年，c a y l e y 就引进了c a y l e 3 ，图 的概念在此之后，c a y l e y 图的研究经历了几个发展阶段二十世纪三十年 代，f r u c h t 在证明任意抽象群都同构于某个图的自同构群时，c a 3 ，l e y 图起了 重要的作用这大大刺激了人们对c a y l e x r 图的研究二十世纪六十年代提出的 群的图正则表示和有向图正则表示以及 c l 抽猜想，p ar s o n 猜想等将c a y l e ) ， 图的研究推向一个高潮从二十世纪七十年代开始，由于建造大型计算机通 信网络及可靠性设计的需要，人们希望构造具有高度对称性的直径较小而连 通度较大的图和有向图，这自然要借助于c a y l e y 图( 2 3 ) 这样，c a y l e y 图连 通度和直径的研究就提到了议事日程二十世纪九十年代以来，研究主要集 中于刻划具有高度对称性的点可迁图，如弧可迁图、点本原图、( ：i 群等，而 c a y l e y 图在其中占了很大比例所有的这些问题都关系到图的自同构问题 对c a y l e y 图的研究在某种意义上说是对代数、组合结构研究的进一步精 细化和发展，而代数、组合结构理论又为c a x r l e y 图的研究创造了条件，它们 互相影响、互相渗透这方面的大量研究成果发表在国内外一些重要学术刊 物上，现代许多著名的代数、组合、图论数学家在这一领域都做了深入的研究 工作可以说c a y l e y 图的研究是以图的结构为基础，以代数方法为工具，具 有重要应用前景的一个交叉研究领域 假设g 是一个有限群，s 是g 的不含单位元1 的子集，g 上相对于s 的c a , y l e y 有向图记作f = c a y ( g ，吼这里 r ) = g ，e ( v ) = ( g ，口s ) 旧g ，s _ ) 对c a y l e y 图，我们可以定义下面的图同构 如：f _ 这里g _ g 从而g 有下面的左正则表示“f ， 下面的结论是显然的： 定理1 1 1 设f = c a y ( ( ? ，趵是( ? 相对于子集，的c a y l e y 有向图则 ( 1 ) g l _ a u t ( p ) ， ( 2 ) 2f 是连通的当且仅当g = ( ：，) r 是无向的当且仅当_ “= _ 定理1 1 2 一个有向图x 是一个c a x 7 l e x 有向图c ”，( “，) 当且仅当它的自同 构群a u t ( x ) 含有一个同构于矗的正则子群 定义群 a u t ( g ，) = d a u t ( a ) 1 s 6 = ，) 可知g c a u t ( g 、s ) a u t ( r ) 设4 = a u t ( r ) - 4 l 是 4 固定g 的单位元的稳定子 群则有下面的结论( 看1 5 3 ) ： 引理1 1 3 ( 1 ) n a ( g l ) = ( ；l a u t ( g _ ) ： ( 2 ) 下面的结果是等价的， ( 2 1 ) a = g l a u t ( g ，) ， ( 2 2 ) a ls h u t ( g ，s ) f 2 3 ) g lq ，4 确定一个图的自同构群是一个很困难的问题，有时是不可能的而对亍 c a y l e y 图f = c a g ( g ，s ) ，我们知道它有一个正则子群因此，研究它的自同 构群a u t ( f ) 的结构是有意义的工作从各个方面考虑它的自同构群和点稳定 子群a 的作用，出现了许多有趣的课题比如当a u t o ) 作用在图的弧集上 时，有可能不可迁我们定义一个图是弧可迁的或对称的，如果它的自同构群 在它的弧集上可迁刻划所有的弧可迁图是一个困难的课题，现在一般考虑循 环图( g 为循环群的c a y l e y 有向图) 相关的文献可看 5 4 当图的自同构群虽 在弧集上不可迁，但在点集和边集上可迁时，则称它是i 1 可迁的c a y l e y 图经 常出现在i 1 可迁图的研究中，例如 5 1 研究i 1 可迁图的文献很多，近期的就 有 1 4 ， 3 4 ，【3 5 ， 3 6 ， 3 9 l 综述可看 3 5 5 2 另一个课题是c a y l e y 图之间的陌构 问题( c a y | e yi s o m o r p h i s m ) 设r = c a y ( g ，s ) 是g 相对于子集s 的一个c a y l e y 有向图，o a u t ( g ) 则。也是从c a y l e y 有向图c a y ( g ，s ) 到c a y ( g ，s 。) 的 一个图同构我们称这种同构为c a f f l e y 同构( c i ) 子集s 称作一个c i 子集， 如果对任意同构于c a y ( g ，s ) 的c a y l e y 有向图c a y ( g ，t ) ，总存在一个c a y l e y 同构映c a y ( g ，s ) 到c a y ( g ，t ) ，即存在一个o a u t ( g ) 使得t = s o 不是任 意的子集能是c i 子集一个重要的结果( 2 9 ) 是下面的 定理1 1 4 设g 是一个有限群，p 是i g l 的最小素因子设s 是g 的生成子 集且j s l p ，则s 是一个c i 子集 类似的定义还有c i ，d c i 群等等相关的文献和综述可看5 3 1 当a l _ 3 是一个奇素数这时，h u t ( r ) = 岛2 邑在g 上作用本原，而且r 和它的补图不是正规的 定理1 1 1 0 设x 是双可迁h a d a i l i a r d2 - ( 1 1 , 5 ，2 ) 设计或它的补设计的关联图 则x 的自同构群同构于p s l ( 2 ，1 1 ) 易这个群有一个同构于d 2 2 的正则子 群当把x 看作d 2 2 的c a y l e y 图时，它是非正规的 定理1 1 1 1 设x 是射影平面p g ( n 一1 ，q ) 的点一超平面关联图则它的自同 构群a 同构于p f l ( n ，g ) 历如果p = ( g “一1 ) ( q 一1 ) 是一个素数，则a 有 一个正则子群d 2 。，而且x 是非正规的 c a y l e y 有向图的正规性对弧可迁有向图，半可迁图的研究有着重要意义 ( 看 1 8 ， 5 1 ) 例如，当r 是一个正规c a y l e y 图时，由引理1 1 3 易知，r 是弧 可迁的当且仅当a u t ( a ，s ) 在单位元的邻域上可迁实际上，对弧可迁图的刻 划是提出c a y l e y 图的正规性的原因之一 类似于群的图正则表示问题，一个问题是，是否每个群都有正规c a y l o y 图和c a y l e y 有向图? 这个问题已经完全解决，w a n g ，w a n g 和徐明曜在文献 【4 3 中证明了 定理1 1 1 2 设g 是一个有限群 ( 1 ) g 必有正规c a y l e y 无向图，除非g 望蜀玩或者q 8x 历，这里q 8 是8 阶四元数群 ( 2 ) g 必有正规c a y l e y 有向图 非正规c a y l e y 图和c a y l e y 有向图是稀少的，徐明曜在 5 3 中猜测几乎所 有的c a y l e y 图和c a y l e y 有向图是正规的，具体说 猜想1 1 1 3 设g 。是n 阶群的集合记 和 ，、g 的正规c a y l e y 有向图数 ，l j = m 1 1 1 一 “7 g g n g 的c a y l e y 有向图数 7 c n ，= g 。，g m ；i n q 。尹鱼! ! i ；2 ：黯 9 徐明曜猜测 。1 i r a 。，( ? 2 ) 21 ，舰m ) 2 1 一个自然的问题是，对给定的有限群g ，决定它的所有正规的或非正规的 c a y l e y 有向图中国数学家作了大部分工作，较近的综述文章可看【5 3 但目 前仍是一个非常困难的问题对一个群的c a y l e y 有向图的正规性有完整的了 解的情况相当少，只限于素数阶循环群( 看 1 ) 和2 p 阶群( 看 1 3 ) 如果考虑 仅边可迁( o n l ye d g e t r a n s i t i v e ) 的c a y l e y 图，有下面的结果( a l s p a c h 【3 ，c h e n g 和o x e y 1 2 ，p r a e g e r 等【3 7 ，3 s ，w a a l g 和x u 【4 4 ) ： 定理1 1 1 4 设q 3 ； ( g ，s ) p k l 一p g ( q ，s ) ，g 3 和k 2 咖凡1 一p k 2 ， ( 3 3 ) 定理1 1 1 0 和定理1 1 1 1 中的图，其中的q = 2 对p 2 阶群，l i ，w a n g 和x u 在【3 1 中证明 定理1 1 1 5 设p 是一个奇素数则 ( 1 ) 定理1 1 9 中定义的图是唯一的p 2 阶非正规点本原c a y l e y 图， ( 2 ) 设x 是非正规仅边可迁c a y l e y 图如果a u t ( x ) 非本原，则x 是 g ( 】) ，r ) ( 2 ，k 1 】，g ( 】) ，7 ) 【p k l 一v g ( p ，) ，这里的p ，r 满足定理1 1 1 4 中的条件 进一步的问题是考虑非本原，非仅边可迁的情况徐 5 3 提出 问题1 1 1 6 决定所有p q ，p 2 阶非本原且非正规的c a y l e y 图和c a y l e y 有向图 关于正规c a y l e y 图和c a y l e y 有向图的连通性，w a n g ，w a n g 和徐明曜 4 3 证明了下面几个定理一 定理1 1 1 7 设f = c a y ( 5 ，s ) 是群g 的正规c a y l e y 图则r 不连通当且仅当 g 垒召+ 1 或历z _ ，其中r = i 或，5 ，且口= 掣召，w = c a y ( g ，s ) l o 是h 的一个g r r 定理1 1 1 8 设r = c a y ( a ，s ) 是群g 的正规c a y l e y 有向图，那么，r 不强连 通当且仅当g 有子群h 使得 ( 1 ) h 是g 的真非单位交换子群，且i g ：h l = 2 ， ( 2 ) 对任意b g h 和h h ，有b 4 = l 和b “h b = 7 l ， ( 3 ) w = c a y ( h ，s ) 是h 的d r r 因此，在本文中，总设c a y l e y 图和c a y l e y 有向图是连通的 对具有特殊阶的群，徐明曜 5 4 证明了下面几个定理 定理1 1 1 9 设g 是一个p ”阶循环群，s 是它的不含0 元的子集定义 r = c a y ( g ，s ) 的边集是e ( p ) = ( g ，g + s ) l g g ，8 s ) 假设r 不是空图和完 全图如果( i a u t ( a ，s ) i ，p ) = 1 ，那么r 是正规的 定理1 1 2 0 设p 是奇素数如果p l i a * ( a ，s ) i ，那么r 不是正规的 关于具有特殊生成子集s 的c a y l e y 有向图，徐明曜提出了下面的问题 ( 5 3 ，问题6 ) ： 问题1 1 2 1 设g 是一个有限群，s 是它的一个极小生成子集 ( 1 ) s 和s u s - 1 是c | ，一子集吗? ( 2 ) 相应的ca _ y | e y 有向图和图是正规的吗? 在文章【2 4 ， 2 5 】和 2 6 】，h u a n g 和m e n g 证明， 定理1 1 2 2 设g 是一个有限循环群，s 是它的极小生成子集记r = c a y ( g ，j ， r = c a y ( a ，s u s _ 1 ) 设刊黾使得对任意g g ，9 5 = g _ 1 的g 的自同构这时， a u t ( f ) = 吼，a u t ( g ) = g l 即，对上面两个问题的解答是肯定的 进一步，当g 是阿贝尔群，s 是极小生成子集时，f e n g 和g a o 【1 7 已证 明，当g 的s y l o w2 子群是循环群时，对徐的问题的回答是肯定的，否则一 般是否定的 对于小度数c a y l e y 图，f a l l g ，l i ，w a n g 和x u 1 5 证明了 定理1 1 2 3 设g 是下面的单群中的一个t ( 1 ) g 是离散单群，且g m m 2 2 ，m 2 3 ，s u z ； ( 2 ) g = a 。，这里n 彰 5 ，1 1 ，2 3 ，4 7 ) u 2 ”2 一l l m 3 ) ； ( 3 ) g 是奇特征l i e 型单群，可能g l 2 ( “) ； ( 4 ) g = l 2 ( 2 。) ，l 3 ( 2 。) ，( 2 6 ) ，p s p 4 ( 2 。) ，e 8 ( 2 。) ，f 4 ( 2 。) ，2 f 4 ( 2 8 ) ，g 2 ( 2 。) ，或者 s ：( 2 e ) 设r 是g 的3 度连通c 埘l e y 图则g l o ) 定义5 ( a ) = s i s 是双随机矩阵，而且s a = a s 则有p ( a ) s ( 4 ) 一个自 1 4 然的问题是，当g 是什么图时， - p ( a ) = s ( a ) ? 并不是对所有的图g ，均有- p ( a ) = 5 f ( 4 ) ，例如下面的7 阶图g 因为g 是正则图，故有 a 圭j = 圭| ，a ， jf 即 ：j s ( a ) - 但 ，g - p ( a ) 这是因为g 不是点可迁的，故g 不可能有把顶点l 变到顶点4 的自同构 如果对一个图g 有- p ( a ) = s ( a ) ，则称g 是紧的( c o m p a c t ) 易见b i r k h o f f 定理等价于说空( n u l l ) 图是紧的因此，紧图的概念是b i r k h o f f 定理的拓广 紧图的同枸有一个好算法t i n h o f e r 在 4 2 】给了一个算法g r a p h i s ，并 证明 定理1 2 2 如果g 是一个紧图，那么算法g r a p h i s 能在多项式时间内判定d 是否同构于另一个相同阶的图日 因此在 2 1 ，c d g o d s i l 提出问题紧图有一个好的刻划吗? 容易看到，完全图( 其邻接矩阵a = j 。一h ) 是紧的紧图的补图也是 紧的t i n h o f e r 4 1 1 证明了 定理1 2 3 圈是紧图 定理1 2 4 树t 是紧图 设g 是二部图，它的邻接矩阵为a ( g ) = ( 耋。言) ，这里b 是一个m ，t 的 1 5 ( 。，1 ) 一矩阵定义一个新图( 一它的邻接矩阵州g 7 ) = ( 。0 一b ，以“ o b ) g 称为g 的1 ，补( b - c o m p l e m e n q 关于b 一补，t i n h o f e r 证明了下面的定理 ( 4 2 ，定理5 ) ： 定理1 2 5 如果g 和g 7 都是连通图，则g 7 是紧的当且仅当g 是紧的 当g 和d 7 中有一个不连通时，b r u a l d i 证明了下面的结果 9 ： 引理1 2 6m k ：的b ，补是紧的，这里m k 2 是个凡。的不交并 对于给定的一个图，决定它的紧性是困难的一个方法是考虑紧图需要满 足的条件来否定一些图的紧性通过考虑均匀划分( e q u i t a b l ep a r t i t i o n ) ，c d g o d s i l 2 0 证明了，当1 2 ? 时，虬的线图不是紧的，并在同一篇文章，证 明了一个重要的定理， 定理1 2 7 设g 是一个有r 个不同特征值的正则图如果g 是紧的，则它的 自同构群a u t ( g ) 是一个秩为7 - 的泛可迁( g e n e l o u s l yt r a n s i t i v e ) 置换群 这个定理的证明对我们的结果是重要的其证明大致如下设c ( a ) 是所有 与a 可交换的矩阵空间首先证明( 。( 4 ) 和s ( 4 ) 的线怯维数( 1 i n e a rd i m e n s i o n ) 相等然后，计算p ( a ) 的线性维数，而f ( 4 ) 的线性维数等于a u t ( g ) 的置换 特征标中不同不可约特征标的维数平方和因为( a ) 和s ( 4 ) 的相等关系， 从而证明置换特征标是无重的( m utp l i c i t y f r e e ) t i n h o f e r ( 4 2 ，定理6 ) 证明了下面的结果， 定理1 2 8 设g = g 1u u 吼，这里g 1 兰兰g k 则d 是紧的当且仅当g 1 是紧的 s c hr e c k 和t i n h o f e r 在 4 0 证明了： 定理1 2 9 设g 是p 阶点可迁图，这里p 是素数如果它不是完全图或者空 ( n u l l ) 图，则g 是紧的当且仅当它的自同构群同构于二面体群d 抄 定理1 2 1 0 设g 是一个”阶循环图如果它的特征子空间的维数不大于2 ，则 g 是紧的 设g 是n 阶正则紧图因为，( - 4 ) ，故g 是可迁的值得注意的是， b o l l o b f i s 8 证明了下面的结果： 引理1 2 1 1 几乎所有正则图是非对称的，即，它的自同构群是平凡的 由此可见，正则紧图是很少的因而刻划紧图的问题具有相当难度由于 组合矩阵论专家b l i l a l c l l 和代数组合论专家g o d s i 的介入，这一问题引起了人 们的广泛关注研究的途径主要有两种一种主要是从组合矩阵论方向来考 虑的，通过矩阵运算和讨论矩阵的特征向量来证明双随机矩阵含有要求的置 换矩阵；另一种主要是从代数组合学方面考虑，比如象g o d s i l ，通过讨论图的 自同构群以及特征标来证明结果，这时主要讨论正则图这两种方法是分不开 的在我们的文章中，主要考虑正则图的紧性因此，我们交替使用这两种方 法 我们知道，点可迁图g 是它的自同构群在集合1 1 ，( g ) v ( g ) 上的轨道图 的边不交的并当g 不是一个轨道图，即它是几个小度数的轨道图的并时， 我们可以先分析当g 是紧图时，这些小度数的轨道图需要满足的条件注意 到轨道图的集合是一个对称交换结合方案，轨道图的邻接矩阵应可以分解成 置换矩阵的非负线性和从这一点出发，我们能初步确定那些图可能是紧图， 这时主要用的是组合矩阵论中的方法然后，我们分析图的自同构群和它的特 征标，进一步确定需要满足的条件，这时主要用代数组合学中的方法交替使 用这两种方法，我们刻划了度数不大于4 的正则紧图 下面的结论是显然的， 定理1 2 1 2 ( 1 1g 是1 正则连通紧图当且仅当g 兰k 2 ( 2 ) g 是2 正则连通紧图当且仅当g 兰g ； 关于3 正则紧图，我们有下面的结果t 定理3 1 2 设g 是一个连通3 正则图如果g 是紧的，则g 是h 。“虬 c a y ( z 2 。 1 ，一1 ，7 z 执n 3 或者c a ) ( z 。，z l ， ( l 、o ) 、( 一1 ，o ) ，( o ，州) ，m 2 特 别，p e t e r s e n 图以及盹的线图都是非紧的 定理3 1 4 设g 是c a y l e y 图c a y ( z , 。z 2 ， ( 1 ，0 3 ，( 一l ，o ) ，( o ，1 ) ) ) 则g 是紧的 当且仅当方程c o s ( 百2 kt r ) 一c o s ( 百2 1r r ) = i 没有解，这里0 k 3 则g 是紧的当且仅当 方程( 一妒+ 2 c o s ( 等) = ( 一l ) f + 2c o s ( 等) 没有解，这里os lsm 特别，当 ? t 三2 ( r o o d4 ) 时，g 是非紧的 关于4 正则紧图，我们证明了 定理3 1 1 设g 是4 正则紧图，则g 是虬，l ( 3 凡2 ) 。，硒，3 k 2 ，虬x 凡2 g 1 2 ，这里g i 是上两个定理中的紧图，c a 37 ( 而。历， ( 1 ，o ) ，( 一j ，o ) ，( 0 ，1 ) ( o ， 1 ) ) ) ，c a y ( z 。x 汤， ( 1 ，o ) ，( 一l ，o ) ，( ，l ) ，( 一k ，1 ) ) ) 或c l a y ( 互。 l ，一l ，一 ) ) 这里( ，m ) = 1 ，中的一个定理中图的紧性可看第三章中相应的定理 在最后一节，我们给出了2 种从正则紧图构造非正则紧图的方法 紧图的内容来自w a n g 和l i ( 4 8 和h 9 ) 第二章2 度c a y l e y 有向图的正规性 设f = c a y ( g ，s ) 是非阿贝尔群g 的2 度c a 3 r 时有向图本章主要用讨论 r 的自同构群4 的正规子群的方法去决定r 是否是正规c a 3 ，l e y 有向图设 是4 的一个极小正规子群则n = t l 乃正，这里疋或者同构于磊或 者同构于一个非阿贝尔单群在第2l 节，我们定