搞了整整一天就学了这些玩意
1.群
想要学会下面的必须得把基本概念弄清楚啊。。血的教训。。
给定一个集合G={a,b,c,…}和一个G上的二元运算×,
若满足
- 封闭性:\(\forall a,b\in G,a×b\in G\)
- 结合律:\(\forall a,b,c\in G,a×(b×c)=(a×b)×c\)
- 单位元:\(\exists e,\forall a\in G,a×e=e×a=a\)
- 逆元:\(\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|)的优秀算法。