群與圖的對(duì)稱性

王佳利，王改霞，鄭祥

（安徽工業(yè)大學(xué)數(shù)理科學(xué)與工程學(xué)院，安徽 馬鞍山243002）

群與圖的對(duì)稱性

王佳利，王改霞，鄭祥

（安徽工業(yè)大學(xué)數(shù)理科學(xué)與工程學(xué)院，安徽 馬鞍山243002）

首先對(duì)平面圖形的對(duì)稱進(jìn)行分析和利用其對(duì)稱群進(jìn)行量化，進(jìn)而將此推廣到考察一般圖的廣義“對(duì)稱性”與圖自同構(gòu)群的關(guān)系，最后刻畫了無平方因子階局部本原弧傳遞圖的自同構(gòu)群結(jié)構(gòu).

Cayley圖；置換群；局部本原群

1 引言

對(duì)稱性是自然界很普遍也很重要的特性，自然界中幾乎所有重要的規(guī)律均與某種對(duì)稱性有關(guān).要給對(duì)稱這一概念精確的和一般的描述，特別是對(duì)稱性在量上的計(jì)算，需要利用群論這個(gè)工具.群是數(shù)學(xué)中基本概念之一，群論自19世紀(jì)Galois創(chuàng)立以來，不僅成為了近世代數(shù)的重要分支，而且其應(yīng)用范圍已深入到科學(xué)技術(shù)的眾多領(lǐng)域，甚至是自然科學(xué)的物理、化學(xué)、生物的研究中，群論也成為強(qiáng)有力地必不可少的工具.眾所周知，關(guān)于平面圖形的對(duì)稱性，圓比正方形更對(duì)稱些；正六邊形比正三角形更對(duì)稱些；正三角形比等腰三角形更對(duì)稱些等.這些都是直觀感性認(rèn)識(shí).如何去刻畫對(duì)稱性的強(qiáng)弱呢？也就是如何給對(duì)稱性加以量化？

用運(yùn)動(dòng)的觀點(diǎn)去看對(duì)稱，可以把平面圖形的對(duì)稱中用到的運(yùn)動(dòng)分為三類：反射（軸對(duì)稱）、旋轉(zhuǎn)（n次中心對(duì)稱）和平移（平移對(duì)稱）.這些運(yùn)動(dòng)共同的特點(diǎn)是，都保持平面上任意兩點(diǎn)間的距離不變.從而把反射、旋轉(zhuǎn)、平移，或者它們的相繼實(shí)施，統(tǒng)稱為“保距變換”.由上述觀點(diǎn)自然的延伸，就可以想到描述平面圖形對(duì)稱性強(qiáng)弱的一種量化的方法.這就是把所有使某平面圖形K不變的“運(yùn)動(dòng)”放在一起，構(gòu)成一個(gè)集合，記為S（K）并稱其為K的對(duì)稱集.這樣就很容易根據(jù)S（K）中所含元素個(gè)數(shù)來進(jìn)行量化對(duì)稱性.把保持不變的運(yùn)動(dòng)放到一起，構(gòu)成一個(gè)集合，稱之為“對(duì)稱集”，用它來描述的對(duì)稱性.這個(gè)“對(duì)稱集”不僅僅是一個(gè)集合，在這個(gè)集合上我們還定義了“保距變換”，并且這種變化還滿足一定的運(yùn)算律，進(jìn)而構(gòu)成了一個(gè)群.

本文把圖形的“對(duì)稱性”概念加以推廣，即一般圖形的“點(diǎn)傳遞性”、“邊傳遞性”和“弧傳遞”等廣義的對(duì)稱概念，討論它們的“對(duì)稱性強(qiáng)弱”，也就是討論圖的自同構(gòu)群在圖上的作用是否“對(duì)稱”.

2 群與圖的對(duì)稱性的聯(lián)系

群與圖是人們一直關(guān)注的兩個(gè)基本數(shù)學(xué)對(duì)象，各自都有一個(gè)龐大的理論體系，但二者結(jié)合起來成為一個(gè)新的數(shù)學(xué)領(lǐng)域則是從上個(gè)世紀(jì)三四十年代開始的.從已知的研究結(jié)果可以看出，群論方法在具有較高對(duì)稱性圖的研究中的重要意義確實(shí)是其他方法所不能比擬的.圖的對(duì)稱性研究或者說研究某種具有對(duì)稱性質(zhì)的圖具有重要的理論意義［1-3］.一方面，許多有趣的著名的圖都具有某種對(duì)稱性質(zhì)，另一方面，對(duì)稱圖與數(shù)學(xué)的很多方向都有密切的內(nèi)在聯(lián)系.

