当前课程知识点:组合数学 >  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算法

--程序支持与Stirling公式

-第二周作业

--H

--U

--G

--思考题

--公式测试

--作业讨论区说明

-第二周演示程序

--程序讨论区说明

--排列数和组合数的计算

--全排列生成

--组合生成器

--共享程序

-参考资料:Stirling估计式

--Stirling估计式

初识母函数

-母函数是函数的母亲吗

--母函数的定义(1)

--母函数的定义(1)--练习

--母函数的定义(2)

--母函数的定义(2)--练习

-母函数的简单应用

--母函数的简单应用(1)

--母函数的简单应用(2)

--初识母函数--母函数的简单应用

-整数拆分

--整数拆分(1)

--整数拆分(2)

-Ferrers图像

--Ferrers图像

--Ferrers图像--作业

-母函数与递推关系

--母函数能做什么

--Hanoi问题(1)

--Hanoi问题(2)

--偶数个5怎样算

--偶数个5怎样算(2)

--母函数小结

-大家谈组合数学(2)

--科研,找工作与组合数学

-第三周作业

--H

--U

--G

--思考题

--作业讨论区说明

-第三周演示程序

--程序讨论区说明

--整数拆分

--汉诺塔

--共享程序说明

线性常系数递推关系

-Fibonacci数列

--Fibonacci兔子

--Fibonacci恒等式

--线性常系数递推关系--Fibonacci数列

-Fibonacci数列的应用

--桌布魔术

--桌布魔术--练习

--Fibonacci的直接表达式

--Fibonacci优选法

--艾略特波浪曲线

-线性常系数齐次递推关系

--定义

--特征多项式

--母函数与特征多项式

--根据特征多项式求解递推关系通解(1)

--根据特征多项式求解递推关系通解(2)

--线性常系数递推关系--线性常系数齐次递推关系

-说“数”解题

--说“数”解题(1)

--说“数”解题(2)

-第四周作业

--H

--U

--G

--GT思考题

--作业讨论区说明

-第四周演示程序

--程序讨论区说明

--Fibonacci优选法

--Fibonacci数值计算

--程序共享说明

-爆笑花絮

--爆笑花絮

-参考资料:K线分析中的Fibonacci 相关理论

--Fibonacci retracement资料

神奇的序列

-Catalan数

--计算机界的精灵

--Catalan数的直接表达式

--Catalan数的各种实例

--神奇的序列--Catalan数

-指数型母函数

--指数型母函数

--指数型母函数的应用

--神奇的序列--指数型母函数

-错排

--错排1

--错排2

--神奇的序列--错排

-Stirling数

--第一类Stirling数

--神奇的序列--Stirling数

--第二类Stirling数

-母函数小结

--母函数小结

-大家谈组合数学(3)

--采访郭家宝(BYVoid)

-第五周作业

--H

--U

--G

--思考题

--作业讨论区说明

-第五周演示程序

--讨论区说明

--Catalan数

--第二类Stirling数

--程序共享

容斥原理和鸽巢原理

-且容且斥

--容斥原理

--容斥原理的证明

--容斥原理和鸽巢原理--且容且斥

-容斥原理的精妙

--容斥原理的应用(1)

--容斥原理的应用(2)

--容斥原理的应用(3)

-回忆过去,容斥新解

--容斥原理的应用(4)

--容斥原理的应用(5)

--容斥原理的应用(6)

--容斥原理和鸽巢原理--回忆过去,容斥新解

-鸽子抢巢

--鸽巢原理

--鸽巢原理--练习

--鸽巢原理的应用(1)

--鸽巢原理的应用(1)--练习

-看得见摸得着的鸽巢

--鸽巢原理的应用(2)

--韩信点兵

--中国剩余定理

--容斥原理和鸽巢原理--看得见摸得着的鸽巢

-6人行和Ramsey数

--6人行

--Ramsey数

--小结

-第六周作业

--H

--U

--G

--GT

--作业讨论区说明

-第六周演示程序

--讨论区说明

--Find a multiple

--程序共享说明

-可以转的世界

--可以转的世界

--可以转的世界--练习

--伽罗华与群

--群的定义

--群的定义--练习

--群的一些概念

-置换群

--置换群

--群--置换群

--共轭类

--对换

--对换--练习

--置换群的应用

-Burnside引理

--着色问题的等价类

--Burnside引理--作业

--Burnside引理

--Burnside引理的应用

-闲话群

--无处不在的群(1)

--无处不在的群(2)

-第七周作业

--H

--U

--G

--作业讨论区说明

Polya定理

-Burnside引理的困境

--Burnside引理的困境(1)

--Burnside引理的困境(2)

-从Burnside到Polya

--Polya定理

--Polya定理的应用(1)

--Polya定理的应用(2)

-立方体旋转

--立方体旋转(1)

--立方体旋转(2)

--立方体旋转--作业

--立方体旋转(3)

--立方体旋转--作业

--立方体旋转(4)

-母函数型Polya定理

--母函数型Polya定理(1)

--母函数型Polya定理(2)

--母函数型Polya定理(3)

--母函数型Polya定理(4)

--Polya定理--母函数型Polya定理

-图的计数

--图的计数

-总结

--本章小结

-第八周作业

--H

--U

--G

--GT

--作业讨论区说明

-大家谈组合数学(4)

--采访黄连生老师

组合之美

-组合之美

--组合之美之计数

--组合之美之排列组合

--组合之美之多样组合和全排列

-组合之美之线性常系数递推关系

--组合之美之线性常系数递推关系

-组合之美之多样的序列

--组合之美之多样的序列

-组合之美之鸽巢原理

--组合之美之鸽巢原理

-组合之美之转动群与染色

--组合之美之转动群与染色

-采访邹欣

--采访邹欣1

--采访邹欣2

-知识点串串烧

--知识点串串烧

期末测验

-期末测验--期末测验

图的计数笔记与讨论

也许你还感兴趣的课程:

© 柠檬大学-慕课导航 课程版权归原始院校所有,
本网站仅通过互联网进行慕课课程索引,不提供在线课程学习和视频,请同学们点击报名到课程提供网站进行学习。