群、Burnside引理与Pόlya定理

搞了整整一天就学了这些玩意

1.群

想要学会下面的必须得把基本概念弄清楚啊。。血的教训。。

给定一个集合G={a,b,c,…}和一个G上的二元运算×,

若满足

  1. 封闭性:\(\forall a,b\in G,a×b\in G\)
  2. 结合律:\(\forall a,b,c\in G,a×(b×c)=(a×b)×c\)
  3. 单位元:\(\exists e,\forall a\in G,a×e=e×a=a\)
  4. 逆元:\(\forall a\in G,\exists b\in G,a×b=b×a=e\)

那么称集合G在×运算下是一个群。

2.置换

n个元素的置换表示为

$$\begin{pmatrix}
1&2&3&···&n\\
a_1&a_2&a_3&···&a_n
\end{pmatrix}$$

其中a是1到n的一个排列,该置换将原来第\(i\)位的元素替换为第\(a_i\)位的元素。

3.置换群

置换群的元素为置换,运算为置换的叠加。

特别的,记

$$(a_1 a_2 ··· a_n)=
\begin{pmatrix}
a_1&a_2&a_3&···&a_n\\
a_2&a_3&a_4&···&a_1
\end{pmatrix}$$

为一个n阶循环。每个置换都可以写成若干互不相交循环的叠加。

如:

$$\begin{pmatrix}
1&2&3&4&5&6\\
3&5&6&4&2&1
\end{pmatrix}=(1 3 6)(2 5)(4)$$

4.Burnside引理

Burnside引理、Pόlya定理都是用来处理这样一个问题:对于一个元素集S,用k种颜色进行染色,并给定置换群G,若\(\exists g\in G\)使得两种染色方案A、B相同,那么认为A和B等价,记为A~B。问有多少种本质不同的染色方法。

对于两种染色方案A~B,我们称A和B属于同一个等价类。本质不同的染色方法数也就等于不同的等价类的数目。

那么Burnside引理告诉我们,若记在一个置换\(g\in G\)下保持不变的染色方案数为C(g),那么总的本质不同的染色方案数为所有\(g\in G\)的C(g)的平均值。写成公式就是如下定理:

设置换群G作用于有限集合\(\chi\)上,则\(\chi\)在G作用下的等价类的数目为:

$$l=\frac{\sum_{g\in G}C(g)}{|G|}$$

其中\(\chi\)指的是染色方案集。

5.Pόlya定理

有了Burnside引理,我们就需要一种行之有效的方法来快速求出每个C(g)的值。

由于每个置换可以表示为若干个不相交循环的叠加,那么我们可以首先把置换g表示出来。

就用上面的例子:

$$\begin{pmatrix}
1&2&3&4&5&6\\
3&5&6&4&2&1
\end{pmatrix}=(1 3 6)(2 5)(4)$$

那么可以发现,在该置换下,若要使染色方案等价,那么136的颜色必须相同,25的颜色必须相同,4单独一个不用考虑

所以我们将这个置换分成了三部分,每个部分可以染一种颜色

总的染色方案就是\(k^3\)!(k表示颜色数)

若用m(g)表示g用不相交循环表示中循环的个数,那么有如下定理:

如果用k种颜色给有限集S染色,对于一个置换g,

$$C(g)=k^{m(f)}$$

将这个定理直接代入Burnside引理,就得到了Pόlya定理:

对于一个元素集S,用k种颜色进行染色,并给定置换群G,若一个方案通过置换\(g\in G\)得到另一个方案,则这两个方案等价,那么本质不同的染色方案数为:

$$l=\frac{\sum_{g\in G}k^{m(g)}}{|G|}$$

若用m(g)表示g用不相交循环表示中循环的个数。

那么对于这一类染色方案数问题,若染色方案数为p,就得到了一个复杂度为O(p|S|)的优秀算法。

说点什么

您将是第一位评论人!

提醒
wpDiscuz