關(guān)于簡單樹的一類計(jì)數(shù)問題的討論

摘 要： 本文通過定義的運(yùn)算“*”，簡要討論了集合τ*τ={（τ，x）*（τ，y）|x∈V，y∈V}的計(jì)數(shù)問題.其中：V）=V∪V，E） =E∪E∪{（x，y）}。研究得到，在運(yùn)算“*”下：若τ，τ是兩棵同階不同構(gòu)簡單無向樹，則|τ*τ={（τ，x）*（τ，y）|x∈V，y∈V}|=|V/Autτ| · |V/Autτ|.

關(guān)鍵詞： 樹 自同構(gòu)群 點(diǎn)軌道

對于一般的圖，可以通過自同構(gòu)群的概念將群與圖聯(lián)系起來，而這正是圖論的一個(gè)充滿活力的新分支.在Springer出版的《Algebraic Graph Theory》一書中有比較系統(tǒng)的介紹.這其中研究得比較多的對象是通過群構(gòu)造的凱萊圖，還有一些特殊圖，如正則圖、樹、線圖等.在文獻(xiàn)[1]中討論了雙Cayley圖的自同構(gòu)群.在文獻(xiàn)[2]、[3]、[4]中討論了Cayley圖的Hamilton性.還有的研究方向是討論圖的不同性質(zhì)如何通過其自同構(gòu)群反應(yīng)，這里面有一些重要而沒有解決的猜想，如“頂點(diǎn)傳遞的簡單連通圖，則一定存在Hamilton路”.在Jean-Pierre Serre的著作《Trees》中又討論了樹，其中第一章第六節(jié)研究了樹在其任意的自同構(gòu)作用下的不動點(diǎn).在學(xué)習(xí)《Trees》時(shí)，受到啟發(fā)，開始研究由兩棵樹生成新樹時(shí)，對稱群有什么樣的影響.并進(jìn)行關(guān)于簡單樹的一類計(jì)數(shù)問題的討論.

本文中討論的是只有有限個(gè)頂點(diǎn)的簡單無向樹.

τ=（V，E）表示圖.V為τ的頂點(diǎn)集，E為τ的邊集.τ*τ={（τ，x）*（τ，y）|x∈V，y∈V}.其中：V=V∪V，E=E∪E∪{（x，y）}，設(shè)α是V→V的一一映射，且滿足？坌（x，y）∈E，（α（x），α（y））∈E和？坌（x，y）∈E，（α（x），α（y））∈E，稱α為圖τ上的一個(gè)自同構(gòu).由τ上的所有自同構(gòu)構(gòu)成的集合記作Autτ，且Autτ構(gòu)成一個(gè)群，我們稱之為τ的自同構(gòu)群.

x∈V，A表示a在Autτ作用下的點(diǎn)軌道類.τ=Γ

引理1給定圖τ=（V，E），τ=（V，E），若f為τ→τ的同構(gòu)映射，則？坌x∈V，？堝x∈V f（x）=x.

證明：由圖之間同構(gòu)的定義，引理顯然成立.

引理2 給4個(gè)定簡單無向的連通樹τ=（V，E），τ=（V，E），τ=（V，E），τ=（V，E），V∩V=？覬（i，j∈{1，2，3，4}，i≠j），取a∈V，b∈V，c∈V，d∈V，設(shè)|V|=|V|=|V|=|V|.若f為（τ，a）*（τ，b）→ （τ，c）*（τ，d）的同構(gòu)映射，則有：

（1）f（（a，b））=（c，d）.

（2）τ≌τ，τ≌τ且f（a）=c，f（b）=d.或者τ≌τ，τ≌τ且f（a）=d，f（b）=c.