下面用兩個(gè)例子闡述下群與圖對(duì)稱性之間的聯(lián)系，即利用圖的對(duì)稱來構(gòu)造其自同構(gòu)群以及利用特定群來構(gòu)造具有某種性質(zhì)的圖類.

2.1利用圖的對(duì)稱性構(gòu)造群

例2.1設(shè)X=（V，E）為一個(gè)4個(gè)頂點(diǎn)4條邊的圖，其中

其圖示如圖1.

圖1 四個(gè)點(diǎn)四條邊的圖

根據(jù)平面圖形的對(duì)稱性，很容易知道圖X有且只有4個(gè)軸對(duì)稱和4個(gè)中心對(duì)稱，它們構(gòu)成了圖自同構(gòu)群的所有元素，即

2.2利用群論來構(gòu)造具有某種對(duì)稱性的圖

Cayley圖是由A.Cayley在1878年提出的，當(dāng)時(shí)是為了解釋群的生成元和定義關(guān)系.但由于它構(gòu)造的簡(jiǎn)單性、高度的對(duì)稱性和品種的多樣性，越來越受到圖論學(xué)者的重視，成為群與圖的一個(gè)重要的研究領(lǐng)域.近年來，由于計(jì)算機(jī)的發(fā)展，人們發(fā)現(xiàn)Cayley圖還是構(gòu)造與設(shè)計(jì)互連網(wǎng)絡(luò)的很好地?cái)?shù)學(xué)模型，因而又獲得了實(shí)際的應(yīng)用，它的重要性日益增加.

例2.2令Z3為剩余類加群，S=｛1，2｝為其子集.其所對(duì)應(yīng)的Cayley圖圖示如下（與圖1同構(gòu)）：

圖2 群的Cayley圖表示

3 無平方因子階局部本原圖的對(duì)稱性

給定一個(gè)圖Γ，用V，E和Arc（Γ）分別表示圖Γ的點(diǎn)集、邊集和弧集，其中點(diǎn)集的勢(shì)稱作圖Γ的階.設(shè)G≤Aut（Γ），若G傳遞地作用在點(diǎn)集V、邊集E或者弧集Arc（Γ）上，則稱圖Γ分別是G-點(diǎn)傳遞的、G-邊傳遞的或者G-弧傳遞的.稱圖Γ為局部本原圖，如果AutΓ的點(diǎn)穩(wěn)定子在任何一個(gè)點(diǎn)鄰域上是本原的.本文所指的圖均為有限簡(jiǎn)單連通無向圖，未加說明的概念和術(shù)語參見文獻(xiàn)［4-5］.

從已有文獻(xiàn)來看，在圖的對(duì)稱性研究中，無平方因子階的對(duì)稱圖的刻畫和分類已經(jīng)引起了廣泛關(guān)注.對(duì)于素因子較少的特殊情況已經(jīng)得到了很好的刻畫和分類［6-11］.關(guān)于一般情況下無平方因子階圖的對(duì)稱性方面也有一些有意義的結(jié)果［12-16］.特別值得指出的是，文獻(xiàn)［1，5］中給出了無平方因子次數(shù)的本原置換群的分類結(jié)果，這個(gè)結(jié)果給研究無平方因子階的圖提供了一個(gè)很有力的工具.本文下面的定理給出了一個(gè)無平方因子階局部弧傳遞圖及其自同構(gòu)群的簡(jiǎn)單刻畫.

定理3.1設(shè)Γ是無平方因子階連通k（k/=3）正則G局部本原圖，設(shè)M是作用在V上至少有三個(gè)軌道的最大正規(guī)子群且ΓM不是星圖，則

（2）Γ是一個(gè)奇素?cái)?shù)度的二部圖，且G同構(gòu)于D2n：Zk，Zn：Zk，或者（其中k是nk的最小素因子）；

（3）G=M：X，其中soc（X）=T、MT=M×T，且T在V上至多有兩個(gè)軌道，Γ是T-邊傳遞圖.

證明 由于ΓM不是星圖，Γ是ΓM的正規(guī)覆蓋，從而正規(guī)子群M在頂點(diǎn)集合V上作用正則.根據(jù)M的選擇可知，商群G/M在ΓM上作用忠實(shí)或者在V ΓM的一個(gè)軌道上作用正則，從而存在一個(gè)G的一個(gè)子群X使得G=M：X.又因?yàn)棣是G/M局部本原圖，所以二元序?qū)Γ℅/M，ΓM）滿足G/M的任何一個(gè)非平凡的正規(guī)子群在ΓM的頂點(diǎn)集至多有兩個(gè)軌道，從而令Y=soc（X）是X的一個(gè)極小正規(guī)子群.如果Y=T是不可交換單群，且G/CG（M）是可解的，所以Y≤CG（M），從而MY=M×Y，定理中（3）成立.

