资讯

精准传达 • 有效沟通

从品牌网站建设到网络营销策划,从策略到执行的一站式服务

polya定理-创新互联

  polya定理的内容好多啊,虽然公式很简单,但是前面关于群论与置换群的内容就要理解一会儿了。。

成都创新互联公司是一家以网络技术公司,为中小企业提供网站维护、网站建设、做网站、网站备案、服务器租用、申请域名、软件开发、重庆小程序开发等企业互联网相关业务,是一家有着丰富的互联网运营推广经验的科技公司,有着多年的网站建站经验,致力于帮助中小企业在互联网让打出自已的品牌和口碑,让企业在互联网上打开一个面向全国乃至全球的业务窗口:建站联系热线:028-86922220

  详细的话就看下组合数学,也可看下这个课件http://wenku.baidu.com/view/3dc7027602768e9951e738ca.html

 下面就说一下自己的见解:

   1)关于群与置换群:

     群:就是经过二元运算后还满足 封闭性、结合律、单位元存在、逆元存在性质的集合就是群。。

       这里的二元运算很广泛,当然也包括+-*/什么的。。。

      举个例子:a,b属于R集,那么,那么a*b当然也属于R了。。那么R对这个运算当然是一个群了

    置换群:实际上就是排列的变化,如 这个就是一个排列到另外一个排列的变化就是一个置换。。a1->ai1

         a2-->ai2.........

  2)Burnside引理:

    实际上就是把所有的方案列出来,对于每一个置换,把置换下不变的方案数统计出来,累加起来

    最后除以置换总数。。

  3)polya定理:

    就是burnside的优化而已,因为所有的进行一次,时间复杂度o(nsp)太高了,所以得优化

    方法:

      把每种置换写成若干个不想交循环的乘积,比如(1 2 3 4) ->(2 1 4 3) 这个置换就可以写成 (1 2)*(3 4),那么求本质不同的时候,只要每个循环

     里涂一种颜色(想想为什么,因循环内部必须一样,这样在该置换下才是一种方案啊,不然就变成多种了),这样的话就变成2(循环的个数)个位置的染色,所以该置换       下为M^2中方案本质不同的(M为颜色数)

     所以就变成了求每种置换下的循环个数,然后每种对应M^T个方案,T为循环个数,其他跟burnside一样。。

 4)polya与burnside联系:

     两者本质相同,结合起来用是解题是最需要的,因为单纯的burnside复杂度太高,polya适用范围较小,遇到颜色有限制条件时,

     就应该用结合的方法, 用(方案总数) / 置换数 的思想,

                   用每种置换下找循环个数并 染色的方法求方案的技巧,

                   从而求出最后答案啊。


文章题目:polya定理-创新互联
URL网址:http://cdkjz.cn/article/dghjis.html
多年建站经验

多一份参考,总有益处

联系快上网,免费获得专属《策划方案》及报价

咨询相关问题或预约面谈,可以通过以下方式与我们联系

大客户专线   成都:13518219792   座机:028-86922220