图论的起点——七桥问题

embedded/2025/1/20 12:47:51/

普瑞格尔河从古堡哥尼斯堡市中心流过,河中有小岛两座,筑有7座古桥,哥尼斯堡人杰地灵,市民普遍爱好数学。1736年,该市一名市民向大数学家Euler提出如下的所谓“七桥问题”:

从家里出发,7座桥每桥恰通过一次,再回到家里,是否可能?

事实上,人们此前已经反复试验多次,不管怎样游行,亦未成功地实现美桥恰过一次的旅行。但又无人严格证明七桥问题的答案是否定的。

欧拉首先想到的是用穷举法, 就是把所有的走法都一一列出来,然后再一个一个的验证是否可行。 但是他马上发现这样做太麻烦了, 因为对七座桥的不同走法就有7!=5040种,逐一检验太耗时费力了,况且这样的方法没有通用性。如果桥的位置或桥的数量发生变化,岂不又得重新检验? 看来此法不可行。

Euler把两岸分别用C和D两个点来表示,两岛分别用A与B两点来表示。A、B、C、D各点的位置无关紧要,仅当两块陆地之间有桥时,在上述相应的两个点间连有一段曲线段,此曲线段的曲直长短也无关紧要,于是得到图:

欧拉在这里是把实际问题抽象成纯数学模型来进行研究从而获得了解决一类问题的方法。所谓抽象就是把研究的事物从某种角度看待的本质属性抽取出来 进行考察的思维方法。在数学中,例如在由“一个人”“一头羊”“一只猴”或者一个其他什么具体事物抽象出相应的数学概念“1”时,我们所注意的只是这些对象在数量上的共同特征,即量的多少,而根本不去考虑所说对象的质的内容(是人是羊是猴还是别的什么东西)。又如哥尼斯堡七桥问题中,一笔画问题便是从七桥问题中抽象出来的数学模型。在该模型里仅仅保留了一次过七桥的基本属性而舍弃了其他一切属性。

通过数学建模,已经把实际问题转化成了数学问题。这时欧拉注意到,如果一个图形能一笔画成,那么除去起点和终点外,其他的点都是经过点。而经过点是有进有出的点,即有一条线进这个点,就一定有一条线出这个点。不可能有进无出,如果有进无出,它就是终点; 也不可能有出无进,如果有出无进,它就是起点。因此,在经过点进出的线总数应该是偶数。我们称在一个点进出线的总数是偶数的点为偶点; 总数为奇数的点称为奇点。如果起点和终点是同一个点,那么它也属于有进有出的点,它也是偶点,这样图上的点全是偶点。如果起点和终点不是同一个点,那么它们必定是奇点。 因此,能够一笔画的图形最多只有两个奇点。

1736年,欧拉证明了自己的猜想,一次不重复走完七座桥是根本不可能的。随即他发表了“一笔画定理”:

一个图形要能一笔画完,必须符合以下两个条件: 

(1)图形是封闭连通的;

(2)图形中的奇点个数为 0 或 2;

七桥问题中的四个点全是奇点,当然不能一笔画,即不可能一次无重复地走完七座桥。 一般地说,如果图中的点全是偶点,那么可以任意选择一个点作为起点,当然终点与起点重合,能一笔画成;如果图中有两个奇点,那么可以任意选一个奇点作为起点,另一个奇点为终点,可以一笔画成。

欧拉的这个研究成果,开创了图论和拓扑学这两门新的学科。这两门学科在计算机科学中有着广泛的应用。由此可见,只要善于用数学的眼光、数学的方法去观察事物,分析问题,就能把生活中的一些实际问题转化为数学问题,并用数学的方法来处理和解决。


http://www.ppmy.cn/embedded/155490.html

相关文章

基于本地消息表实现分布式事务

假设我们有一个电商系统,包含订单服务和库存服务。当用户下单时,需要在订单服务中创建订单,同时在库存服务中扣减库存。这是一个典型的分布式事务场景,我们需要保证这两个操作要么都成功,要么都失败,以保证数据的最终一致性。 项目结构: 订单服务(Order Service)库存服务(Inv…

基于Springboot实现旅游网站系统开发

项目介绍 在介绍文章之前呢,小伙伴们需要掌握关于咱们前后端知识点,我整理了几个课程,可以去学习: 课程1-java和vue前后端分离项目实战 课程2-HTML5入门级开发 课程3-vue入门级开发教程 课程4-CSS入门级开发 里边的老师也很敬业&…

面试-业务逻辑2

应用 给定2个数组a、b,若a[i] b[j],则记(i,j)为一个二元数组,求具体的二元数组及其个数。 实现 a input("请输入数组a的元素个数:") # print(a) a_list list(map(int, input("请输入数组a的元素,…

25/1/15 嵌入式笔记 初学STM32F108

GPIO初始化函数 GPIO_Ini:初始化GPIO引脚的模式,速度和引脚号 GPIO_Init(GPIOA, &GPIO_InitStruct); // 初始化GPIOA的引脚0 GPIO输出控制函数 GPIO_SetBits:将指定的GPIO引脚设置为高电平 GPIO_SetBits(GPIOA, GPIO_Pin_0); // 将GPIO…

2025年1月19日(振动控制研究历史)

振动控制研究的历史可以追溯到19世纪末,随着工程和物理学的快速发展,特别是在机械、土木和航空工程领域。以下是振动控制研究历史的一些关键节点: 1. 早期阶段 (19世纪末 - 20世纪初) 在19世纪末,工程师开始注意到机械和建筑物的…

MyBatis动态SQL标签的案例

1. 使用<if>进行条件查询 假设我们有一个用户表users&#xff0c;包含字段id, name, age。我们要根据名字和年龄来查找用户&#xff0c;但这两个条件都是可选的。 <select id"findUsers" parameterType"map" resultType"User">SEL…

今天你学C++了吗?——C++中的STL

♥♥♥~~~~~~欢迎光临知星小度博客空间~~~~~~♥♥♥ ♥♥♥零星地变得优秀~也能拼凑出星河~♥♥♥ ♥♥♥我们一起努力成为更好的自己~♥♥♥ ♥♥♥如果这一篇博客对你有帮助~别忘了点赞分享哦~♥♥♥ ♥♥♥如果有什么问题可以评论区留言或者私信我哦~♥♥♥ ✨✨✨✨✨✨ 个…

嵌入式知识点总结(一)-C/C++关键字

针对于嵌入式软件杂乱的知识点总结起来&#xff0c;提供给读者学习复习对下述内容的强化。 目录 1.C语言宏中"#“和"##"的用法 1.1.(#)字符串化操作符 1.2.(##)符号连接操作符 2.关键字volatile有什么含意?并举出三个不同的例子? 2.1.并行设备的硬件寄存…