图论的起点——七桥问题

server/2025/1/19 21:59:21/

普瑞格尔河从古堡哥尼斯堡市中心流过,河中有小岛两座,筑有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/server/159732.html

相关文章

AI实验室copilot自动化科研,AMD联手约翰霍普金斯大学:成本节约84%!

在科学研究领域,特别是机器学习的探索过程中,资源的高效利用和时间管理一直是研究者面临的重要挑战。随着大型语言模型(LLMs)的发展,自动化科学研究成为可能,但现有的研究工具通常只能处理研究过程的单个环…

Flink概述

一、Flink是什么 二、Flink特点 三、Flink vs SparkStreaming 表 Flink 和 Streaming对比 Flink Streaming 计算模型 流计算 微批处理 时间语义 事件时间、处理时间 处理时间 窗口 多、灵活 少、不灵活(窗口必须是批次的整数倍) 状态 有 …

数智化转型 | 星环科技Defensor 助力某银行数据分类分级

在数据驱动的金融时代,数据安全和隐私保护的重要性日益凸显。某银行作为数字化转型的先行者,面临着一项艰巨的任务:如何高效、准确地对分布在多个业务系统、业务库与数仓数湖中的约80万个字段进行数据分类和分级。该银行借助星环科技数据安全…

精度论文:【Focaler-IoU: More Focused Intersection over Union Loss】

Focaler-IoU: 更聚焦的交并比损失 Focaler-IoU: More Focused Intersection over Union Loss Focaler-IoU: 更聚焦的交并比损失I. 引言II. 相关工作III. 方法IV. 实验V. 结论 原文地址:官方论文地址 代码地址:官方代码地址 摘要——边界框回归在目标检…

数据库:Redis命令行帮助解释

Redis命令&#xff1a; Redis-cliredis-serverredis-benchmark 下面是redis-cli命令行接口的帮助信息&#xff0c;该接口用于与Redis服务器进行交互。以下是参数的说明&#xff1a; 通用选项&#xff1a; -h <主机名>: 指定Redis服务器的主机名&#xff08;默认为127…

基于金融新闻的大型语言模型强化学习在投资组合管理中的应用

“Financial News-Driven LLM Reinforcement Learning for Portfolio Management” 论文地址&#xff1a;https://arxiv.org/pdf/2411.11059 摘要 本研究探索了如何通过将大语言模型&#xff08;LLM&#xff09;支持的情感分析融入强化学习&#xff08;RL&#xff09;中&#…

使用 Tailwind CSS 的几点感触

大家好&#xff0c;我是大澈&#xff01; 偶然看到了js前端样式库的排名&#xff0c;Tailwind CSS 以大比例的优势&#xff0c;稳稳占据第一的位置。 对于 Tailwind CSS 我之前用的很少&#xff0c;我一般都是使用自定义原子css写法&#xff0c;感觉更自由更舒服&#xff0c;而…

力扣 全排列

回溯经典例题。 题目 通过回溯生成所有可能的排列。每次递归时&#xff0c;选择一个数字&#xff0c;直到选满所有数字&#xff0c;然后记录当前排列&#xff0c;回到上层时移除最后选的数字并继续选择其他未选的数字。每次递归时&#xff0c;在 path 中添加一个新的数字&…