当前课程知识点:组合数学 > Polya定理 > 图的计数 > 图的计数
我们刚才都在说一些旋转 翻转
比如说立方体有多少个转动群
但实际波利亚定理有一个
非常重要的应用
是用来给图数数的
大家都知道图在计算机当中
非常的重要
一般图的构造有多少种呢
这个问题就是图的计数
比如我们问N个顶点的简单图
有多少种不同的图形
首先我们知道什么叫简单图
也就是说对于两个顶点之间
它如果是无向边的话
就只有一条边的可能性
而且
不存在环
对于一共有n个顶点列在那里
我要用若干条边对它进行相连接
那就意味着有些边是不存在的
有些边是存在的
这就相当于对完全图进行二着色
求不同的方案数
对于完全图它应该有多少条边呢
每一个顶点它可以和
n减1个顶点进行相连
因为所有的点来计数的话
应该是N乘以N减1
而每条边对有两个点
因此还有再除以2
在这样的条件下
我们来看
应该怎样考虑图的计数问题
首先我们知道图的计数无非就是
完全图上进行二着色
但是它的置换应该怎么写呢
我们当然可以说
比如说这样四个顶点
对应的完全图可以旋转
可以产生某些角度的翻转
但是它有一些不太一样的地方
比如说原来我们认为所有的
正方形 长方形或者是三角形
他们是一个钢体
它不能发生扭转
但是在图中
大家可以看
只有边
边是随点动的
我们有可能出现
只挪动上条边的两个顶点
这时候整个图是发生了扭转的
因此我们会发现由于这不算是
一个钢体了
所以它边随点动
它对应的应该是点的全置换
也就是对应的是对称群
在这里四个顶点的完全图
对应的置换群应该是S4
也就是所有全排列对应的置换
都可以用来表示它的置换结果
我们先看一个简单的例子
以三个顶点为例
我们现在有一个正三角形
3个顶点
那么它V1 V2
V3这样一个完全
图中我有多少种
不同的边的刻画方法呢
这就是图的计数
首先我们知道它对应的就是S3
3的所有排列全部列举出来
对应的边的置换该如何呢
首先第一点
它不动的时候我们知道
它就是各个边不动
但是如果它进行翻转比如说V1不动
下面的V2和V3进行翻转的话
我们会发现有一条边不动
而上面的两条腰会发生相互的交换
根据对应的边的置换
我们可以写出它的母函数形式
也就是它首先是两着色
它就有可能用X或者Y
来表示两种不同着色
第一个不动置换
一阶循环有三个
写成X加上Y的3次方
下面我们会看到有二阶循环的
甚至有三阶循环的
不要忘记最后要除以对应的
置换个数一共是6个置换
整理出来之后
这些式子整理之后非常简洁
它只剩下了四项也就是
X的3次方
加Y的3次方
加XY平方
加X平方Y
什么意思
实际上这就告诉我们
这样一个三角形
它有多少种不同的连边方式
实际上只有这四种
对应的要么三条边都连
要么三条边都不连
要么连两条边
要么连一条边
这就是波利亚定理告诉我们
对于图应该如何进行计数
下面我们就来分析四个顶点的
简单图该如何分析
四个顶点就是
V1 V2 V3 V4
他们对应有向图中
一共有6条边
这6条边实际上要想对于它有的连接
有的不连接
就相当于对完全图的
边进行二着色
而对于顶点所有的运算
都可以用置换来表示
因此对于图的计数问题和交换群
S4是完全一致的
那么我们挨个分析一下
S4上的每个置换
它实际上是对应的点
而边会发生什么样的置换呢
第一个首先顶点不动的时候
自然6条边也都不动
因此一阶循环有6个
这样的个数就只有一个
同样其他的形式下
如果对应的是一个顶点和
另外一个顶点不动
而V1和V2发生互换的话
这时候它的边会
发生变化呢
首先我们会发现这个
V3和V4不动
因此E3也不会发生变化
而V1和V2只是换了
起点的顺序而已
他们的边还是原来自己
因为有两条边是不发生
任何变化的
而对于其他的两条边
这个边就会和这个边重合
而这个边和这个边重合
因此
对于有一个边发生互相交换的话
这种交错的情况
它的边的置换应该写成
1的平方再乘以2的平方
这时候一共有少个不同的置换呢
意味着我们在这里能找到
多少个相邻的点呢
因为是完全图
所以V1可以和其他的
三个不同的顶点
进行完全图的交流
因为一共有6个这样的置换
而接着往下
如果说我们有一个顶点
V1换到V2
V2又换到V4
然后又换回V3
V3又换回1
这时候构成四阶循环
在这样四阶循环中
实际上会发现
一转之后其实
下面这四条边会发生循环操作
而对于上面的两条边
会发现这条边和
这条边发生了互换
对应其他的边也会发生互换
因此对应的个数就是
二阶循环一个
四阶循环一个
这样的选择置换一共有
6种不同的可能性
相当于在6个顶点中选4个
而另外一种顶点的
置换是两两进行交换
两两进行交换的时候我们发现
对于原来的连接边
是没有发生变化的
仍然是一阶循环有两个
剩下的相当于这样三角形的
对角线和高进行互换
这时候我们发现
它对应写成边的形式
就是一阶循环有两个
二阶循环有两个
它的个数相当于在里面
要取对应的对角线的个数
有了这样的思想之后
我们会发现剩下的还有
一种情况我们把它单独拿出来
比如说对于V2这个顶点
如果它不动的情况下
V3 V4他们可以做成
一种三角形底面进行旋转
因此写成顶点的个数置换情况
就是一阶循环有一个
三阶循环有一个
但是从图的角度来看
V2虽然没有动
但是E1 E6 E2他们发生了
循环交互的过程
因此这里是三阶循环
而它的底面也由三阶循环构成
它有3条边构成了
分别可以循环的结构
一共有多少个这样的情况呢
我们会发现
这里我们实际上去选择
相应的顶点个数
而同时他们的顶角又有正负
120度之分
因此我们会发现一共是
2乘以4个
我们把上面的式子完全联立起来
比如说一阶循环是
X加上Y的六次方
二阶循环是X加上Y的平方乘以X
平方加上Y平方的对应的系数
因为符合这样结构的有9个
因此是9累乘在这里
还有剩下的8个
这3个对应的情况
三阶循环有两个
写出来是这样的式子
这其中我们需要把所有
对应置换的情况数出来
一共是24个
数出来之后就可以直接算
PXY对应的母函数形式
就是这么多
我们把对应的母函数展开之
后发现其实对于一个
简单图进行着色
它的母函数就写成
X的6次方加X5Y
加上2XY
加上3X三次方Y三次方
加上2倍X平方Y四次方
加上XY五次方
加上Y六次方
这样一个式子表达是什么意思呢
表达的就是
说对于全部都着边的话
有一种情况
对于有四条边
另外一条边没有的情况下
它有这么多情况
所以我们可以把所有的
着色方案全部都拿出来
比如说在这里我们就可以看到
对于所有的四个顶点着色方案
无非就是这么多种
如果我们不光求简单图
我们如果想要找对于
有向图来说有多少种不同的构型呢
我们还是拿四个顶点为例
求四个顶点不同构
的有向图的个数
这时候发现边是可以有方向的
可以出也可以入
因为对于四个顶点
它的边数已经变成了12条
因为每个顶点可以出去有3条
可以回来有3条
这时候对应的边就不是像刚才
简单图那样简单了
我们要仔细的分析
同样我们还要从顶点置换里出发
分析有相边的置换
如果顶点单个不动的话
对于十二条边自然也不动
因此也是一阶循环的12次方
而同样如果有两个点不动
其中两个进行互换的话
这时候我们会发现和
原来的简单图类似
如果一条边不动
V1和V2它们之间
没有发生任何的变化
剩下的这两个进行了变化
实际上不动的边就只有
V1和V2之间的
两条边是不动的
剩下的这些都会发生两两交换
因此除了V1 V2之间的
两条边
还剩下10条边
每条边是两两互换
因此是二阶循环有五个
而对于一共有多少个
这样的循环呢
我们会发现实际上对应的就是
求这里面完全四个顶点中
任取两个的组合数有多少
就是6个
接着我们再往下
可以是四个顶点
不停的发生变化
V1变V2
V2变V3
V3变V4
依此类推
构成的四阶循环有一个
每一次旋转实际上
它也就是对应的四条边
发生了变化
而一共多少组这样的4条边呢
根据位置和方向的不同
它应该有3组这样的四条边
因此四阶循环有三个
同样我们也是有
6个不同的选择置换
同样还有两两进行交换
V1和V2进行交换
V3和V4进行交换
我们发现不仅V1和
V2之间的边发生了变化
同时原来V1原来连接
V3的也会变到这边来
所以他们也会有两两置换
一共有6组
同样怎么去选择他们有
多少个不同的呢
一共有3个
接着往下
有一个顶点不动
剩下的三个顶点发生交换的时候
对应的相当于从这个点到
V2 V4 V3对应的边
全部要进行轮换
出边也要进行轮换
而底面上
V2 V3
V4之间也是三个三个一组
因此一共有4组
而它一共有两种不同的角度
对应于有4个不同的选择
因此它应该有2乘以4是8个
我们可以把它写成母函数的形式
第一个就是一阶循环的12次方
x加y的12次方
再加上6乘以
X加上Y的平方
乘以X的平方加
Y平方5次方
依此类推
别忘了最后还要除以置换的个数24个
我们通过展开式想去求X平方项
以及Y的10次方项的系数
它代表的是什么
它代表如果用X表示对应有边的话
Y代表无边的话
那意味着着用两条有向边
去连接四个顶点
有多少种不同的可能性
这里我直接代到里面
去求X平方Y10次方的系数
在第一项中
确实有
从12项中要选出两个X
10个Y
因为是12阶层除
2阶层 10阶层
对于这里我们对应的是如果是
第一项中取了对应的X平方
它两项就必须都要取
剩下的这里面就只有
5个Y平方来取了
因此它有一个
后面的一种情况有可能
是在这里面取了某一项
是X的平方项
因此它是5的阶层除以4阶层
而它有6个
因为累乘进来就可以
这里面也同样可以
存在X平方Y的10次方
意味着从6个里面
选择其中一个选择是x平方
而在这一项中每一项
都是X的3次方
因为它不会产生X的
平分项Y的10次方项
而这一项也一样
它必须是它必须是X的4次方
也不会存在X的平方Y的10次方
这时候我们把所有的
式子累加在一起
除以24
答案是5
也就是说如果有两条有项边
对于四个顶点进行连接
就只有5种不同的构型
-什么是组合数学
--什么是组合数学
--讨论题
-最精巧的排列——幻方
--幻方
-漫谈组合数学--最精巧的排列——幻方
-苦难的羊皮纸卷
--羊皮纸卷
-苦难的羊皮纸卷--作业
-你的手机密码安全吗
-漫谈组合数学--你的手机密码安全吗
-暴力枚举和抽象转换
--世界杯引出的问题
--世界杯引出的问题--练习
--一一对应
--七桥问题
--小结
--讨论题
-大家谈组合数学(1)
--采访武永卫老师
-第一周作业
--作业说明
--H
--U
--G
--作业讨论区说明
-第一周演示程序
--程序讨论区说明
--幻方生成器
--换方计数
--屏幕解锁方案数
--欧拉路计数
--共享程序
-加减乘除来计数
--计数的基本法则
-排列还是组合
--排列还是组合
--小乒乓球的组合之旅--排列还是组合
-各种各样的排列
--圆排列和项链排列
--圆排列和项链排列--习题
--多重排列
--多重排列--练习
-多样的组合
--可重组合
--不相邻组合
--小乒乓球的组合之旅--多样的组合
-钟声里的全排列
--钟声里的全排列
--钟声里的全排列
--字典序法
--SJT算法
-第二周作业
--H
--U
--G
--思考题
--公式测试
--作业讨论区说明
-第二周演示程序
--程序讨论区说明
--全排列生成
--组合生成器
--共享程序
-参考资料:Stirling估计式
-母函数是函数的母亲吗
--母函数的定义(1)--练习
--母函数的定义(2)--练习
-母函数的简单应用
--初识母函数--母函数的简单应用
-整数拆分
--整数拆分(1)
--整数拆分(2)
-Ferrers图像
--Ferrers图像--作业
-母函数与递推关系
--母函数能做什么
--偶数个5怎样算
--母函数小结
-大家谈组合数学(2)
-第三周作业
--H
--U
--G
--思考题
--作业讨论区说明
-第三周演示程序
--程序讨论区说明
--整数拆分
--汉诺塔
--共享程序说明
-Fibonacci数列
--线性常系数递推关系--Fibonacci数列
-Fibonacci数列的应用
--桌布魔术
--桌布魔术--练习
--艾略特波浪曲线
-线性常系数齐次递推关系
--定义
--特征多项式
--线性常系数递推关系--线性常系数齐次递推关系
-说“数”解题
-第四周作业
--H
--U
--G
--GT思考题
--作业讨论区说明
-第四周演示程序
--程序讨论区说明
--程序共享说明
-爆笑花絮
--爆笑花絮
-参考资料:K线分析中的Fibonacci 相关理论
-Catalan数
--计算机界的精灵
--神奇的序列--Catalan数
-指数型母函数
--指数型母函数
--神奇的序列--指数型母函数
-错排
--错排1
--错排2
--神奇的序列--错排
-Stirling数
--神奇的序列--Stirling数
-母函数小结
--母函数小结
-大家谈组合数学(3)
-第五周作业
--H
--U
--G
--思考题
--作业讨论区说明
-第五周演示程序
--讨论区说明
--Catalan数
--程序共享
-且容且斥
--容斥原理
--容斥原理的证明
--容斥原理和鸽巢原理--且容且斥
-容斥原理的精妙
-回忆过去,容斥新解
--容斥原理和鸽巢原理--回忆过去,容斥新解
-鸽子抢巢
--鸽巢原理
--鸽巢原理--练习
--鸽巢原理的应用(1)--练习
-看得见摸得着的鸽巢
--韩信点兵
--中国剩余定理
--容斥原理和鸽巢原理--看得见摸得着的鸽巢
-6人行和Ramsey数
--6人行
--Ramsey数
--小结
-第六周作业
--H
--U
--G
--GT
--作业讨论区说明
-第六周演示程序
--讨论区说明
--程序共享说明
-可以转的世界
--可以转的世界
--可以转的世界--练习
--伽罗华与群
--群的定义
--群的定义--练习
--群的一些概念
-置换群
--置换群
--群--置换群
--共轭类
--对换
--对换--练习
--置换群的应用
-Burnside引理
--着色问题的等价类
--Burnside引理--作业
-闲话群
-第七周作业
--H
--U
--G
--作业讨论区说明
-Burnside引理的困境
-从Burnside到Polya
--Polya定理
-立方体旋转
--立方体旋转(1)
--立方体旋转(2)
--立方体旋转--作业
--立方体旋转(3)
--立方体旋转--作业
--立方体旋转(4)
-母函数型Polya定理
--Polya定理--母函数型Polya定理
-图的计数
--图的计数
-总结
--本章小结
-第八周作业
--H
--U
--G
--GT
--作业讨论区说明
-大家谈组合数学(4)
--采访黄连生老师
-组合之美
--组合之美之计数
-组合之美之线性常系数递推关系
-组合之美之多样的序列
-组合之美之鸽巢原理
-组合之美之转动群与染色
-采访邹欣
--采访邹欣1
--采访邹欣2
-知识点串串烧
--知识点串串烧
-期末测验--期末测验