用数字表示各点(就像表盘一样),那么我们用一个数组就可以表示一幅图:相邻的数字表示对应的点相连。例如
并且我们发现,若对该图施以置换
图 与图 是没有区别的。但若施以置换
这提示我们,这个问题实际上要求我们研究对称群 在某种等价关系下的商集。
则 ,这是因为一个无向圈的起点、方向是任意的。
所以当我们讨论某一图时,实际上说的是一个等价类,或者说代表元。
正方形共有8个对称变换,其中有4个旋转变换,4个轴对称变换,这也就是说图 在以下置换中不变。
事实上 是 的子群——二面体群。而其余置换则会改变图形原先的连接方式,于是形成了新的图,前文我们验证了 就是这样的置换。接下来我们从“生成元”的角度去看待这个问题:先找到几个基本生成元,然后再交给 去变换,得到的置换与对应的生成元等价,从而穷尽 ,这样我们的考虑就完全。
经计算,只需考虑的 三个陪集有以下关系,即
可见需要考虑的图无非以下3种:
而后两者却有如下关系
所以只有两类图
通过上面的分析,对于更一般的 的解题流程:
于是得到图形总个数:
定理1
关于具体的计算,我们有——
引理2(Lagrange)
是 的子群,则
是 关于 的陪集个数
进而可以得到一个粗略的估计:
定理3
证:上界由定理1、引理2可得
即忽略了 的影响
于是由定理3可知
这个上界是大了点……
这个重点分析,留到以后。