pálya計數(shù)法的應(yīng)用ppt課件

1、Plya計數(shù)法的運用；問題描畫問題描畫 06年江蘇上海選拔賽 染色圖是無向完全圖，且每條邊可被染成k種顏色中的一種。 兩個染色圖是同構(gòu)的，當(dāng)且僅當(dāng)可以改動一個圖的頂點的編號，使得兩個染色圖完全一樣。 問N個頂點，k種顏色，本質(zhì)不同的染色圖個數(shù)模質(zhì)數(shù)NP109。 N53；問題描畫問題描畫；問題描畫問題描畫；問題描畫問題描畫 N=3 K=2；簡單分析簡單分析 枚舉會超時枚舉會超時 普通的乘法原理無法求解普通的乘法原理無法求解；Burnside引理 設(shè)設(shè)G是置換群，是置換群，C是是G的著色集合。的著色集合。 C中的不等價著色數(shù)為：使著色經(jīng)過中的不等價著色數(shù)為：使著色經(jīng)過G中的中的置換堅持不變的著色的

2、平均數(shù)。置換堅持不變的著色的平均數(shù)。sjjaDGAnswer1)(|1；Plya定理 假設(shè)有假設(shè)有k種不同的顏色，某個置換的循環(huán)數(shù)種不同的顏色，某個置換的循環(huán)數(shù)為為c，那么對于這個置換，經(jīng)過它堅持不變，那么對于這個置換，經(jīng)過它堅持不變的著色數(shù)為，的著色數(shù)為，k的的c次方。次方。)()(jacjkaD；例題分析例題分析 放在這個問題中，置換群中的對象就是一放在這個問題中，置換群中的對象就是一切的邊，染成切的邊，染成k種顏色，種顏色，G就是由點的置換就是由點的置換引起的邊的置換的群。引起的邊的置換的群。；分析分析 例如例如N=3時一共有時一共有3條邊。條邊。 點的不同陳列有點的不同陳列有3!=6種

3、。種。 由點的置換而引起的對應(yīng)的邊的置換如下：由點的置換而引起的對應(yīng)的邊的置換如下：)3,2(),3,1(),2,1()3,2(),3,1(),2,1(3,2,13,2,1)3,2(),2,1(),3,1()3,2(),3,1(),2,1(2,3,13,2,1；)3,1(),3,2(),2,1()3,2(),3,1(),2,1(3,1 ,23,2,1)3,1(),2,1(),3,2()3,2(),3,1(),2,1(1 ,3,23,2,1)2,1(),3,2(),3,1()3,2(),3,1(),2,1(2,1 ,33,2,1)2,1(),3,1(),3,2()3,2(),3,1(),2,1(

4、1 ,2,33,2,1；)2,1(),3,2(),3,1()3,2(),3,1(),2,1(2,1 ,33,2,1；分析分析 先求出每個置換的循環(huán)數(shù)先求出每個置換的循環(huán)數(shù)c 根據(jù)根據(jù)Plya定理，可求出本質(zhì)不同的方案定理，可求出本質(zhì)不同的方案數(shù)：數(shù)：sjacjkGAnswer1)(|1；分析分析 這個算法非常直觀，直接套用了這個算法非常直觀，直接套用了Plya定定理，但需求枚舉每個對于點的置換，并求理，但需求枚舉每個對于點的置換，并求循環(huán)數(shù)。時間復(fù)雜度為循環(huán)數(shù)。時間復(fù)雜度為 O(N!N2)。 對于此題對于此題N53的數(shù)據(jù)范圍，這個算法會的數(shù)據(jù)范圍，這個算法會超時。超時。；分析分析 再進一步分析

5、問題，會發(fā)現(xiàn)，其實這再進一步分析問題，會發(fā)現(xiàn)，其實這N!個個置換中，有許多是類似的，比如：置換中，有許多是類似的，比如：；)3,2(),2,1(),3,1()3,2(),3,1(),2,1(2,3,13,2,1)3,1(),3,2(),2,1()3,2(),3,1(),2,1(3,1 ,23,2,1)2,1(),3,1(),3,2()3,2(),3,1(),2,1(1 ,2,33,2,1；分析分析 察看這些對于點的置換，發(fā)現(xiàn)它們都是由察看這些對于點的置換，發(fā)現(xiàn)它們都是由一個長度為一個長度為1和一個長度為和一個長度為2的循環(huán)組成。的循環(huán)組成。 顯然它們對應(yīng)的邊的置換，也是類似的。顯然它們對應(yīng)的邊

6、的置換，也是類似的。假設(shè)把每個置換都處置一遍，是很浪費的。假設(shè)把每個置換都處置一遍，是很浪費的。 這這3個，只需處置一個即可。個，只需處置一個即可。；分析分析 枚舉出一切本質(zhì)不同的對于點的置換，并枚舉出一切本質(zhì)不同的對于點的置換，并對每種置換求下面對每種置換求下面2個值個值 1、該種置換的對應(yīng)邊的置換的循環(huán)節(jié)數(shù)、該種置換的對應(yīng)邊的置換的循環(huán)節(jié)數(shù) 2、與該種置換類似的置換總數(shù)、與該種置換類似的置換總數(shù)；分析分析 要保證枚舉出來的對于點的置換各不一樣，要保證枚舉出來的對于點的置換各不一樣，只需枚舉它的一切循環(huán)節(jié)長度，設(shè)為只需枚舉它的一切循環(huán)節(jié)長度，設(shè)為Li，并保證并保證 0L1L2Lm L1+L2

7、+Lm=N N=53時，一共要需求枚舉時，一共要需求枚舉329921種不種不同情況。同情況。；分析分析 然后需求把對應(yīng)點的循環(huán)信息轉(zhuǎn)化成對應(yīng)邊的置然后需求把對應(yīng)點的循環(huán)信息轉(zhuǎn)化成對應(yīng)邊的置換的循環(huán)節(jié)數(shù)換的循環(huán)節(jié)數(shù)；分析分析 假設(shè)點假設(shè)點i與點與點j同屬于一個長度為同屬于一個長度為L的循環(huán)中，的循環(huán)中，那么那么 (i,j)組成的置換中循環(huán)節(jié)個數(shù)為組成的置換中循環(huán)節(jié)個數(shù)為 有一個長度為有一個長度為5的循環(huán)的循環(huán)(1,2,3,4,5) (1,2),(2,3),(3,4),(4,5),(5,1) (1,3),(2,4),(3,5),(4,1),(5,2)2L；分析分析 假設(shè)點假設(shè)點i與點與點j各屬于長

8、各屬于長L1和和L2的兩個不同循環(huán)中，的兩個不同循環(huán)中，那么這樣的邊那么這樣的邊(i,j)組成的置換中循環(huán)節(jié)個數(shù)為組成的置換中循環(huán)節(jié)個數(shù)為(L1,L2)。 (1,2) (3,4,5,6) (1,3),(2,4),(1,5),(2,6) (1,4),(2,5),(1,6),(2,3) ；分析分析 還需求求出與其類似的置換數(shù)還需求求出與其類似的置換數(shù) 假設(shè)已確定了假設(shè)已確定了0L1L2Lm ，接，接下來就是將下來就是將1N這這N個點分別放入這個點分別放入這m個個循環(huán)節(jié)中，滿足第循環(huán)節(jié)中，滿足第i個循環(huán)中恰含有個循環(huán)中恰含有Li個點，個點，這相當(dāng)于這相當(dāng)于m個圓陳列問題，可知一共有個圓陳列問題，可知

9、一共有mLLLN.!21 種不同方式。種不同方式。；分析分析 假設(shè)有假設(shè)有Li=Li+1=Lj，那么每，那么每(j-i+1)!種方案又是反復(fù)的，所以還要除以種方案又是反復(fù)的，所以還要除以(j-i+1)!；分析分析 所以總的置換個數(shù)就是所以總的置換個數(shù)就是 每個循環(huán)的長度為每個循環(huán)的長度為L 每組每組Li=Li+1=Lj s為為j-i+1!.!.!2121tmsssLLLN；分析分析 需求計算很多需求計算很多T2-1，其中，其中T2很大，而且是很大，而且是-1次的，難道次的，難道要分解質(zhì)因數(shù)了嗎？要分解質(zhì)因數(shù)了嗎？ P是質(zhì)數(shù)，且滿足是質(zhì)數(shù)，且滿足NP。 所以所以T2也與也與P互質(zhì)互質(zhì) 由數(shù)論知識

10、可知：由數(shù)論知識可知： T2p-11 (mod p) T2-1 T2p-1T2-1=T2p-2 (mod p) 所以可以把所以可以把T2-1轉(zhuǎn)化為求轉(zhuǎn)化為求T2p-2，可用倍增的方法在，可用倍增的方法在O(Logp) 的時間內(nèi)求解。的時間內(nèi)求解。；此題總結(jié)此題總結(jié) 這個問題遇到了這樣的困難：這個問題遇到了這樣的困難： 置換的個數(shù)偏多而導(dǎo)致不能對每個置換都算其循置換的個數(shù)偏多而導(dǎo)致不能對每個置換都算其循環(huán)數(shù)環(huán)數(shù) 處理的方法，就是找出置換群中類似的置換，而處理的方法，就是找出置換群中類似的置換，而不反復(fù)計算不反復(fù)計算 這個去除冗余運算的方法在這個去除冗余運算的方法在Plya計數(shù)問題中經(jīng)計數(shù)問題中經(jīng)

11、常用到常用到 對于每類類似置換個數(shù)的計算，也需求扎實的數(shù)對于每類類似置換個數(shù)的計算，也需求扎實的數(shù)學(xué)功底。學(xué)功底。；全文總結(jié)全文總結(jié) 信息學(xué)競賽中經(jīng)常出現(xiàn)這類問題。比如信息學(xué)競賽中經(jīng)常出現(xiàn)這類問題。比如 Transportation is fun (spoj 419) Hes Circles (sgu 294) Cubes (uva 10601) 它們在直接運用公式時往往會遇到一些困它們在直接運用公式時往往會遇到一些困難。這些困難雖然不同，但也有一些類似難。這些困難雖然不同，但也有一些類似之處。之處。；全文總結(jié)全文總結(jié) Plya計數(shù)法不僅僅能處理許多計數(shù)問題，它的證明過程也是相當(dāng)有意思的。 靈

12、敏運用Plya計數(shù)法，不僅僅需求熟練掌握此類問題的性質(zhì)，還要有扎實的數(shù)學(xué)功底和分析問題才干。 數(shù)學(xué)方法是處理問題的工具，而分析問題才干是算法的源泉。；分析分析 下面討論一下如何計算：下面討論一下如何計算： 一部分是一部分是MT1，其中，其中T1并不大，并不大，MT1 mod P可以用倍增的思想在可以用倍增的思想在log(T1)時間時間內(nèi)計算。內(nèi)計算。；證明證明 設(shè)設(shè)c為為 中的一種著色，那么與中的一種著色，那么與 c 等價的等價的著色數(shù)等于著色數(shù)等于G中的置換個數(shù)除以中的置換個數(shù)除以 c 的穩(wěn)定的穩(wěn)定核中的置換個數(shù)。核中的置換個數(shù)。；證明證明 定理定理1：對于每一種著色：對于每一種著色c，c的

13、穩(wěn)定核的穩(wěn)定核G(c)是一個置換群，而且對是一個置換群，而且對 G 中恣意置換中恣意置換f與與 g，g*c=f*c 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng) f-1 g 屬于屬于 G(c)。；證明證明 假設(shè)假設(shè)f*c=g*c 那么那么 所以所以 f-1 g使使c不變，因此，不變，因此，f-1 g 屬于屬于G(c)。 反之，假設(shè)反之，假設(shè)f-1 g屬于屬于G(c) ，經(jīng)過類似的，經(jīng)過類似的計算可證得計算可證得f*c=g*c；證明證明 推論：設(shè)推論：設(shè)c為為 中的一種著色，那么與中的一種著色，那么與 c 等等價的著色數(shù)等于價的著色數(shù)等于G中的置換個數(shù)除以中的置換個數(shù)除以 c 的的穩(wěn)定核中的置換個數(shù)。穩(wěn)定核中的置換個數(shù)。；