證明：（1）設(shè)f為（τ，a）*（τ，b）→（τ，c）*（τ，d）的同構(gòu)映射，假設(shè)f（（a，b））=（m，n），（（a，b）∈E，（b，z）∈E）（其中（c，d）≠（m，n））.由樹（τ，a）*（τ，b）的定義，可設(shè)當(dāng)樹（τ，a）*（τ，b）抹去邊（a，b）時(shí)，得到兩個(gè)連通的子圖分別為τ，τ.因?yàn)閒為（τ，a）*（τ，b）→（τ，c）*（τ，d）的同構(gòu)映射，且f（（a，b））=（m，n）.所以當(dāng)（τ，c）*（τ，d）抹去（m，n）時(shí)，也得到兩個(gè)連通的子圖，我們分別設(shè)為樹圖τ，τ，其中m∈V，n∈V，且由同構(gòu)的定義可得|V|= |V|.因?yàn)椋╟，d）≠（m，n），所以有（c，d）∈E或（c，d）∈E，假設(shè)（c，d）∈E，由樹（τ，c）*（τ，d）的定義，可設(shè)當(dāng)樹（τ，c）*（τ，d）抹去邊（c，d）時(shí)，得到兩個(gè)連通的子圖分別為τ，τ，我們有V∩V≠？覬且V∩V≠？覬，同時(shí)能得到V∩V≠？覬且V∩V≠？覬.因?yàn)闃洌é樱琧）*（τ，d）的子圖τ，τ，τ，τ都是連通的子圖，當(dāng)（m，n）∈E時(shí)，我們構(gòu)造樹τ的一條連通的道路Γ（v∈τ，v∈τ且v∈τ，v∈τ），當(dāng)（m，n）∈E時(shí)，我們構(gòu)造樹τ的一條連通的道路Γ（v∈τ，v∈τ且v∈τ，v∈τ），所以可以得到樹（τ，c）*（τ，d）的一條連通道路Γ，且邊（m，n）不屬于這條連通的道路，因?yàn)楫?dāng)（τ，c）*（τ，d）抹去（m，n）時(shí)，得到兩個(gè)連通的子圖，我們分別設(shè)為樹τ，τ，即樹（τ，c）*（τ，d）存在一條由v→v的連通道路Γ′，且（m，n）∈E.這將導(dǎo)致樹（τ，c）*（τ，d）存在回路，同理當(dāng)（c，d）∈E，也會導(dǎo)致樹（τ，c）*（τ，d）存在回路，這都將與樹的定義矛盾.所以若f為（τ，a）*（τ，b）→（τ，c）*（τ，d）的同構(gòu)映射，則f（（a，b））=（c，d）.

（2）由（1）可得f為（τ，a）*（τ，b）→（τ，c）*（τ，d）的同構(gòu)映射，則f（a）=c，f（b）=d或者f（a）=d，f（b）=c.當(dāng)f（a）=c，f（b）=d時(shí)，假設(shè)f（V）≠V，則有f（V）∩V≠？覬且f（V）∩V≠？覬.所以當(dāng)樹（τ，a）*（τ，b）抹去頂點(diǎn)，得到至少兩個(gè)連通子圖，這與樹（τ，c）*（τ，d）的定義矛盾（因?yàn)椋é樱琧）*（τ，d）抹去頂點(diǎn)集V生成的是一個(gè)連通子圖，由同構(gòu)映射的定義可知樹（τ，a）*（τ，b）抹去頂點(diǎn)集V生成的是一個(gè)連通子圖），所以f（V）=V，因?yàn)閒為（τ，a）*（τ，b）→（τ，c）*（τ，d）的同構(gòu)映射，所以f（V）=V.由同構(gòu)映射的定義得τ≌τ，τ≌τ且f（a）=c，f（b）=d.

同理當(dāng)f（a）=d，f（b）=c，我們也能得到τ≌τ，τ≌τ且f（a）=d，f（b）=c所以定理得證.

引理3 假設(shè)|V|=|V|=|V|，且（τ，a）*（τ，y）≌（τ，b）*（τ，z）.則有τ≌τ.

證明：設(shè)f：（τ，a）*（τ，y）→（τ，b）*（τ，z）的同構(gòu)映射，由引理2的（2）有τ≌τ，τ≌τ，且a→b，y→z.或者τ≌τ，τ≌τ且a→z，y→b.當(dāng)有τ≌τ，τ≌τ且a→b，y→z，定理得證.當(dāng)τ≌τ，τ≌τ且a→z，y→b，顯然有τ≌τ.

引理4 假設(shè)|V|=|V|=|V|，且a，b∈V，y∈V.當(dāng)在圖τ=（V，E）中有A=A時(shí)，則在（τ，a）*（τ，y）≌（τ，b）*（τ，y）

證明：假設(shè)由A、A的定義可知？堝f∈Autτ， f（a）=b，定義f（x）=f（x），x∈Vx，x∈V，顯然可得，f是Aut（τ，a）*（τ，y）→（τ，b）*（τ，y）的同構(gòu).

引理5 假設(shè)|V|=|V|=|V|，且a，b∈V，y∈V，當(dāng)（τ，a）*（τ，y）≌（τ，b）*（τ，y），則有A=A.

