樹的強自同態幺半群的一些特征

摘 要： 給定圖τ=（V，E）為只有有限個頂點的無向，簡單樹（文中涉及的樹都滿足這個條件）.設τ的所有強自同態映射組成的半群為樹圖τ的強自同態幺半群，記作sEndτ.通過樹的特征研究了樹的強自同態幺半群的特征，得到結論：若τ′為τ的連通子圖，則sEndτ′同構于sEndτ的子半群.

關鍵詞： 自同態幺半群 連通子圖 子半群 右理想

有限單群的分類經過群論工作者長達150年的努力，已于上個世紀八十年代完成[1].學者們最終證明，有限單群共有十八個無限族和二十六個零散單群.單群分類完成后，Gorenstein提到了群論研究的幾個發展方向：新領域的出現（比如，對可解群的研究更加深入），圖的研究及在分類過程中提出的研究方法的應用等.

通過閱讀與思考，發現其中研究得比較多的對象是通過群構造的凱萊圖（均是點傳遞的圖，即圖在其自同構群作用下只有一條頂點軌道），還有一些特殊圖，如正則圖線圖等.例如：在文獻[8]中，討論了雙Cayley圖的自同構群.在文[2]，[3]，[4]討論了Cayley圖的Hamilton性.還有的討論點傳遞圖的Hamilton性的文章，見文獻[5][6].

文章嘗試討論圖的自同態幺半群與圖的結構之間的關系.因為一般圖形的研究難度較大，于是主要討論簡單樹強自同態幺半群，最后得到：樹的每個連通子圖的強自同態幺半群均同構與樹的強自同態幺半群的子半群；樹的強自同態幺半群的極大右理想對應樹的極大連通子圖.

文章未作特殊說明處，均討論有限個頂點的簡單無向樹.

τ表示一棵樹.用V 為樹τ的頂點集，E 為樹τ的邊集.

給定兩棵樹τ′，τ.設α是V →V 的一個映射，且滿足？坌x，y∈V ，若（x，y）∈E，則（α（x），α（y））∈E 且？坌m，n∈V ，（m，n）∈E ，蘊含（m，n）的原象屬于E ，稱α為圖τ到τ′上的一個強同態.

樹τ的強自同態半群：τ到自身的所有強同態組成的集合，記作sEnd（τ）.

α（τ）表示同態映射α作用于樹τ得到的新樹，記為α（τ）=τ .

其中V =τ（V ），E =τ（E ）.

引理1 樹τ的強自同態半群sEnd（τ）為幺半群.

證明：設e是Autτ的單位元，由定義可知e∈sEnd（τ），顯然有？坌α∈sEndτ，αe=eα所以引理得證.

引理2 設α∈sEndτ，令α（τ）=τ ，則τ 為τ的連通子圖.

證明：由定義易知，？坌x，y∈V ，若（x，y）∈E ，則（α（x），α（y））∈E 有τ 連通圖.又因為V ？哿V ，？坌m，n∈V ，（m，n）∈E 蘊含（m，n）的原象屬于E ，

則顯然有τ 為τ的子圖.所以τ 為τ的連通子圖.

引理 3 設τ的階是n（n≥2），若τ 為τ的n-1階連通子圖，則？堝α∈sEndτ，使得α（τ）=τ ，α（τ ）=τ .

證明：易證τ 為τ的n-1階連通子圖，等價于τ去掉的是一片葉子.當n=2時，引理顯然成立.當n≥3時，設τ 是去掉了葉子v 得到，令v 是與v 相鄰的（即（v ，v ）∈E ），v 是與v 相鄰且v ≠v .構造α，令α（v ）=v ？搖？搖i≠1v ？搖？搖i=1，由sEnd（τ）的定義易知α∈sEndτ.引理得證.

推論1設τ的階是n（n≥2），若τ 為τ的k（k=1，2…，n-1，n）階連通子圖，則？堝α∈sEndτ，使得α（τ）=τ ，且α（τ ）=τ .

證明：當k=n時，α∈Autτ，顯然有α∈sEndτ.當k=n-1時，由引理3結論可得證.當k=n-2時，可得存在τ 為τ的n-1階連通子圖且τ 為τ 的n-2階連通子圖，由引理3，？堝β∈sEndτ，使β（τ）=τ ，α（τ ）=τ .同理得，？堝？掊∈sEndτ ，使？掊（τ ）=τ ，？掊（τ ）=τ .則α=？掊·β.由定義易知α∈sEndτ.推論1得證.

定理1若τ′為τ的連通子圖，則sEndτ′同構于sEndτ的子半群.

證明：由推論1知？堝α∈sEndτ，使得α（τ）=τ′，α（τ′）=τ′.？坌β∈sEndτ′，令β′=αβ，S ={αβ|β∈sEndτ′}.一、若？坌β ，β ∈sEndτ′，β ≠β ，則有αβ ≠αβ ，所以sEndτ′與S ={αβ|β∈sEndτ′}之間一一對應.二、由（αβ ）·（αβ ）=αβ αβ =α（β α）β =α（β β ），得sEndτ′與S ={αβ|β∈sEndτ′}之間同態關系α：β→αβ.由一、二可得sEndτ′同構于S ={αβ|β∈sEndτ′}.易知S ={αβ|β∈sEndτ′}？哿sEndτ，所以sEndτ′同構于sEndτ的子半群.

將已知條件中的樹換成有限階的有向簡單樹時則不一定出現定理一的情況.

例子1，構造有限階的簡單有向樹τ=（V，E），如圖1.再構造其子圖τ′=（V′，E′），如圖2.

由圖1可知，sEndτ為{e，α}，α（v ）=v ，i≠8v ，i=8，i=1，2，…，9.由圖2可得Autτ′=S ？哿sEndτ′.易知，sEndτ′不可能同構于sEndτ的子半群.

進一步思考，還有什么樣的圖能有定理一這樣的性質呢？通過研究得到1個簡單的猜想.

當一個有限階的簡單有向圖有一個圈時，則不一定有定理一的性質.例如：構造有限階的簡單無向圖G=（V，E），其中v={v ，v ，v }，E={（v ，v ），（v ，v ），（v ，v ）}，如圖3.易知，圖4G′=（V′，E′）為G=（V，E）的連通子圖.我們有AutG=S ，但是AytG′=S .顯然圖G與G′有不同自同構群.又因為sEndG=S ，所以sEndG′不可能同構于sEndG的子半群.

因此，產生一個猜想，只有當限階的簡單有向圖G=（V，E）是一棵樹時，才會有定理一的結果.

參考文獻：

[1]D.Gorenstein，Finite Simple Groups，Harper and Row，NewYork，1968.

[2]路在平.雙Cayley圖的自同構群[J].北京大學學報（自然科學版），2003，39（1）：1-5.

[3]Meng Jixiang，Huang qiongxiang.Almost all Cayley Graphs Are Hamiltonian[J].Acta Mathematica Sinica，1996，12：151-155.

[4]Li Haizhu，Wang Jianfang，Sun Liang.Hamiltonian decomposition of Cayley graphs of ordersp2 andpq [J].Acta Mathematicae Applicatae Sinica，2000，16：78-86.

[5]S.J.Curran，J.A.Gallian.Hamiltonian cycles and paths in Cayley graphs and digraphs—a survey，Discrete Math，1996 （156）：1-18.

[6]D.Marusic，Hamiltonian cycles in vertex-symmetric graphs of order 2p^2，Discrete Math，1987（66）：169-174.

[7]祝富洋，游泰杰，徐波.樹在其自同構群下的點軌道集的特征[J].貴州師范大學學報（自然科學版），2013.