Burnside引理与Polya定理

Burnside引理与Polya定理

1.置换。

大概学过抽象代数的同学都知道这个概念吧。

置换简单来说就是对元素进行重排列，如下图所示。置换是[1,n]到[1,n]的一一映射。

再比如，将正方形绕其中心逆时针旋转90度，可以看成是正方形四个顶点的一个置换。关于置换、置换群的具体理论，可以学一下抽象代数。

（1）置换可以分解成若干循环，方法为：连边1−>a1,2−>a2,…，i−>ai，…,n−>an，任取一个元素，顺着有向边走，直到回到出发点，即形成一个环，剩余元素也是这样。

（2）如果一个状态经过置换f后跟原来相同，即S[1]=S[a1],S[2]=S[a2],…,S[n]=S[an]。则称该状态为f 的不动点。

（3）题目中常常出现“本质不同的方案数”，一般是指等价类的数目，题目定义一个等价关系，满足等价关系的元素属于同一等价类。等价关系通常是一个置换集合F，如果一个置换能把其中一个方案映射到另一个方案，则二者是等价的。

那么，置换构成的群就是置换群，就是交换排列顺序而已。2.Burnside引理：

对于一个置换f,若一个染色方案s经过置换后不变，称s为f的不动点。将f的不动点数目记为C(f)，则可以证明等价类数目为所有C(f)的平均值。

百度百科的定义：

设G=a1,a2,…ag是目标集[1,n]上的置换群。每个置换都写成不相交循环的乘积。 是在置换ak的作用下不动点的个数，也就是长度为1的循环的个数。通过上述置换的变换操作后可以相等的元素属于同一个等价类。若G将[1,n]划分成l个等价类，则：

举个例子： 一正方形分成4格，2着色，有多少种方案？其中，经过转动相同的图象算同一方案。

对于每种格子我们都有两种选择，所以会有一下16种方案： （百度百科）

但是对于这16种方案可以归一下类：

-不动：a1=(1)(2)…(16)

-逆时针转90度 ：a2=(1)(2)(3 4 5 6)(7 8 9 10) (11 12)(13 14 15 16)

-顺时针转90度 ：a3=(1)(2)(6 5 4 3)(10 9 8 7)(11 12)(16 15 14 13)

-转180度：a4=(1)(2)(3 5)(4 6)(7 9)(8 10)(11)(12) (13 15)(14 16)

(a,b,c)表示a,b,c可以通过旋转得到。

由Burnside引理，共有(16+2+2+4)4=6(种方案).

burnside是一种计数方法，用来计算含有不等价类的数量

burnside算法的关键是找好“置换群”。

例题：

​​POJ 2154​​

​​PE 281​​

利用Burnside引理要首先列出所有nm种可能的染色方案，然后找出在每个置换下保持不变的方案数。显然当m或n很大的时候，这个方法会非常繁琐。 这时就需要用到polya定理。

3.polya定理 polya定理实际上是burnside引理的具体化，提供了计算不动点的具体方法。 假设一个置换有k个循环，易知每个循环对应的所有位置颜色需一致，而任意两个循环之间选什么颜色互不影响。因此，如果有m种可选颜色，则该置换对应的不动点个数为mk。用其替换burnside引理中的C(f)，即C(f)=mk。得到等价类数目为：

∑|F|i=0mki|F|

其中|F|表示置换的数目，ki表示第i个置换包含的循环个数。

还是这个例子吧。

-不动：a1=(1)(2)(3)(4) -旋转90度 ：a2=(1 2 3 4) -旋转180度 ：a3=(1 3)(2 4) -旋转270度：a4=(1 4 3 2) 比如，“逆时针旋转180度”，这个置换写成循环的乘积就是（1,3）（2,4），即1和3互变，2和4互变，不难发现，1和3的颜色必须相同，2和4的颜色也必须相同，而1-3和2-4的颜色互不相干。 由Polya定理得，共有(24+21+22+21)4=6(种方案). 可以看Burnside引理和Polya定理是一样的，Polya定理是Burnside引理的优化。

例题： ​​​POJ 1286​​

除此之外还有很多例题的，不详细列出来了。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。