无人能解的“一笔画”问题,最后被炮弹炸出了答案

作者: 编辑:大琳砸

来源: 果壳少年

发布日期: 2018-07-13

数学家欧拉通过简化地图,将哥尼斯堡的七桥问题转化为图论问题,提出了判断一笔画问题的通用理论。

在现在的地图上,你很难找到哥尼斯堡这个城市,但它可以说是数学史上最著名的堡了。这座城市跨普雷格尔河两岸,河中心有两个小岛。小岛与河的两岸有七条桥连接。这个神奇的构造引起了数学家埃勒的强烈兴趣,他提出了一个问题:在所有桥都只能走一遍的前提下,如何才能把这个地方所有的桥都走遍?这个问题凭借其简单的题干、风骚的设问、复杂的可能性,成功吸引了数学家欧拉的注意。

欧拉的想法是,在岛屿或河岸内部行走的路线实际上并不重要。这样,我们就可以把地图简化成四个区域,它们可以分别用一个点表示,也就是“节点”。这些大黑点就是“节点”。它们之间的线(图论里称为“边”)则代表桥。这样,简化的图使我们比较容易计算每个节点的度,也就是节点之间桥的数量。根据这个问题的设定,一旦有人想要通过一座桥到达一个区域,他就必须通过另一座桥离开。

也就是说,进入节点和离开节点的桥必须是以成对的方式出现的,这意味着连接每个节点的桥的数量一定是偶数,唯一可能的例外是在路程的起点和终点。欧拉甚至发展出了一个通用的理论,适用于存在两个或两个以上节点的图。在这套理论里,每一个边仅经过一次的欧拉路径只可能出现在以下两种情况里。一,当仅有两个节点为奇数度,而其它的节点都是偶数度时。这样,我们就以其中一个拥有奇数度的节点作为起点,另一个作为终点。

二,当所有的节点都是偶数度时。那么,欧拉路径就从同一个位置开始和结束,这被称为欧拉回路。这样看来,四个节点都是奇数度的“七桥问题”——你猜对了吗?

UUID: 04d10e82-fe18-4b70-a431-79497a841a60

原始文件名: /home/andie/dev/tudou/annot/AI语料库-20240917-V2/AI语料库/果壳少年公众号-pdf2txt/2018-2019/2018-07-13_无人能解的“一笔画”问题,最后被炮弹炸出了答案.txt

是否为广告: 否

处理费用: 0.0021 元