Polya总结

标签： 总结

---

1.序

Polya定理主要是解决一类翻转染色问题，即本质不同的种类数。（看到题目问题问本质不同的什么什么…就可以联想到Polya定理了）

2.重要定理

这个算法有两个最重要的定理，只要知道这个定理就可以直接套公式辣~~

（1）Burnside 引理

$$\frac{1}{\left | G \right |}\sum_{i=1}^{n}D(a_{i})$$
其中G表示置换种类（需要记住的是不变置换也算一种置换）
$D(a_{i})$表示在i置换下不动点的个数（这里的“点”可以理解一种方案，比如涂色方案）

（2）Polya 定理

$$\frac{1}{\left | G \right |}\sum_{i=1}^{n}m^{c(g_{i})}$$
其中m表示染色种类，$c(g_{i})$表示在第i种置换下的循环节个数
我们可以从Burnside引理来理解，Burnside引理是求每个置换下的不动点，而每种置换可以当前目标分割成一个一个的循环节，那么只要对每个循环节内部染上相同颜色，则就相当于构造出不动点了撒

3.方法总结

几乎可以一句话总结:找循环节！只要找到就可以套公式辣。当然这里是对于颜色无限使用的情况下，如果颜色数量有限制的话我们就只能用Burnside引理了（比如找出循环节然后对每个循环节分配颜色，就相当于背包DP之类的）
当然还有一类题是就同构图，即二元组的polya定理（这个是我自己口胡的，感觉很形象~~）详见这里

4.最后的话

对Polya定理总结大概就这样吧，以后遇到新题型也会及时更新的~~