参考/来源:
图的同构
置换群
群
Burnside引理
∣X/G∣=∣G∣1g∈G∑∣Xg∣
其中
Xg={x∣x∈X,g(x)=x}
X为映射(所有染色方案),X/G为置换群G作用在X上产生的等价类,Xg代表X中运用置换g仍然不变的元素(通俗的讲就是给正方体染色,所有染色方案中执行这个置换后正方体完全相同的染色方案)。考虑下Xg如何求,其实把g划分成多个等价类使得等价类个数最少,且对于X中所有元素执行置换g,不会存在一个元素出现“跨等价类置换”的情况。
(图的情况中)换句话说,对于置换g如果存在k个边的等价类,那么X中就有2k个不动点。即:
∣Xg∣=2k
图的同构
式子:
∣X/G∣=∑b∏(bi)∏(ci!)2kk=∑i=1K⌊2bi⌋+∑i=1K∑j=1i−1gcd(bi,bj)
其中b是从小到大划分n,c每个划分的每种划分大小有多少个。