今天咱们来聊一聊《最强大脑-燃烧吧大脑》第二期的第三题-立体一笔画。
找出从任一顶点出发,一笔不重复,经过所有的棱边,画出的立体多边形。
讲到一笔画,我们先来说下最经典的哥尼斯堡七桥问题。
七桥问题是历史上著名的数学问题之一,它简单有趣,通俗易懂。欧拉解决七桥问题的思路方法对如何用数学解决实际问题有非常好的借鉴意义,同时,欧拉对七桥问题的研究,也成为了拓扑学研究的先声。
18世纪,东普鲁士的首府哥尼斯堡是一座景色迷人的城市,普莱格尔河横贯城区,使这座城市锦上添花,显得更加风光旖旋。这条河有两条支流,在城中心汇成大河,在河的中央有一座美丽的小岛。河上有七座各具特色的桥把岛和河岸连接起来。每到傍晚,许多人都来此散步。人们漫步于这七座桥之间,久而久之,就形成了这样一个问题:能不能既不重复又不遗漏地一次相继走遍这七座桥呢?这就是闻名遐迩的“哥尼斯堡七桥问题”。
数学求解首先完成对实际问题的抽象
七桥问题提出之后引起了当地居民极大的兴趣,他们在不断地尝试寻找着问题的答案。这一个看似简单的问题,却没有一个人能按照要求不重复地走遍这七座桥。这已经成为当地人的一种游戏。
七桥问题也困绕着哥尼斯堡大学的学生们,他们非常想知道这个问题的解。在屡试屡败的情况下,有人提议给当时著名数学家欧拉写了一封信,请他帮助解决这个问题。欧拉看完信后,对这个问题也非常感兴趣。
首先能想到的方法是把走七座桥的走法都列出来,一个一个的试验,但七座桥的所有走法共有7!=5040种,逐一试验将是很大的工作量。
欧拉作为数学家,当然没那样想。欧拉首先做的事是完成对七桥问题的抽象。他在对这个问题的相关情况做了深入的分析之后,他把岛、半岛和两岸陆地看成是桥梁连接的点,那这四个地方可以表示成四个结点,然后再把这七座桥看成是连接结点的七条线,这样七桥问题就被抽象为仅包含点和线的拓扑结构。这样七桥问题就抽象为如下的关系图。这个问题也被人们称为“一笔画”的问题,即:能否笔不离纸,不重复地一笔画完整个图形。
接下来欧拉就集中研究这个图。欧拉想,人们希望找到一条不重复的路线,可是这么多人的尝试都失败了,说不定这样的路线根本就不存在。于是欧拉开始考虑,这种不重复的路线是否存在,存在的解的充分必要条件是什么。经过研究欧拉找到问题的答案。
欧拉发现,能够一笔画的图形必须是连通图。连通图是指图形的各部分都有边相连。但是并不是所有的连通图都可以一笔画的。能否一笔画是由图的奇、偶点的数目来决定的。那么什么叫奇、偶点呢?与奇数条边相连的点叫做奇点;与偶数条边相连的点叫做偶点。
欧拉最终发现的一笔画规律:
1.凡是由偶点组成的连通图,一定可以一笔画成。画时可以把任一偶点为起点,最后一定能以这个点为终点画完此图。
2.凡是只有两个奇点的连通图(其余都为偶点),一定可以一笔画成。画时必须把一个奇点为起点,另一个奇点终点。
3.其他情况的图都不能一笔画出。
由于七桥问题有四个奇点,所以要找到一条经过七座桥,但每座桥只走一次的路线是不可能的。七桥问题就这样被欧拉解决了。1736年欧拉发表了图论的第一篇著名论文“哥尼斯堡七桥问题”。他在这篇论文中提出了一些图论奇数点、偶数点和欧拉图的定义以及判断有无解的定理。
回到立体一笔画题目中,看上去难度增加了,但是通过降维或者说映射完全就变成了一个二维平面上的一笔画问题!也就可以通过上面说到的结论直接解题。要做的,就是尽快找到一个多边形,去找奇点,找到三个就直接过滤掉。一个都没有或者有且仅有两个奇点的时候就是正确答案!
所以立体一笔画这样的项目对于了解这一结论的人来说,实际上就是在多边形道具中找奇点,这场比赛也只是在比赛数点的速度而已。对于不了解的选手来说就有点吃亏。
“七桥问题”与欧拉和拓扑学
七桥问题是一个几何问题,但是一个以前的几何学里从来没有研究过的一类几何问题。在以前的几何学里,不论怎样移动图形,它的大小和形状都是不变的;而欧拉在解决七桥问题时,把陆地变成了点,桥梁变成了线。同时他注意到了线段的长短曲直,交点的准确方位。面积、体积等这些概念,显然在这个问题中都变得没有意义了。图中什么都可以变,唯独点线之间的相关位置,或相互连结的情况不能变。欧拉认为对这类问题的研究,属于一门新的几何学分支,他称之为“位置几何学”。但人们有时也把它叫做“橡皮几何学”。后来,这门数学分支被正式命名为“拓扑学” 欧拉对七桥问题的研究,是拓扑学研究的先声。
1750年,欧拉又发现了一个有趣的现象。正4面体有4个顶点、6条棱,它的面数加顶点数减去棱数等于2;正6面体有8个顶点、12条棱,它的面数加顶点数减去棱数也等于2。接着欧拉又考察了正12面体、正20面体,发现都有相同的规律。他继续研究顶点数V 、棱数E、面数F之间的关系问题,终于发现了一个著名的定理:
F(面数)+V(顶点数)-E(棱数)=2
后人将此命名为“多面体欧拉公式”。有人说,这是拓扑学的第一个定理。
从这个公式可以证明正多面体只有五种,即:正四面体、正六面体、正八面体、正十二面体、正二十面体。
在欧拉之后,人们又陆续发现了一些拓扑学定理,但是这些知识都相对比较琐碎,直到19世纪的最后几年里,法国数学家庞加莱才开始系统地研究拓扑学,并奠定了这门数学分支的基础。现在拓扑学已成为20世纪最丰富多彩的一门数学分支。
(来自:数学建模)
1、头条易读遵循行业规范,任何转载的稿件都会明确标注作者和来源;
2、本文内容来自“泉州市科技馆”微信公众号,文章版权归泉州市科技馆公众号所有。