14、證明證明 設(shè)設(shè) f 是是 G 中的一個置換，根據(jù)定理中的一個置換，根據(jù)定理1，滿，滿足足g*c=f*c的置換的置換 g 實踐上就是實踐上就是 中的那些置換。中的那些置換。 由消去律，那么從由消去律，那么從f h=f h得到得到h=h。 集合中集合中 的置換個數(shù)等于的置換個數(shù)等于G(c)中中置換的個數(shù)。置換的個數(shù)。 由于總共有由于總共有|G|個置換，所以，與個置換，所以，與c等價的等價的著色數(shù)等于著色數(shù)等于 ；證明證明 我們要數(shù)使我們要數(shù)使f堅持堅持c不變即不變即f*cc的對偶的對偶(f,c)的個數(shù)。的個數(shù)。 ；證明證明 一種計數(shù)的方式是調(diào)查一種計數(shù)的方式是調(diào)查G中的每個中的每個f ，并計，并計算算f堅持著色不變的著色數(shù)，然后相加一切堅持著色不變的著色數(shù)，然后相加一切的量。設(shè)的量。設(shè)D(f)是經(jīng)過是經(jīng)過f堅持著色不變的著色堅持著色不變的著色集，所以用這種方式計數(shù)得到集，所以用這種方式計數(shù)得到 sjjaDGL1)(|1；證明證明 另一種計數(shù)的方式按等價類將著色歸類。另一種計數(shù)的方式按等價類將著色歸類。 在同一等價類中，兩種著色對和奉獻了同在同一等價類中，兩種著色對和奉獻了同樣的量，每個等價類的總奉獻是樣的量，每個等價類的總奉獻是|G|。 因此，不同等價類數(shù)目