下面分下述兩種情況來證明定理的前兩部分.

情形1Γ≌Kk，k且Y≌T2（T是單群）.

在這種情況下，Y在ΓM的邊集上作用傳遞，從而Y在ΓM上恰好有兩個(gè)長(zhǎng)度為k的軌道，即MY在V上恰好有兩個(gè)長(zhǎng)度為k|M|的軌道.如果Y在ΓM上的每個(gè)部分中作用忠實(shí)，則T≌A7，k=105，且Tδ≌A6×PSL（3，2），此時(shí)很顯然ΓM不是X局部傳遞的.

假設(shè)Y在其中一個(gè)軌道上作用不忠實(shí)，不妨設(shè)為UM，令K為Y在ΓM上的核.如果X在VM上作用不傳遞，則MK/M包含在G/M的一個(gè)正規(guī)子群中，該正規(guī)子群在VM至少有三個(gè)軌道.從而G有一個(gè)真包含M正規(guī)子群且在V上至少有三個(gè)軌道，與M的選擇矛盾.從而X在VM上作用傳遞，且Γ是G-弧傳遞的.很容易證明K≌T在ΓM的另一個(gè)分支上傳遞，令U是UM的MY-軌道.

如果T是非交換單群，因?yàn)镸K/CMK（M）同構(gòu)于Aut（M）的一個(gè)子群，且是可解的，從

而

且

.令?是包含U的M軌道，根據(jù)MK在?上的作用，可知K在?上作用是平凡的.故K在VM上作用傳遞，從而ΓKk，k，M=1，Γ是G弧傳遞的且G只有一個(gè)極小正規(guī)子群.定理3.1中（1）成立.

假設(shè)T≌Zp（p為奇素?cái)?shù)），則k=p與|M|互素，且Aut（ΓM）=（Sp×Sp）：Z2.從而G的Sylow p子群的階為p2.因?yàn)閨M|為無平方因子數(shù)，所以O(shè)ut（M）可解.因?yàn)閅≌Z2p是X≌G/M的一個(gè)極小正規(guī)子群，所以G/M是不可交換的.故MMCG（M）.

根據(jù)M的選擇性，可得MCG（M）在V上至多有兩個(gè)軌道.即p是|MCG（M）|的一個(gè)因子，也是|CG（M）|的一個(gè)因子.從而

即

又因?yàn)镸Y和M是G的正規(guī)子群，從而CMY（M）是G的正規(guī)子群.令P是CMY（M）的Sylow p子群，則CMY（M）=M×P是G的正規(guī)子群，從而P是G的正規(guī)子群.又由P≤Y，故P=Y.定理3.1中（1）成立.

情形2soc（G/M）≌soc（X）=Y≌Zp，則|VM|=p或者|VM|=2p.

假設(shè)CX（Y）=Y，則G=L：Zl，其中l(wèi)|p-1.所以Gα≌X?≌Zl或者α∈V，?是M軌道，則X?在?的鄰域上作用正則.由于ΓM是X局部本原的，從而|Gα|=k是個(gè)奇素?cái)?shù).若G在V上作用不傳遞，則Gα≌Zk且G≌L：Zk.令q是|L|的素因子滿足L的Sylow q子群非正規(guī)或者q是|L|的最小素因子，則L有唯一的q′Hall子群N.則N是G的正規(guī)子群且N不傳遞.從而|ΓN|=2q，Γ是ΓN的一個(gè)正規(guī)覆蓋，所以q≥k.如果q＞k，令Q為L(zhǎng)的Sylow q子群，有Q≤NCG（N）且NCG（N）=N×Q=L與Q是L的正規(guī)子群矛盾.所以q=k.又由于k是|G|的最小素因子，故L≌Zn或者：Zk，即G≌Zn：Zk或假設(shè)G在V上作用傳遞，則G含有一個(gè)正規(guī)正則子群R=L或者R=L：Z2且Γ≌Cay（R，S），其中S=｛si|0≤i≤k-1｝，s為R中的一個(gè)對(duì)合.由于|R|是無平方因子數(shù)，從而R是一個(gè)二面體群，不妨假設(shè)R=D2n，則此時(shí)D2n：Zk，定理3.1中（2）成立.

假設(shè)CX（Y）/=Y，由于X≤（Sp×Sp）：Z2，所以CX（Y）≤Z2p：Z2.又因?yàn)閄/CX（Y）是Aut（Y）的子群，故X≤（Z2p：Z2）.Zp-1.假設(shè)p2不是|CX（Y）|的因子，則|CX（Y）|=Y×K，其中K/=1且K是CX（Y）的p′Hall子群，從而K是X的正規(guī)子群且K在VM上作用平凡，從而MK是G的正規(guī)子群且與M的軌道相同，從而與M的選擇矛盾.從而p2是|CX（Y）|的因子，