證明：設(shè)f為（τ，a）*（τ，y）≌（τ，b）*（τ，y）的同構(gòu)映射，由引理2的（2）有τ≌τ，τ≌τ且a→b，y→y.或者τ≌τ，τ≌τ，且a→y，y→b.當(dāng)有τ≌τ，τ≌τ，且a→b，y→y，顯然有A=A.當(dāng)τ≌τ，τ≌τ，且a→y，y→b，可以得到τ≌τ且a→b，所以有A=A.所以引理得證.

引理6 假設(shè)|V|=|V|，取a，b∈V，y，z∈V，若τ不同構(gòu)τ.則（τ，a）*（τ，y）≌（τ，b）*（τ，z）當(dāng)且僅當(dāng)A=A，A=A.

證明：充分性：設(shè)f為（τ，a）*（τ，y）≌（τ，b）*（τ，y）的同構(gòu)映射，由引理2的（2）有τ≌τ，τ≌τ且a→b，y→y.或者τ≌τ，τ≌τ且a→y，y→b.因?yàn)棣硬煌瑯?gòu)τ，所以只有τ≌τ，τ≌τ且a→b，y→y是成立的，顯然在樹τ中有A=A，又由引理5得到在樹τ中有A=A.

必要性：若有A=A，A=A，由引理4顯然可得，（τ，a）*（τ，y）≌（τ，b）*（τ，z）.

定理1 假設(shè)|V|=|V|，若τ，τ不同構(gòu)，則|τ*τ={（τ，x）*（τ，y）|x∈V，y∈V}|=|V/Autτ|·|V/Autτ|

證明：由引理6有（τ，a）*（τ，y）≌（τ，b）*（τ，z）當(dāng)且僅當(dāng)A=A，A=A.所以有|τ*τ={（τ，x）*（τ，y）|x∈V，y∈V}|=|V/Autτ|·|V/Autτ|.

引理7 假設(shè)|V|=|V|，取a，b∈V，y，z∈V.若τ≌τ，則（τ，a）*（τ，y）≌（τ，b）*（τ，z）當(dāng)且僅當(dāng)存在f為τ→τ的同構(gòu)映射使得f（a）=z，f（b）=y，或A=A，A=A.

證明：充分性：若τ≌τ，當(dāng)在樹τ中A=A，又由引理5可得A=A，所以A=A，A=A.當(dāng)A≠A，因?yàn)閨V|=|V|，由（τ，a）*（τ，y）≌（τ，b）*（τ，z）的定義，若設(shè)f為（τ，a）*（τ，y）→（τ，b）*（τ，z）的同構(gòu)映射，由引理2的（2）有τ≌τ，τ≌τ且a→b，y→z，.或者τ≌τ，τ≌τ且a→z，y→b.因?yàn)锳≠A，所以只能有τ≌τ，τ≌τ且a→z，y→b.所以有f（a）=z，f（b）=y.

必要性：若有A=A，A=A，由引理4可得（τ，a）*（τ，y）≌（τ，b）*（τ，z）.若存在f為τ→τ的同構(gòu)映射使得f（a）=z，f（b）=y，顯然有（τ，a）*（τ，y）≌（τ，b）*（τ，z）.

推論1 假設(shè)|V|=|V|，若τ≌τ，則|τ*τ={（τ，x）*（τ，y）|x∈V，y∈V}|=.

證明：若（τ，a）*（τ，y）與（τ，b）*（τ，z）同構(gòu)，由引理7可知存在兩種情況，（1）A=A，A=A時(shí).（2）A≠A時(shí)，存在f為τ→τ的同構(gòu)映射使得f（a）=z，f（b）=y.在只考慮（1）的情況下，|τ*τ={（τ，x）*（τ，y）|x∈V，y∈V}|=|V/Autτ|·|V/Autτ|.當(dāng)A≠A時(shí)，在情況（1）下的計(jì)數(shù)會被重復(fù)一次.所以可以得|τ*τ={（τ，x）*（τ，y）|x∈V，y∈V}|=.

參考文獻(xiàn)：

[1]路在平.On the automorphisms groups of BiCayley Graphs [J].北京大學(xué)學(xué)報(bào)（自然科學(xué)版），2003，36.

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

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

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

[5]Chris Godsil，Gordsil Royle.Algebraic Graph Theory[M].世界圖書出版公司，2004：5-6.

[6]祝富洋，游泰杰，徐波.樹在其自同構(gòu)群下的點(diǎn)軌道集的特征[J].貴州師范大學(xué)學(xué)報(bào)（自然科學(xué)版），2013.