当前课程知识点:组合数学 >  群 >  Burnside引理 >  着色问题的等价类

返回《组合数学》慕课在线视频课程列表

着色问题的等价类在线视频

着色问题的等价类

下一节:Burnside引理

返回《组合数学》慕课在线视频列表

着色问题的等价类课程教案、知识点、字幕

我们刚才一直都在讲置换群

而置换群的对象无非就是一些文字

那么再回到我们本节课一开始

提出的问题

对应于这个正方形

我们顶点要用两种颜色

进行着色的话

会有多少种不同的方案

这时候其实我们仔细研究一下

如果这样一些图形摆在这里的话

它对应于不同的位置着不同的颜色

应该有多少个呢

实际上它看到的是一些图像

何为图像

就是像照片一样摆在这儿

我们看见的

它不能动

那么图像有多少个呢

我们每一个顶点都有两个选择

一共是4个顶点

所以是2的4次方种不同的图像

而我们要求什么

我们要求的是结构

结构对应的实际上叫做着色方案

也就是说如果我们经过外力

进行变换

比如说旋转翻转

原来这个图像能够通过变换

产生另外一个图像

那么这两个图像我们认为是等价的

我们要求什么

我们要求的就是一共有多少个

不同的等价类

那么这里面有几个概念

首先我们经过旋转以后

要求它的内部结构不发生变化

而所谓置换

什么叫做置换呢

我们说90度旋转

180度旋转

它就是一个置换

通过置换之后

它的图像就会变换成另外一个图像

那么我们现在研究的群

就应该是这些图像所构成的置换群

比如说我们给这所有的图像

16个图像都发生了一些标号

从1一直标到了16

这时候我们对应的一些外力的运作

比如说旋转90度

那么2号图像就变成了3号

3号就变成的4号

那么依次往下

这时候我们会发现

我们的图像作为一些元素

构成了置换群

而置换群又给我们作出了

很多的不同的等价类

那么我们要求的着色方案是什么呢

就应该是这些图像在

置换群中的作用下产生的等价类

有了这个概念之后我们来分析一下

实际上我们对应的这四个顶点的

着色问题

无非在求它一共有多少个等价类嘛

那么假如说我们现在考虑的置换

只考虑对应的是角度的旋转

而不考虑翻转

那这时候该怎么分析呢

首先我们要把置换拿出来

置换有多少个呢

我们可以考虑四种不同的旋转

构成的置换群包括它旋转0度

旋转0度

那么每一个图像还是

它的自己的样子

因此旋转0度的时候

它写出的置换就是单个单个的

一共是16个一阶循环

如果我说要旋转90度的话

旋转90度的时候

我们发现第一个图像旋转90度

还是它自己

而对应于2变成3

3变成4

4变成5

它们构成了一个四阶的循环

而6这个图像转的90度以后

就会变成7

因此6和7构成了一个2阶循环

同样8 9 10 11以及12 13 14 15

它们分别是4阶循环

接着16是个1阶循环

这就是对应的第二个置换

我们用P1来表示

那么接着旋转180度构成了

另外一个置换

对应于第一个元素

图像它是不变的

而对应于2

它转了180度

到了4

3转了180度

它到了5

而6转了180度还是它自己

7转了180度也还是它自己

依次类推

同样我们可以分析旋转270度的

270度的时候

我们用p3来表示的话

它就有这样一个对应的置换表示

我们来分析所有这样的置换

我们会发现

何为等价类

如果某一个置换能够把一个图像

转换成另外一个图像

那么这两个图像就属于同一个等价类

那么同时我们还会发现有一些

很有玄妙的地方

有一些置换

它虽然在这个图像上转了

但是没有发生任何的变化

比如说这里旋转180度

对于图像6来说

转了180度

还是它自己

没有发生任何的变化

因此我们会发现某些置换

它实际上对某一些图像

是不起作用的

我们给这种特别的置换取一个名字

叫做k不动置换类

英文呢 更形象

就叫stabilizer 把他stable住了

那什么意思呢

对应于G来说

它是1到n上的所有的置换

那么它有一个子群

这个子群也就是它对应于

k这个元素

有一部分的置换在k上

基本没有作用

那么我就称它为k不动置换类

