（运筹学与控制论专业论文）6p阶小度数cayley有向图的正规性.pdf

北京交通大学硕士学位论文 中文摘要 中文摘要 摘要：给定有限群g ，设s 是g 的不含单位元1 的子集，群g 关于子集s 的c a y l e y 有向图c a y ( g ，s ) 是一个以g 顶点集合，而以 渤5 萝) fg g ，5 曰 为边集合的有向图特别地，若s 。= 5 f ，则x = c a y ( c ，s ) 是无向的此时我们 把一条无向边 “，口) 等同于两条有向边( 虬口) 和( 弘“) 易见，群g 的右正则表示 r ( g ) ，即g 在g 上的右乘作用，为图c a y ( a ，s ) 的全自同构群a u t ( c a y ( g ，s ) ) 的一个子群 c a y l e y ( 有向) 图x = c a y ( a ，s ) 叫做正规的，若r ( g ) 是a u t ( c a y ( g ，s ) ) 的 正规子群c & y l e y ( 有向) 图的正规性对于弧传递图和半传递图的研究非常重要设 p 为素数本文主要研究6 p 阶群上的2 、3 度c a y l e y 有向图的正规性首先，完 全决定了印阶群上的2 度c a y l e y 有向图的正规性，发现了一个新的2 度非正 规c a y l e y 有向图x = c a y ( c ，s ) 且a u t ( x ) 兰r ( a ) d 8 ，其中g = ( qb ，c 0 7 = 泸= c 2 = 1 ，c a c = a 一1 ，b c = c b ，b - 1 a b = 口2 ) ，s 皇 c a b ，西。) 其次， 决定了6 p 阶二面体群上的3 度c a y l e y 有向图的正规性，发现了一个新的3 度 非正规c a y l e y 有向图c a y ( g ，s ) ，其中g = ( 0 ，bn 6 = 萨= 1 ，b a b = a _ 1 ) ， s 岂仙，a ，“4 关键词：c a y l e y 有向图i正规c a y l e y 有向图；自同构群 分类号：0 1 5 7 5 ；0 1 5 2 5 北京交通大学硕十学位论文 a b s t r a c t a b s t r a c t a b s t a c t ：l e tgb eaf i n i t eg r o u p a n dsas u b s e to fgn o tc o n t a i n i n gt h e i d e n t i t ye l e m e n t1 ，t h ec a y l e y & g r a p hc a y ( g ，s ) o ng w i t hr e s p e c tt osi sd e f i n e d a sad i r e c t e dg r a p hw i t hv e r t e xs e tga n de d g es e t 2 ) ，s 兰 n ，a n + l ，x 笺c 2 k 1 ( 这里g 表示长为n 的 有向圈) ； ( 2 ) g = 2 k 历= ( 曲x ( ) ( n 2 ) ，s 垒 ，o u ，x 垒c 2 k l i 设r 是有向图，( “， ) 为它的一有向边我们说u 是( u ，v ) 的尾， 是( ， ) 的 头如果r 有一圈，其上任一点同时为该圈上两个相邻有向边的头或尾，则称此圈 为r 的一个交错圈若r 是两度有向图，u 是它上两相邻有向边的尾( 头) ，那么最 多存在一个交错圈含有这两条有向边；若存在，用o ( u ) ( i ( u ) ) 表示这个交错圈 命题2 1 2 ( 1 3 ，引理2 2 1 ) 设g 为有限群，s = e ，) 是g 的不含单位元的两 元生成子集记x = c a y ( g ，s ) 且a = a u t ( x ) 设q 是a 中固定1 ，e 和，的 子群，则有 ( 1 ) x = c a y ( g ，s ) 正规当且仅当a ：= 1 ( 2 ) 若e 和，中有个阶为2 ，则x = c a y ( a ，s ) 正规 ( 3 ) 若o ( e _ 1 ，) z m 为奇数，则q 至少固定( d ) ( e - 1 ，) 中每点，其中d = ，( e _ 1 ，) 2 学 ( 4 ) 若o ( e - 1 ，) = m 为奇数，且( d ) ( e 1 ，) 或( e - 1 ，) ( d ) ( d = ，( e _ 1 ，) 2 铲) ， 则x = c a y ( g ，s ) 正规 命题2 1 3 ( 【1 3 ，定理2 1 ) 设g 是妒( p 是奇素数) 阶非交换群，s 是g 的二 元生成子集若r = c a y ( a ，s ) 不正规，则有r = c a y ( h ，t ) ，其中h = ( a ，b ，c l a p = 扩= c 2 = 1 ，陋，6 】= 【a ，c 】= l ，c - 1 b c = b - 1 ) ，t 兰 c a ，c b a - 1 进一步，还有 a u t ( c a y ( e 刃) 垒( 历易) 4 命题2 1 4 ( 【1 4 ，定理2 2 1 】) 设g 是卸( p 是奇素数) 阶非交换群，s 是g 的 二元生成子集，则c a y ( g ，s ) 都正规 4 j ! 塞丝盔雯堕主兰笪堡塞 笙三垦塑堕登圭! 星叟翌! 型查塑堕堕垩塑垡 2 主要结论 本节的主要目的是证明下面的定理2 2 1 定理2 2 1 设g 是印( p 为素数) 阶群，s 是g 的不含单位元的二元生成子集 则c a y l e y 有向图x = c a y ( g ，s ) 是正规的，除非下列情形之一发生 ( 1 ) g = z 印= ( 口) ，s 兰 n ，o 印+ 1 ，； ( 2 ) g = z 印z 2 = ( ) x 由，s ! ： n ，n ) ( 3 ) g = ( n ，6 ，c n 3 = 6 3 = c 2 = 1 ，【口，6 】= 陋，c 】= 1 ，c - i b c = b - 1 ) ，s 垒 c n ，c b a 一1 ( 4 ) g = ( ，b ，c i 7 = 6 3 = c 2 = 1 ，c = a 一1 ，6 c = c b ，b - l 曲= a 2 ) ，s 笺 c a b ，c 6 1 证若g 是交换群，则由命题2 1 1 ，可得定理中的情形( 1 ) 和( 2 ) 下设g 是非 交换群当p = 2 时，由命题2 1 4 ，可知x 正规当p = 3 时，由命题2 1 3 ，可得 定理中的情形( 3 ) 下面设p 3 我们来证明定理中的情形( 4 ) 由初等群论知识，可知g 同构于下列群之一： g l ( p ) = ( n ，b ，c i8 p = 6 3 = c 2 = 1 ，0 6 = k ，o c = ，c b c = b - 1 ) ， g 2 ( p ) = ( o ，6 ，c i 矿= 6 3 = c 2 = 1 ，n 6 = b a ，b c = c b ，c n c = a - 1 ) ， g 3 ( p ) = ( c t ，b ，c l 扩= 6 3 一c 2 = 1 ，曲= 乩，口c = c n - 。，c b e = b - 1 ) ， ( ) g 4 ) = ( c t ，b ，c i 扩b 3 c 2 1 ，n c = c a ，b c = c b ，b - a a b = o ) ， g 5 p ) = ( n ，b ，c l 扩= 6 3 = c 2 = 1 ，c c = n ，b c = c b ，b - 1 a b = a r ) ， 其中，产十r + 1 = 0 ( r o o d p ) 容易验证，这5 个群中元素的阶如表l 所示 设a = a u t ( x ) ，a 1 为点1 在a 中的点稳定子群，钟为a 1 的点型稳定s 的 子群设s = e ，) 由命题2 1 2 ( 2 ) ，若e ，中有一个是2 阶元，则x 正规因 此，可设o ( e ) ，o ( y ) 2 若o ( e ) 和o ( f ) 中有一个为3 ，比如设o ( f ) = 3 由表1 知g 不能由3 阶元生 成，故有o ( e ) 3 考虑x 中过点1 的长为3 的有向圈( 1 ，z l ，f 2 f 1 ，f 3 f 2 2 1 = 1 ) ，其 中k = e 或，( 1 i 3 ) 。若e 和，在 f 1 ，1 2 ，f 3 ，中都出现，则由1 3 1 2 l l = 1 可知 e = 厂2 或，= e _ ，导致( 巴，) 交换，从而( e ，) g ，矛盾所以1 l = 1 2 = 如= ， 从而( 1 ，2 ，3 = 1 ) 为x 中过点1 的唯一的长为3 的有向圈这样，a 1 中的元 素必然不动e 和，从而由x 的连通性，可知a i 中的元素也不动x 的每一点， 所以a 1 = 1 ，x 正规 这样下面的证明中总可假设o ( e ) 和o ( y ) 阶都不是2 或3 由表1 知g 不能 全由奇数阶元生成因g = ( e ，) 知，e ，中至少个是2 p 或6 阶元不妨设e 是 偶阶元 5 北京交通大学硕士学位论文第二章印阶群上2 度c a y l e y 有向图的正规性 2 阶元3 阶元6 阶元 p 阶元2 p 阶元 3 p 阶元 g x ( p ) c b 扩 | 。 c o , 2 护矿护 ( 0 曼i 3 1( 0 i 3 ) ( 0 i p )( 0 z p )( 0 z p ) ( 0 sj 3 )( 0 j 3 ) g 2 0 ) 。扩c a 4 护a t l n 。护 ( 0 i p )( 0 i 3 )( 0 i p )( 0 i ( 0 i p ) ( 0 j 3 )( 0 3 ) g a ( p ) c a 4 护扩 | a ， | 护 ( 0 i p )( 0 i 3 ) ( 0 i p )( 0 i p ) ( 0 i 3 ) ( 0 j 3 ) g 4 ( p ) a t 驴4 b jn i c a t | ( 0 i p )( 0 i p )( 0 i ( 0 i p ) ( 0 j 3 )( 0 j 3 ) g 5 0 ) a 护c a b j矿 | ( 0 兰i p )( 0 i p )( 0 i p )( 0 i p ) ( 0 j 3 )( 0 j 3 ) 表1 ：6 p 阶群及其元素的阶 情形1 ：o ( e ) = 2 p 由表1 知，只有g 1 ) 和g 4 ( p ) 存在2 p 阶元故此时g = g 1 ) 或g 4 0 ) 首先令g = g 1 ( p ) ，则e = c a p ( 0 i p ，0 茎j 3 ) 易见，g 1 ( p ) 垡z p x 岛 从而，易知存在a a u t ( g t ( p ) ) ，使得( n 4 ) o = 。，( b ) o = b ，( c 护) o = c 从而e o = 因此不妨设e = 由表1 知 ，的阶可能为2 弘3 p 若o ( f ) = 印，则f = 耐驴，( 0 i p ，0 j 3 ) 显然存在p a u t ( c l p ) ) ， 使，4 = c a b ，则e - i f = a i - l b ，若i = l ( m o d p ) ，则，= c a b ，此时西( e ) n 托( ，) = e 2 ，所以，筲中的元素必然固定x 1 ( e ) 和x l ( i ) ，易证a ：= 1 ，x 正规故可 设i 1 ( r o o dp ) ，此时d ( e 1 ，) = 3 p 由命题2 1 2 ( 3 ) 知川至少固定( d ) ( e - 1 f ) 中每点d ：y ( e - 1 ，) 号 = 甜6 ( n “6 ) 亚乒= 止学业6 学若p t0 + 1 ) ，则 o ( d ) = 印所以l ( d ) ( e 一1 y ) i = 播尝$ 硼= 学= 印，因而g = ( d ) ( e 。，) 所 以硝点型稳定g ，因而x 正规若p l ( i + 1 ) ，则。( d ) = 2 ，同样l ( d ) ( e - 1 川= 船糕瑚= 纽1 = 6 p ，所以q 点型稳定g ，因而x 正规 若o ( f ) = 3 p ，则，= 驴，其中( 3 ，j ) = 1 同上分析，我们可设，= 一6 ，则 e - a f = e b a 1 若i = 1 ( r o o d 力则d ( e _ 1 f ) = 2 ，= n 6 ，此时蜀( e ) = e 2 ，r e = 0 2 ，2 b 。) ，x i ( y ) = ，2 ，e ， = 2 6 2 ，2 耐，且x a ( e 2 ) n x l ( e 1 ) = c a 3 ，a 3 6 ) 而 蜀( e 2 ) nx l ( ，2 ) = 乃，x m ( e 1 ) nx 1 ( y e ) = a ，所以，a ：点型稳定五( e ) ，x l ( y ) 从 而由x 的连通性知a ：= 1 ，x 正规 若i 1 ( r o o d p ) ，则d ( e - 1 ，) = 劫，任取g g ，x 中过g 的交错圈如下 6 j ! 塞窒望盔竺堡主堂垡堡塞笙三童塑堕登圭! 星旦塑! 型互堕堕盟垂塑丝 由上图容易推出，若a i 固定g ，那么也固定( e - 1 f ) p g 从而固定( ( e 1 f ) n ) g 中的每个元素显然雀固定0 ( 1 ) 的每个点，即固定( e - i f ) u e ( e - 1 ，) 中的每个 元素所以a ；固定( ( e - 1 ，) ，) e ( e _ 1 ，) 中的每个点 因此，钟点型稳定( e - i ，) u e ( e _ 1 ，) u ( ( e - 1 f ) p ) e ( e - 1 ，) ，即( c b a i - 1 ) u c a ( c b a i - 1 ) u c b c a ( c b a 1 ) 易见c a ，c b c a = b - l a 不属于( c b a i - 1 ) 且( ) _ 1c b c a ) = c b _ 1 不属于 ( c b a “1 ) ，所以这三个集合恰为( c b & - 1 ) 在g 1 ) 中的三个不同的陪集，这就意味 着硝稳定图x 中所有点，从而a ：= 1 由命题2 1 2 ( 1 ) ，知x 正规 现在设g = g 如) ，则e = 耐，其中( f ，p ) = 1 映射o ：一a ，b 一6 ，c c 诱导出国( p ) 的一个自同构，且矿= c a ，不妨设e = c a 由表1 ，知，的阶一定 为6 ，此时f = c b i ( 0 s i p ，j = 士1 ) 通过计算可得： x 1 ( e ) = x 1 ( ) = a 2 ，t g a ”+ 1 ， 蜀( ，) = x l ( c a 4 护) = t p a ”“，b 2 ：a 。 x 2 ( a 2 ) =a 4 ，n a 一+ 3 ，n a 。一十一十2 ，b 2 j a 一。+ 2 ) x 2 ( 护n 。+ 1 ) = b j a 。r j + 2 一+ 1 ，6 巧n 一+ 一+ 1 ，b 2 j a 7 2 一。+ 1 ，n ) 恐( 护。一+ 。r j ) = b j a 孙+ t r ，6 幻。一+ 2 一，b 2 , a 一1 一，a r j x 2 ( b 2 j a 一) = b 2 j a 打却一，a r 句，一，n ) 若r 2 ，4 ，则恐( 0 2 ) ，x 2 ( b i a i r + 1 ) ，兄( n 一+ 纠) ，x 2 ( b 2 i a - ) 中仅有恐( + 1 ) n x 2 ( b v a “) = a ，而其余集合两两交为空，因此q 点型稳定蜀( e ) 和墨( ，) ，从 而a - 1 ，得x 正规 若r = 2 或4 ，则必有p = 7 当r = 2 ，j = 1 或r = 4 ，= - 1 时， 恐( o r j + i r ) n x d e ) = 口2 ) ，而恐( 印0 - ) n x i ( e ) = 咖所以a ：固定制，舻8 一，a 2 ， 继而点型稳定咒( e ) ，x 1 ( ，) 所以a i = 1 ，x 正规同样若r = 4 ，j = 1 或 r = 2 ，j = 一1 时，有x 2 ( b 2 j a 一) n x l ( e ) = a 2 ) ，而x 2 ( 护a 一+ 一) n x l ( e ) = ，意 味着a ：= 1 ，从而x 正规 情形2 ：o ( e ) = 6 由表1 知，只有g 2 ，g 4 p ) 和g 5 有6 阶元故此时g = g 2 ，g 4 或g 5 如) 首先令g = g 2 ，则e = 耐, j ( 0 i p ，j = - , - i ) 显然，映射n ：a a ， 7 北京交通大学硕士学位论文第二章6 p 阶群上2 度c a y l e y 有向图的正规性 护一b ，2 一c 诱导出g = g 2 ( p ) 的一个自同构且矿= 西，故可令e = c b 故 o ( f ) = 6 ，p 或劬 若o ( f ) = 6 ，则令，= c a 。护( 0 i p ，j = 土1 ) 易见映射：0 2 一，b b ， c c 诱导出g = g 2 ( p ) 的一个自同构，且e 口= e = c 6 ，口= c a b 3 若j = 1 ，则 ，= c a b ，此时，x l ( e ) = x l ( c b ) = b ，a - l b 。1 ) ，x l ( ，) = x l ( c a b ) = 6 ，a b _ 1 ， 因此，x l ( e ) n x l ( y ) = 6 。) ，易知a ；= 1 ，x 正规若j = 一1 ，则，= c a b ， 此时，x l ( e ) = x l i ( 西) = 6 ，a - 1 ，x l ( y ) = x l ( c a b - 1 ) = 6 ，n ) ，x 2 ( b - 1 ) = 。1 b ，b ，a b ，1 ) ，恐( o 。) = a 。6 ，o ，a - l b ，1 ) 因为局( 6 。) n x l ( y ) = 6 ) ， 恐( 。- 1 ) n x l ( ，) = ，所以a ：固定点b ，n ，b 这样a ：= 1 ，x 正规 若o ( ) = p ，则令，= 矿( o i p ) ，易见映射p ：hn ，b 一6 ，c c 诱导出g = g 2 0 ) 的一个自同构，且扩= e ，“= n 因而可令，= n 设 ( 1 ，l i ，1 2 l x ，z p 0 1 1 2 z l = 1 ) 为x 中过点1 的长为p 的有向圈，其中以= e 或 ，( 1 isp ) 断言对任意l i p ，都有l = f 否则，假设e 在知知一1 1 2 1 1 中出现m ( o m p ) 次注意到b 在g 2 p ) 的中心里以及c = 可得 1 = 知知一1 1 2 l l = 护n ，其中t = 0 ，s = 士1 从而扩= 1 ，b m = 1 且 j = x 口一m = 1 所以pi 如由o ( c ) = 2 ，知m 为偶数，所以p m 为奇数，导致 j = l 口一t n 0 i 屯l p ，矛盾因此断言成立，即l = f ( 1 i p ) 从而( 1 ，2 ， j = l ，= 1 ) 为x 中过点1 的仅有的长为p 的有向圈这样，a l 中的元素必然不动e 和，从而由x 的连通性，可知a ，中的元素也不动x 的每一点，所以a 1 = 1 这说明x 正规 若o ( f ) = 劬，令，= o 锣( 0 i p ，j = 1 或一1 ) 因n 一一一b ，c c 诱导出g 2 p ) 的自同构，可设，= a b 或n 6 当，= a b 时，五( e ) = e 2 ，f e = 6 2 ，m - 1 6 2 ) ，( ，) = ，2 ，e l = n 2 b 2 ，c 0 6 2 ) 因为x 1 ( e ) n x l ( e 2 ) = n ，c ，而x l ( e f ) n x l ( y e ) = 庐，x x ( e 2 ) n x l ( f 2 ) = ， 所以a ：固定x l ( e ) 和x l ( f ) 中每点由x 的连通性容易推出a ：= 1 ，x 正规 当，= n 6 。时，设( 1 ，z 1 ，1 2 1 1 ，1 6 1 5 纠1 = 1 ) 为x 中过点1 的长为6 的 有向圈，其中l = e 或( 1 i 6 ) 若不全为e ，则由b 在g 2 0 ) 的中心里以及 1 6 f 5 1 2 1 l = l ，可得f 6 f 5 f 2 z l 中e ，出现的次数皆为3 因此，c 3 a 6 - + 如+ 如= 1 ， 其中文= 4 - 1 ( 1 3 ) 从而c 3 = 1 ，矛盾因此，= e ( 1si p ) 进一步， ( 1 ，e ，e 2 ，e 6 = 1 ) 为x 中过点1 的唯一的长为6 的有向圈这样，a 1 中的元素 必然不动e 和，从而由x 的连通性，可知a l 中的元素也不动x 的每一点，所 以a l = 1 这说明x 正规 现在令g = g 4 ) 由表1 ，可令e = 甜驴( 0 i a ，= 4 - 1 ) 若i = 0 ，则 8 些塞窒塑盔兰蚌学位论整 第二章6 p 阶群上2 度c a y l e y 有向图的正规性 e = c b 或c 6 若i 0 易见映射o ：a i ha ，b hb ，c c 诱导出g = g 4 ( p ) 的 一个自同构，且矿= c a b j 这样e = c a b 或c a b 进步，aho ，bhn 6 ，ch c 以及a a ，b b a ，a a 诱导出g 的自同构，从而可设e = c b 或c 6 由此 可见，我们总可设e = 秽，= 士1 由表l ，知o ( f ) = 6 或p 若o ( f ) = 6 ，则，= c a 。护( 0 i p ，j = i l ) 显然映射a ：a 4 一a ，b 卜 b ，c c 诱导出g = ( 力的一个自同构，使得广= 护故可设f = c a t p 注意 e = 西2 ( k = 士1 ) ，则 x 1 ( e ) = x l ( c b ) = b 2 ，+ “) x 1 ( ，) = x l ( c a b j ) = “a r ，b 2 j a _ 1 ) x l ( b 2 ) = c ，c b j + 2 k a 一“ x i ( 驴+ ) = c b j + 2 a r $ ，c 6 2 j + ( t r 2 ，+ 一+ x 1 ( 驴+ ( ) = c 驴+ 2 后。一，c 6 2 j + 0 7 卸+ + r j x 1 ( b 2 3 a 4 ) = c ，西+ n 一1 蜀( 渺) ，x l ( 驴+ a r j “) ，托( 驴+ n 一) ，x 1 ( b 2 j a 一1 ) 中，仅有x l ( b 2 k ) nx 1 ( b 2 j a 一1 ) = c ，而其余两两交都是空集所以，a ：点型稳定x ，( e ) ，x l ( ，) 从而a ：= 1 ，x 正 规 若o ( f ) = p ，令f = a 4 ( 0 i p ) 存在a 4 ( p ) 自同构卢使得，4 = a 故设 f = o 注意e = c 泸( 一士1 ) 则有 x l ( e ) = x 1 ( 舻) 一 渺，c b k a 一 x ( ，) = x l ( a ) = n ，a 2 为( 榉) = 泸，c a ，c d t 2 k ，b 2 n 2 r 2 。 恐( 毋矿) = c a r ，6 2 口，b 2 k a 2 ，c b a 3 r x z ( c 妒a ) = c a ，b z 0 1 + 一，b z 1 + r ，c b 1 + 矿) ( 2 ) = 舻n 2 ，舻a 2 栅，舻n 3 ，a 4 ) 容易验证兄( 萨) ，咒( 舻n r k ) ，x z ( c 驴a ) ，恐( n 2 ) 中仅有x 2 ( g ) n 咒( 舻n ) = m ) 其余集合两两交皆为空，因此，雒点型稳定x 1 ( e ) ，蜀( ，) ，a ：= 1 ，x 正规 最后设g = g 5 p ) ，此时，由表1 ，知e = 耐( 0 s i p ，j = 士1 ) 若i = 0 ， e = 曲或西若i 0 易见映射o ：a i a ，b b ，c c 诱导出g = g 5 ( p ) 的一个自同构，且e “= c 棚0 = 士1 ) 可设e = c a b 或c a b - 这掸共有四种情形： e = c b ，c b 一。，c a b 或c a b - 1 由表1 ，知o ( s ) = 6 或p 设o f f ) = 6 ，则，= c a i 护( 0 i p ，j = 士1 ) 以下分别考虑e 一 9 北京交通大学硕士学位论文第二章6 p 阶群上2 度c a y l e y 有向图的正规性 c a b j ，c b j ，c a b l 和c 6 一j ，若e = c a b 3 ，则 x a ( e ) = x l ( c a t 一) = 6 幻n 一卸+ 一，b 2 j a 一。幻+ 一) x l ( ，) = x l ( 耐护) = 护。一7 4 + ，护n “枷+ i r j x 1 ( b 2 j a 一7 幻+ 一) = c a l 一2 j + ，c a 4 一r 2 j + 一) x 1 ( b 2 j a 一7 2 j + 一) =c a l + r j 一。7 2 j ，c a 一7 卸+ 一) x l ( b 幻a 一习+ i r j ) =c a 衙却“r j = c a l + r j 州卸，c a l 一卸+ 一) x 1 ( 6 巧n 一7 句+ 一) = c 。1 一r 2 j + 4 一，c a 一卸+ ”。 注意到i 1 ，容易验证托( 护n 一7 4 + r j ) ，x 1 ( b 2 j a 一删州) ，x l ( b 2 j a - - r 2 j + i ”) ，x 1 ( b 2 j a 一4 一+ ”) 中仅有x 1 ( b 2 ：a - i r 2 3 州) n x l ( b v a 一7 4 + ”) = c a “r j - i t 2 j ，其余集合两两交为空因 此，钟点型稳定x l ( e ) 和五( ，) ，雀= 1 ，x 正规 若e = c 驴，则i 0 ，此时存在g 5 0 ) 的自同构p ：a ha ，b b ，c c 这样 f 4 = ( c a 和) 4 = c a l p ，从而可设s = c a b j ，c 护) ，只需将上面做法，= c a b b y 中的i 取为0 ，即可得到同样的结论x 正规， 若e = c a b - ，则 x l ( e ) = x 1 ( c a b 一) = a 。”“，b j a p 。 x 1 ( ，) = x lc a ) = b - o 一打幻+ 一，a 一1 + 。一) x 2 ( a 一件7 卸) = b - j a 一。句+ 一一十2 ，a i r j - z + 2 一1 ，0 2 印一2 ，一一+ 2 r 2 一， x 2 ( b j a f 。= - 一) = a - i + i r 2 j + r 2 j 一一，护n t r 卸+ r 幻一2 一，护。一。r j + 1 + 句一一，6 一，0 1 一一) x 2 ( 6 3 a = s t 2 + 1 r j ) = 护n 川7 勘，6 一j n 一7 2 + t t 一+ 2 一，6 一j n 一一2 7 卸+ 2 r j ，o r j 一1 叫2 + 2 一) x 2 ( a 一1 + r j ) = 6 3 a - $ 2 3 + 2 一1 ，a 2 z r - 2n r 2 - - l - - z + 2 一，护n 一一+ r 2 1 + 4 一， 注意到i r 2 ：，否则e = ，容易验证当p 7 且r j 2 ，4 时，恐( 。- - i + r 2 ) ， 恐( 驴。冲。) ，恐( 6 3 a “p 制) ，( n - 1 “) 中仅有尼( 口1 ”) n 托( n - 1 + ”) = n 纠“+ r 2 j _ 1 ，其余集合两两交为空因此，雀点型稳定x 1 ( e ) 和x t ( ，) ，a ；= 1 ， x 正规 若e = c 矿j ，贝4 存在g 5 的自同构卢，使得尸= ( 甜) 4 = 驴此时可设 s = c 凸驴，c b j ) ，若p 7 且一2 ，4 时，只需将上面做法f = c a i 驴中的i 取为 0 ，即可得到x 正规 以下设p = 7 注意到g 5 与r 的选择无关，故可设g 5 ( 7 ) = ( a ，b ，cja 7 = 泸= c 2 = 1 ，c a c = n 一，c b c = b ，b - 1 0 h = n 2 ) 若e = c a b 一，则s = c a b 一，c 矿驴 ， 其中0 i p ，j = 士1 ，s = g s ( 7 ) 若e = c b 一，则s = c b - j ，耐驴 ，对于 i 0 ，那么a i ha ，b hb ，c c 诱导出g 5 ( 7 ) 的自同构，故可设s = c a b ，c a b _ 1 ) 或 c b ，c a b _ 1 由( s ) = g 5 ( 7 ) 知i 2 这样s 有7 种可能：s ：f = c a b ，c a b - 1 ) ( o i 7 且i 2 ) ，岛= e b ，c a b - 1 容易验证aha 2 ，bh0 5 6 ，chc a 和 a o ，b 0 2 6 ，c c a - 1 分别诱导出g 5 ( 7 ) 的自同构，分别记为p 和7 通过简 北京交通盔塑士学位论文 第二章印阶群上2 度c a y l e y 有向图的正规性 单计算得：爵= 昆，霹= s - ，篱= s 4 ，田= s 6 ，鳄= c 6 - 1 ，c a e 叮，霹= 岛因为 c b ，c a 6 6 ，呈s 0 ，故可设s = c a b ，c b 。 设x = c a y ( g ， c a b ，曲- 1 ) ) 取6 = ( n ，6 2 ) ( 3 ，6 n 6 ) ( “4 ，b a 2 ) ( 0 5 ，b a 4 ) ( n 6 ，b ) ( b a ，b 2 a 3 ) ( 6 驴，6 2 n 4 ) ( 6 2 n ，b 2 泸) ( c ，c 蚰) ( ，c b a 3 ) ( c 舻，c b a 6 ) ( 甜，c b 2 a 5 ) ( c n 6 ，c b a 5 ) ( c 6 ，c b 2 a ) ( c b a 4 ，c b 2 2 ) ( c 铲4 ，c 6 2 驴) 且d 点型稳定 1 ，c b a 2 = e ，c b 2 = ，b 2 “5 = e 2 ，2 ，c a 5 ，c 酽扩，6 2 2 ，6 扩，c a 3 通过计算可以验证6 满足( 凰( ”) ) 6 = x l ( ) ，v ( x ) ( 亦可通过下图验证注 意v ( x ) = 矿( x 1 ) = y ( x 2 ) ，e ( x ) = e ( x 1 ) u e ( x 2 ) ) 由此可以得出1 j 4 ；， 所以x 非正规 图x l 图如 若o ( f ) = p ，则，= n ( 0 k p ) 注意e = c a b j ( i = 0 ，1 ，j = 士1 ) 设( 1 ， 如，1 2 l l ，f 6 f 5 易f l = 1 ) 为x 中过点1 的长为6 的有向固，其中i t = 或， ( 1 ts6 ) 设e 出现的次数为m 由= c a ，b c = 曲以及o ( c ) = 2 知，2 1 - * 同样由西= b c ，a b = w ，o ( b ) = 3 知，3 i m 所以6 | m 因为o ( f ) = p ，过点1 的 有向6 圈中必含e ，所以e 的个数为m = 6 因此，“= e ( 1st 6 ) 进一步， ( 1 ，8 ，e 2 ，e 6 = 1 ) 为x 中过点1 的唯一的长为6 的有向圈这样，a l 中的元索 必然不动e 和，从而由x 的连通性，可知a l 中的元素也不动x 的每一点，所 以a 1 = 1 这说明x 正规 口 j ! 塞塑盔兰塑堂焦堡塞 蔓三童塑堕登占! 鏖g 塑l 旦查鱼堕塑垩塑焦 注记：在定理2 2 1 中我们发现了一个新的非正规两度c a y l e y 有向图x = ca y ( c ， e ，厂 ) ，其中g = ( a ，b ，ca 7 = b 3 = c 2 = 1 ，c a c = a ，b c = c 6 ，b - 1 a b = 护) ， e = c a b ，= c b 下面计算x 的全自同构群为a u t ( x ) 兰n ( c ) d 8 设 a = a u t ( x ) ，只需说明a 1 竺d s ，其中a 1 是1 在a 中的点稳定化予因为定理 2 2l 证明中的 固定2 - 弧( 1 ，e ，e 2 ) ，可得l a l i28 容易计算恐( e 3 ) = x 3 ( c a 6 ) = 1 ，b a ，b a 2 ，b 2 a 4 ，b 2 a 2 ，a 6 ，b 2 ，b a 5 ，所以x 中过3 弧( 1 ，e ，e 2 ，e 3 ) 的6 _ 圈的只有一 个，即( 1 ，e ，e 2 ，e 3 ，e 4 ，e 5 ) 这说明固定3 - 弧( 1 ，e ，e 2 ，e 3 ) 的x 自同构只有单位，从而 f a i = 8 取a = ( o ，6 4 ) ( n 2 ，6 ) ( 0 3 ，b a 2 ) ( n 4 ，b a 5 ) ( a 6 ，b 2 a s ) ( b a 3 ，b 2 a 2 ) ( 比6 ，b 2 a ) ( b 2 a 4 ，b 2 a 6 ) ( c ，c b a 4 ) ( c 0 2 ，c b 2 a 3 ) ( c 0 4 ，c b a 3 ) ( c a 5 ，c b a 6 ) ( c n 6 ，c b a ) ( c b a 2 ，c b 2 ) ( c b a 5 ，c b 2 a 6 ) ( c 6 2 0 2 ，c b 2 a 4 ) 且a 点型稳定 l ，c b 2 a ，c 6 ，0 5 ，b 2 ，c b ：a 5 ，c a ，b a ，b 2 a 3 ，c a 3 可以验证a 满足( x 1 ( ) ) 1 = x 1 ( u 1 ) ( v v y ) ) ，所以a a 1 注意到定理2 2 1 中6 和上面的a 是互不交换 的2 阶元，故a 1 是8 阶非交换群又因为8 阶非交换群只有二面体群d s 和四元 数群q 8 ，而后者只有一个2 阶元，从而a 1 兰d s 北京交通大学硕士学位论文第三章印阶二面体群上3 度c a y l e y 有向图的正规性 第三章6 p 阶二面体群上3 度c a y l e y 有向图的正规性 1 预备知识 本章主要决定印阶二面体群上3 度c a y l e y 有向图的正规性 命题3 1 1 ( 1 0 ，定理1 1 1 ) 设g 是交换群，x = c a y ( a ，s ) 若s 满足以下条件 ( + ) ，则x 正规： ( ) 若。，y ，z ，u s ，且1 z y = z u ，贝4 z ，) = 2 ，“) 命题3 1 2 ( 1 6 ，引理6 1 ) 令x = c a y ( c ，s ) ，若坳h u t ( x ) 1 ，妒点型稳定 x 1 ( 1 ) ，则h u t ( x ) 1 = 1 命题3 1 3 ( 1 6 ，引理3 】) 令x = c a y ( g ，s ) ，z s 令y = c a y ( c ，s z ) ) ，若 如a u t ( x ) l ，= z ，则a u t ( x ) l a u t ( y ) 1 2 主要结论 本节中p 总表达一个素数由z h a n g 等【17 】可得到印阶二面体群上三度无向 c a y l e y 图的正规性，本节主要目的是证明下面的定理3 2 1 定理3 2 1 设g 是劬阶二面体群，g = ( a ，b a 3 p = 6 2 = 1 ，b - 1 a b = a - 1 ) ，s 是 g 的不含单位元的三元生成子集，且s - 1 s 令x = c a y ( g ，s ) 则x 非正规 当且仅当：g = ( a ，bia 6 = 护= 1 ，b - 1 n 6 = a - 1 ) ，s 垒 6 ，o ，一 证若p = 2 ，则g = ( o ，bla 6 = 6 2 = 1 ，b - l 曲= a - 1 因为g = ( s ) ，所以s 中 必存在2 阶元附( 0s is 5 ) ，因为耐在i u t ( g ) 下共轭，故总可设为b 因为 s s ，s 中含一个或两个2 阶元 若s 中只有一个2 阶元，则s 竺 6 ，a i ， 因为( ，) = ( a ) ，所以n l ，中 至少有个6 阶元，不妨设为6 阶元故映射：一吼b b 诱导出h u t ( g ) 的一个自同构，则s 垒 6 t 叱a k ，( = 2 ，4 ) 当k = 2 时，s = 6 ，a ，a 2 ) x l ( 1 ) 诱导出的子图由一个孤立点b 和一条有向边( a ，a 2 ) 组成，所以a n t ( x ) l 点型稳 定x l ( 1 ) 由命题3 1 2 知a u t ( x ) 1 = 1 ，x 正规当k = 4 ，s = 6 ，一 取 n = ( 2 ，a - 1 ) ( 6 n 2 ，b a 。) 且o t 固定x 中其它点，容易验证o t h u t ( x ) l ，显然n 不属于h u t ( g ) 所以，x 非正规 若s 中有两个2 阶元，则有两种情况：( 1 ) s 望 6 1 耐， ；( 2 ) s 望 6 ，a 3 ， 对于情况( 1 ) 考虑的阶，若为2 阶元，则s 竺 6 b a 3 ，a k 映射a o ，b b 诱导出群g 的个自同构，因而在等价的意义下= 1 ，2 因为边( 1 ，6 ) ， ( 1 ，b a 3 ) 无向，边( 1 ，a k ) 有向，所以v 妒a u t ( x ) l ，( o p = 口所以i 以1 胆：i 2 北京交通大学硕士学位论文第三章6 p 阶二面体群上3 度c a y l e y 有向幽正塑堡 下证a ：= 1 x 1 ( 6 ) = 1 ，3 ，b a ) ，x l ( h a 3 ) = l ，n 3 ，6 “3 因为边( b ，矿) 无向， 边( b ，施“) 有向，边( 妇3 ，她3 “) 有向，所以w 川，6 点型稳定x l ( b ) 和x - ( 6 n 3 ) x 1 ( ) = 舻，b a 3 + ，0 2 因为边( ，b a ) 和( n ，6 n 3 + 。) 无向，边( 矿，8 驰) 有向， 所以d 固定点“因为x 1 ( h a ) = 扩，扩，6 ) ，x 1 ( b 3 + ) = n 3 + 。，扩，k 3 ，所 以b 属于x 1 ( 6 扩) ，b 不属于x l ( h a 3 + k ) ，因而j 固定点6 0 ，她3 ”，继而点型固定 x l ( 扩) 由d 的任意性知，a j = 1 ，所以i a - i 2 ，x 正规 若矿为3 阶元，则易知在等价的意义下s 竺 6 ，b a 2 ，n ，因为边( 1 ，6 ) ，( 1 ，b a 2 ) 无向，边( 1 ，。) 有向，所以v 妒a u t (