樹的強(qiáng)自同態(tài)幺半群的一些特征

摘 要： 給定圖τ=（V，E）為只有有限個(gè)頂點(diǎn)的無(wú)向，簡(jiǎn)單樹（文中涉及的樹都滿足這個(gè)條件）.設(shè)τ的所有強(qiáng)自同態(tài)映射組成的半群為樹圖τ的強(qiáng)自同態(tài)幺半群，記作sEndτ.通過(guò)樹的特征研究了樹的強(qiáng)自同態(tài)幺半群的特征，得到結(jié)論：若τ′為τ的連通子圖，則sEndτ′同構(gòu)于sEndτ的子半群.

關(guān)鍵詞： 自同態(tài)幺半群 連通子圖 子半群 右理想

有限單群的分類經(jīng)過(guò)群論工作者長(zhǎng)達(dá)150年的努力，已于上個(gè)世紀(jì)八十年代完成[1].學(xué)者們最終證明，有限單群共有十八個(gè)無(wú)限族和二十六個(gè)零散單群.單群分類完成后，Gorenstein提到了群論研究的幾個(gè)發(fā)展方向：新領(lǐng)域的出現(xiàn)（比如，對(duì)可解群的研究更加深入），圖的研究及在分類過(guò)程中提出的研究方法的應(yīng)用等.

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

文章嘗試討論圖的自同態(tài)幺半群與圖的結(jié)構(gòu)之間的關(guān)系.因?yàn)橐话銏D形的研究難度較大，于是主要討論簡(jiǎn)單樹強(qiáng)自同態(tài)幺半群，最后得到：樹的每個(gè)連通子圖的強(qiáng)自同態(tài)幺半群均同構(gòu)與樹的強(qiáng)自同態(tài)幺半群的子半群；樹的強(qiáng)自同態(tài)幺半群的極大右理想對(duì)應(yīng)樹的極大連通子圖.

文章未作特殊說(shuō)明處，均討論有限個(gè)頂點(diǎn)的簡(jiǎn)單無(wú)向樹.

τ表示一棵樹.用V 為樹τ的頂點(diǎn)集，E 為樹τ的邊集.

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

樹τ的強(qiáng)自同態(tài)半群：τ到自身的所有強(qiáng)同態(tài)組成的集合，記作sEnd（τ）.

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

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

引理1 樹τ的強(qiáng)自同態(tài)半群sEnd（τ）為幺半群.

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

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

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

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

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

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

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

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

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

證明：由推論1知？堝α∈sEndτ，使得α（τ）=τ′，α（τ′）=τ′.？坌β∈sEndτ′，令β′=αβ，S ={αβ|β∈sEndτ′}.一、若？坌β ，β ∈sEndτ′，β ≠β ，則有αβ ≠αβ ，所以sEndτ′與S ={αβ|β∈sEndτ′}之間一一對(duì)應(yīng).二、由（αβ ）·（αβ ）=αβ αβ =α（β α）β =α（β β ），得sEndτ′與S ={αβ|β∈sEndτ′}之間同態(tài)關(guān)系α：β→αβ.由一、二可得sEndτ′同構(gòu)于S ={αβ|β∈sEndτ′}.易知S ={αβ|β∈sEndτ′}？哿sEndτ，所以sEndτ′同構(gòu)于sEndτ的子半群.

將已知條件中的樹換成有限階的有向簡(jiǎn)單樹時(shí)則不一定出現(xiàn)定理一的情況.

例子1，構(gòu)造有限階的簡(jiǎn)單有向樹τ=（V，E），如圖1.再構(gòu)造其子圖τ′=（V′，E′），如圖2.

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

進(jìn)一步思考，還有什么樣的圖能有定理一這樣的性質(zhì)呢？通過(guò)研究得到1個(gè)簡(jiǎn)單的猜想.

當(dāng)一個(gè)有限階的簡(jiǎn)單有向圖有一個(gè)圈時(shí)，則不一定有定理一的性質(zhì).例如：構(gòu)造有限階的簡(jiǎn)單無(wú)向圖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′有不同自同構(gòu)群.又因?yàn)閟EndG=S ，所以sEndG′不可能同構(gòu)于sEndG的子半群.

因此，產(chǎn)生一個(gè)猜想，只有當(dāng)限階的簡(jiǎn)單有向圖G=（V，E）是一棵樹時(shí)，才會(huì)有定理一的結(jié)果.

參考文獻(xiàn)：

[1]D.Gorenstein，F(xiàn)inite Simple Groups，Harper and Row，NewYork，1968.

[2]路在平.雙Cayley圖的自同構(gòu)群[J].北京大學(xué)學(xué)報(bào)（自然科學(xué)版），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]祝富洋，游泰杰，徐波.樹在其自同構(gòu)群下的點(diǎn)軌道集的特征[J].貴州師范大學(xué)學(xué)報(bào)（自然科學(xué)版），2013.