当前课程知识点:组合数学 >  漫谈组合数学 >  暴力枚举和抽象转换 >  七桥问题

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

七桥问题在线视频

七桥问题

下一节:小结

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

七桥问题课程教案、知识点、字幕

下面呢给大家介绍一个问题

是一个非常有名的叫做哥尼斯堡七桥问题

哥尼斯堡是普鲁士一个非常景色迷人的城市

这个城市呢实际上充满了魅力

如果大家了解一下它的历史会发现

有很多的伟大的数学家和哲学家都出生于此

哲学家康德以及数学学家哥德巴赫

都是这里面出生的

这里所谓人杰地灵 尤其神奇的地方是

有一条河穿过了哥尼斯堡

并且这条河在城区里形成了两条支流

把整个城市分成了四块

人们为了在岛屿和城市之间进行穿梭

所以在这个桥上一共建了七座桥

而这七座桥的分布 但是发现非常有意思

所以呢在哥尼斯堡

这里的人们就有这样一个游戏

他们散步的时候走在这七座桥上

就想我这七座桥相互似乎都连在一起

那有没有可能我走完所有的桥不重复

而遍历所有的七座桥呢

这就是有名的哥尼斯堡七桥问题

大家一看到这里就想

不就是挨个挨个的走桥嘛

我用暴力枚举把它所有的排列全部排出来

它既然说是不重复的

那我无非就是12345677456321不同的排列嘛

七个数的排列有多少种呢

7的阶乘5040种方案

但是在这里面却有很多不可行的解

比如说从这个桥不能直接到另外一个桥

这样的排列就是一个不合理的解

那么人家说那我就挨个走完吧 5040种方案

如果你一天走一个方案的话

你得走13年才能走完哪

这个问题成为了哥尼斯堡大家闲暇时

不停去探索的一个问题

这个时候有几位大学生觉得这个问题很有意思

但是呢他们发现好像怎么都不可能

找到一个可行的解

于是他们就效仿哥德巴赫给欧拉写了一封信

欧拉绝对是大家 他尝试了几次发现

好像没有可以的方案

于是他转换了思路

他觉得是不是也许根本就不可能

无重复的走完这七座桥呢

欧拉仅仅花了几天的时间就解决了这个难题

他的答案是0种方案

欧拉他是怎么做到的呢

他并没有挨个去枚举呀

他呢也甚至没有把所有的桥标上1234567

他做了一个伟大的尝试

他把七座桥变成了一张图

他把它们之间连接的陆地作为了点

而每座桥就是点与点之间的边

这七条边构成的图

正好对应哥尼斯堡七桥问题

如果想要无重复的走完这七座桥

实际上就是相当于我们在这样一个图上

能不能一笔画出所有的边呢

欧拉做了一个这样的抽象 非常的精妙

他把原来的那个问题变成了图

同时他又转化成了一个一笔画的问题

欧拉写了一篇论文非常有名

它被称为是拓扑学的开端

他当年在1736年发表了有关图论的

全世界第一篇论文

也就是哥尼斯堡七桥问题

他不仅仅进行了抽象

同时他还证明了如果在一张图上

你想要一笔画出来所有边的话

他的充分必要条件是什么

首先你的节点要连通

另外他把所有的点分成了两类

根据边的不同如果一个点连接的是奇数条边

就被称为奇数点

如果它连接的是偶数条边就被称为偶数点

那么一张图它能够一笔画完

它的充要条件就是

奇数点的个数要么是0 要么是2

我们回头来看一下哥尼斯堡七桥问题的图

是不是满足刚才说到的充要条件呢

在这张图中一共有4个节点

每个节点要么连接了三条边

要么连接了5条边

所以可以看到4个点全部都是奇数点

那么充要条件说到

要想一笔完全画出来这张图

奇数点最多0个或者2个

显然这七桥问题里面是不满足充要条件的

所以欧拉可以断言不用再走13年了

没有任何一种可行方案

可以无重复的遍历这七座桥

随着时间的流逝

渐渐七桥问题已经渐渐淡化了

但是故事还在继续

有一些桥因为年久失修了已经完全退役了

这时候我们再回头看图发生了变化

比如我们把这上面一角的这条边去掉

这时候我们发现奇数点少了两个

只剩下两个奇数点了

这时候就满足了欧拉提出的

有关一笔画的充要条件

那么既然有了可行的方案

那么不妨这样想

那到底有多少种不同的方法

能够一次性地遍历这六座桥呢

这个问题似乎又把欧拉的问题进一步地深化了

那么在欧拉的论文里面

不仅说了一笔画的充要条件

而且他给出了这样一个定理

他说要想一笔画

那么你就奇数点有可能是0个

意味着所有的点都是偶数点

当所有的点都是偶数点的时候

你要完成一笔画

就可以从任何一个偶数点出发

最终呢回到这个偶数点

如果你要是有两个奇数点要想完成一笔画

那必然是从其中一个奇数点

最终回到另外一个奇数点

有了这样两个条件我们发现

想要找到所有的遍历六桥的方案

没有必要再一个一个全部枚举出来了

因为在这个条件中我们知道

如果奇数点只有两个

那么它必然是从一个奇数点不停地遍历

最终走到了另一个奇数点

其实在计算机算法领域

这种无重复地去遍历所有边

就是一种特殊的问题

而且这个问题以欧拉命名

称这种轨迹称为欧拉路

那么要找到一共有多少条欧拉路呢

实际上是需要同学们

编写一个高速有效的算法的

这时候我们就会发现

其实本质上我们还是在枚举

但是好像没那么暴力了

传统意义上我们说暴力枚举就要

把所有的可能方案全部都拿出来

但是这里面我们因为有了欧拉的工作

我们用欧拉的定理就可以逐步逐步地进行推理

同时发现这样的枚举过程变得轻松自然了

所以可以发现枚举虽然是计数的基本法则

但是真正让它强大起来的还是需要抽象的功力

而且在很多情况下缺了计算机

你的枚举能力是非常有限的

组合数学就是运用了这样的思维

能够告诉计算机如何用抽象的方法

把你枚举的过程变得更加的精巧更加的简洁

这也就是组合数学的魅力所在

组合数学课程列表:

漫谈组合数学

-什么是组合数学

--什么是组合数学

--讨论题

-最精巧的排列——幻方

--幻方

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

-苦难的羊皮纸卷

--羊皮纸卷

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

-你的手机密码安全吗

--你的手机密码安全吗

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

-暴力枚举和抽象转换

--世界杯引出的问题

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

--一一对应

--七桥问题

--小结

--讨论题

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

-知识点串串烧

--知识点串串烧

期末测验

-期末测验--期末测验

七桥问题笔记与讨论

也许你还感兴趣的课程:

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