当前课程知识点:组合数学 > 漫谈组合数学 > 暴力枚举和抽象转换 > 七桥问题
下面呢给大家介绍一个问题
是一个非常有名的叫做哥尼斯堡七桥问题
哥尼斯堡是普鲁士一个非常景色迷人的城市
这个城市呢实际上充满了魅力
如果大家了解一下它的历史会发现
有很多的伟大的数学家和哲学家都出生于此
哲学家康德以及数学学家哥德巴赫
都是这里面出生的
这里所谓人杰地灵 尤其神奇的地方是
有一条河穿过了哥尼斯堡
并且这条河在城区里形成了两条支流
把整个城市分成了四块
人们为了在岛屿和城市之间进行穿梭
所以在这个桥上一共建了七座桥
而这七座桥的分布 但是发现非常有意思
所以呢在哥尼斯堡
这里的人们就有这样一个游戏
他们散步的时候走在这七座桥上
就想我这七座桥相互似乎都连在一起
那有没有可能我走完所有的桥不重复
而遍历所有的七座桥呢
这就是有名的哥尼斯堡七桥问题
大家一看到这里就想
不就是挨个挨个的走桥嘛
我用暴力枚举把它所有的排列全部排出来
它既然说是不重复的
那我无非就是12345677456321不同的排列嘛
七个数的排列有多少种呢
7的阶乘5040种方案
但是在这里面却有很多不可行的解
比如说从这个桥不能直接到另外一个桥
这样的排列就是一个不合理的解
那么人家说那我就挨个走完吧 5040种方案
如果你一天走一个方案的话
你得走13年才能走完哪
这个问题成为了哥尼斯堡大家闲暇时
不停去探索的一个问题
这个时候有几位大学生觉得这个问题很有意思
但是呢他们发现好像怎么都不可能
找到一个可行的解
于是他们就效仿哥德巴赫给欧拉写了一封信
欧拉绝对是大家 他尝试了几次发现
好像没有可以的方案
于是他转换了思路
他觉得是不是也许根本就不可能
无重复的走完这七座桥呢
欧拉仅仅花了几天的时间就解决了这个难题
他的答案是0种方案
欧拉他是怎么做到的呢
他并没有挨个去枚举呀
他呢也甚至没有把所有的桥标上1234567
他做了一个伟大的尝试
他把七座桥变成了一张图
他把它们之间连接的陆地作为了点
而每座桥就是点与点之间的边
这七条边构成的图
正好对应哥尼斯堡七桥问题
如果想要无重复的走完这七座桥
实际上就是相当于我们在这样一个图上
能不能一笔画出所有的边呢
欧拉做了一个这样的抽象 非常的精妙
他把原来的那个问题变成了图
同时他又转化成了一个一笔画的问题
欧拉写了一篇论文非常有名
它被称为是拓扑学的开端
他当年在1736年发表了有关图论的
全世界第一篇论文
也就是哥尼斯堡七桥问题
他不仅仅进行了抽象
同时他还证明了如果在一张图上
你想要一笔画出来所有边的话
他的充分必要条件是什么
首先你的节点要连通
另外他把所有的点分成了两类
根据边的不同如果一个点连接的是奇数条边
就被称为奇数点
如果它连接的是偶数条边就被称为偶数点
那么一张图它能够一笔画完
它的充要条件就是
奇数点的个数要么是0 要么是2
我们回头来看一下哥尼斯堡七桥问题的图
是不是满足刚才说到的充要条件呢
在这张图中一共有4个节点
每个节点要么连接了三条边
要么连接了5条边
所以可以看到4个点全部都是奇数点
那么充要条件说到
要想一笔完全画出来这张图
奇数点最多0个或者2个
显然这七桥问题里面是不满足充要条件的
所以欧拉可以断言不用再走13年了
没有任何一种可行方案
可以无重复的遍历这七座桥
随着时间的流逝
渐渐七桥问题已经渐渐淡化了
但是故事还在继续
有一些桥因为年久失修了已经完全退役了
这时候我们再回头看图发生了变化
比如我们把这上面一角的这条边去掉
这时候我们发现奇数点少了两个
只剩下两个奇数点了
这时候就满足了欧拉提出的
有关一笔画的充要条件
那么既然有了可行的方案
那么不妨这样想
那到底有多少种不同的方法
能够一次性地遍历这六座桥呢
这个问题似乎又把欧拉的问题进一步地深化了
那么在欧拉的论文里面
不仅说了一笔画的充要条件
而且他给出了这样一个定理
他说要想一笔画
那么你就奇数点有可能是0个
意味着所有的点都是偶数点
当所有的点都是偶数点的时候
你要完成一笔画
就可以从任何一个偶数点出发
最终呢回到这个偶数点
如果你要是有两个奇数点要想完成一笔画
那必然是从其中一个奇数点
最终回到另外一个奇数点
有了这样两个条件我们发现
想要找到所有的遍历六桥的方案
没有必要再一个一个全部枚举出来了
因为在这个条件中我们知道
如果奇数点只有两个
那么它必然是从一个奇数点不停地遍历
最终走到了另一个奇数点
其实在计算机算法领域
这种无重复地去遍历所有边
就是一种特殊的问题
而且这个问题以欧拉命名
称这种轨迹称为欧拉路
那么要找到一共有多少条欧拉路呢
实际上是需要同学们
编写一个高速有效的算法的
这时候我们就会发现
其实本质上我们还是在枚举
但是好像没那么暴力了
传统意义上我们说暴力枚举就要
把所有的可能方案全部都拿出来
但是这里面我们因为有了欧拉的工作
我们用欧拉的定理就可以逐步逐步地进行推理
同时发现这样的枚举过程变得轻松自然了
所以可以发现枚举虽然是计数的基本法则
但是真正让它强大起来的还是需要抽象的功力
而且在很多情况下缺了计算机
你的枚举能力是非常有限的
组合数学就是运用了这样的思维
能够告诉计算机如何用抽象的方法
把你枚举的过程变得更加的精巧更加的简洁
这也就是组合数学的魅力所在
-什么是组合数学
--什么是组合数学
--讨论题
-最精巧的排列——幻方
--幻方
-漫谈组合数学--最精巧的排列——幻方
-苦难的羊皮纸卷
--羊皮纸卷
-苦难的羊皮纸卷--作业
-你的手机密码安全吗
-漫谈组合数学--你的手机密码安全吗
-暴力枚举和抽象转换
--世界杯引出的问题
--世界杯引出的问题--练习
--一一对应
--七桥问题
--小结
--讨论题
-大家谈组合数学(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
-知识点串串烧
--知识点串串烧
-期末测验--期末测验