.特別地，ΓM=Kp，p且k=p，此時(shí)X在VM上作用傳遞，Γ是G弧傳遞圖.令Q為CX（Y）的Sylow p子群，則Q是X的正規(guī)子群且MQ是G的正規(guī)子群.

類似前面的討論，

如果Q∩CMQ（M）=Q，則M=1且Γ≌Kk，k.如果

令N是M中指數(shù)為素?cái)?shù)的正規(guī)子群，則NY是G的正規(guī)子群.顯然，NY在M的兩部分都是不傳遞的，故Γ是ΓNY的一個(gè)覆蓋.從而soc（G/NY）為素?cái)?shù)階群，Γ是無平方因子階的二面體群所對(duì)應(yīng)的一個(gè)正則Cayley圖，定理3.1中（2）成立.

［1］顧沛.對(duì)稱與群［M］.北京：高等教育出版社，2011.

［2］陳進(jìn)之.群與圖及相關(guān)課題的研究［J］.數(shù)學(xué)理論及應(yīng)用，2001，21（1）：120-125.

［3］Hahn G，Sabidussi G.Graph Symmetry［M］.The Netherlands：Kluwer Academic Publishers，1996.

［4］徐明曜.有限群導(dǎo)引：上冊(cè)［M］.北京：科學(xué)出版社，1999.

［5］徐明曜，黃建華，李慧陵等.有限群導(dǎo)引：下冊(cè)［M］.北京：科學(xué)出版社，1999.

［6］Chao C Y.The classification of symmetric graphs with a prime number of vertices［J］.Transactions of the American Mathematical Society，1971，158：247-256.

［7］Cheng Y，Oxley J.On weekly symmetric graphs of order twice a prime［J］.Journal of Combinatorial Theory Series B，1987，42：196-211.

［8］Liebeck M W，Saxl J.Primitive permutation groups containing an element of large prime order［J］.Journal of London Mathematical Society，1985，2：237-249.

［9］Marusic D，Scapellato R.Characterizing vertex-transitive pq-graphs with an imprimitive automorphism subgroup［J］.Journal of Graph Theory，1992，16：375-387.

［10］Praeger C E，Xu M Y.Vertex-primitive graphs of order a product of two distinct primes［J］.Journal of Combinatorial Theory Series B，1993，59：245-266.

［11］Praeger C E，Wang R J，Xu M Y.Symmetric graphs of order a product of two distinct primes［J］.Journal of Combinatorial Theory Series B，1993，58：299-318.

［12］Li C H，Maruvsivc D，Morris J.Classifying arc-transitive circulants of square-free order［J］.Journal of Algebraic Combinatorics，2001，14：145-151.

［13］Li C H，Seress A.On Vertex-transitive non-Cayley graphs of square-free order［J］.Designs，Codes and Cryptography，2005，34：265-281.

［14］Li C H，Liu Z，Lu Z P.Tetravalent edge-transitive Cayley graphs of square-free order［J］.Discrete Mathematics，2012，312：1952-1967.

［15］Li C H，Seress A.The primitive permutation groups of square-free degree［J］.Bulletin of the London Mathematical Society，2003，35：635-644.

［16］Li C H，Lu Z P，Wang G X.Vertex-transitive cubic graphs of square-free order［J］.Journal of Graph Theory，2014，75：1-19.

On the group and graph symmetries

Wang Jiali，Wang Gaixia，Zheng xiang

（School of Mathematics and Physics，Anhui University of Technology，Maanshan 243002，China）

In this paper，the symmetries of plane figure is analyzed and quantified at first，then the relation between the general symmetry of a graph and its automorphism group is studied，and the automorphism groups of the locally primitive arc transitive graphs of square-free order is presented.

Cayley graph，Permutation group，Locally primitive

O157.6

A

1008-5513（2015）04-0367-06

10.3969/j.issn.1008-5513.2015.04.005

2015-07-14.

國(guó)家自然科學(xué)基金（11226276）；安徽省自然科學(xué)基金（1408085MA04）；安徽工業(yè)大學(xué)研究生創(chuàng)新研究基金（2014130）；安徽省大學(xué)生創(chuàng)新創(chuàng)業(yè)訓(xùn)練項(xiàng)目（AH201310360231，AH201310360341）.

王佳利（1990-），碩士生，研究方向：代數(shù)組合，群與圖.

王改霞（1982-），博士，講師，研究方向：代數(shù)組合，群與圖.

2010 MSC:05C25