用Zk来表示

举个简单的例子

有这样一个置换群

对应于G等于单位元e

以及1换2

3 4不动

3换4

1 2不动

以及1 2互换

3 4互换

这就是一个最基本的一个置换群

在这个置换群上我们来看

有哪些置换让1不动了

也就是z1等于什么

我们会发现当然单位元是不动的

对应于3和4互换

1和2不动

那么1在这里面也不会发生变化

因此对应于1的不动置换类呢

就包含两个元素

一个是e

一个是(3 4);对应于2它的

不动置换类同样也是e和(3 4)

而对应3呢

Z3也是e (1 2) z4和z3是相等的

这时候我们就分析了

什么叫做k不动置换类

那我们回头再来看对应于这样一个

四个顶点着色的问题

我们会发现它的不动置换类

会有什么样的规律呢

同样我们会看到对应于从p0 p1 p2 p3

这四个操作来说

对于1这样一个图像

谁会让它不动呢

其实我们发现1这个图像不论怎么转

还是它自己

因此它的不动置换类包含了p0 p1 p2 p3

四个元素都在内

而对于对应的下面的这个元素

比如说2来说

谁会让它不变呢

只有p0

对应于转90度

转180度和转270度

都会让它发生变化

因此对应的Z2就包含一个元素

也就是p0

而正好3 4 5它们对应的

不动置换类和2的不动置换类

是完全一样的

那么对应于6和7这样两个元素

我们也会发现Z6有谁呢

有转0度和转180度

因此就是p0和p2

对应于6和7

它的不动置换类也是完全一样的

那么这时候我们就会发现

是不是等价类和不动置换类之间

有一定的关系呢

那我们先看

我们要求的等价类

其实等价类是什么呢

回头还是这样一张图

我们会发现要求的等价类

好象是这个元素经过某些变换

就可以到达另外一个元素

依次它们好象构成了一个

围成的轨道一样

而每一个轨道就对应着一个等价类

因此其实等价类的英文更为形象

它就叫做Orbit

对应于一个等价类

就是一个经过置换的一个轨道

那么所谓等价类也就说对应于1 2 3

一直到n中的数k

如果存在某个置换使得k变成l的话

那么k和l属于同一个等价类

对应于作为的k对应的等价类

我们可以用Ek来表示

我们再看还是这道题

对应的4个顶点着色的话

我们会发现E1有谁呢

E1就是它自己

也就是一个元素

那么对应于E2有谁呢

我们会发现2 3 4 5这四个图像

位于一个轨道上

因此他们属于同一个等价类

那么接着6和7会发现

它们也是彼此可以通过置换达到的

所以6和7属于同一个等价类

那么E6等于E7

一共有两个元素

这时候我们发现

有一个很奇妙的地方

你会发现它的置换以后一共多少个

一共有4个

而对应于1这个元素

它自己的等价类只有一个

有就是E1的个数等于1

但是这时候它的不动置换类

有几个呢

正好4个

而对应于2 3 4 5

它在同一个轨道上一共有4个元素

也就是说E2它对应的个数等于4

而它的不动置换类有几个呢

有一个

再看

6和7

6和7属于同一个等价类

那么E6的个数等于2

而对应于不动置换类有几个呢

两个

2乘以2还等于4

这时冥冥之中是不是有一定的关系

我们会发现

有没有可能Ek的个数乘以Zk的个数

就直接等于置换的个数呢

组合数学课程列表:

漫谈组合数学

-什么是组合数学

--什么是组合数学

--讨论题

-最精巧的排列——幻方

--幻方

-漫谈组合数学--最精巧的排列——幻方

-苦难的羊皮纸卷

--羊皮纸卷

-苦难的羊皮纸卷--作业

-你的手机密码安全吗

--你的手机密码安全吗

-漫谈组合数学--你的手机密码安全吗

-暴力枚举和抽象转换

--世界杯引出的问题

--世界杯引出的问题--练习

--一一对应

--七桥问题

--小结

--讨论题

-大家谈组合数学(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

-知识点串串烧

--知识点串串烧

期末测验

-期末测验--期末测验

着色问题的等价类笔记与讨论

也许你还感兴趣的课程:

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