关注数学发展弘扬科学精神

关注数学发展,弘扬科学精神,专注数学科普

您的位置:主页 > 数学哲学 > 从七桥问题到四色猜想

从七桥问题到四色猜想

作者:华东师大二附中科发布日期:2019-12-21 23:14浏览次数: 来源:微信公众号

七桥问题”促进了图论的出现,同样的,在“四色问题”的研究过程中,新的数学理论和数学计算技巧也随之产生。

从七桥问题到四色猜想

图一 七桥问题

哥尼斯堡七桥问题是18世纪着名古典数学问题之一。在哥尼斯堡的一个公园里,有七座桥将普雷格尔河中两个岛及岛与河岸连接起来。问是否可能从这四块陆地中任一块出发,恰好通过每座桥一次,再回到起点?欧拉于1736年研究并解决了此问题,他把问题归结为如图的“一笔画”问题,证明上述走法是不可能的。

一笔画问题

我们定义,在一个连通图中,由一点引出的线段为奇数个,则这个点为奇点,由一点引出的线段为偶数个,则这个点为偶点。一个图形能否被一笔画出,关键看的是奇点的个数。当奇点为0个或者2个时,图形可以被一笔画下来,反之则不能。一个图形要能一笔画完成必须符合两个条件,即图形是封闭联通的和图形中的奇点(与奇数条边相连的点)个数为0或2。这就是欧拉提出的着名的“一笔画定理”。

从七桥问题到四色猜想

图二 一笔画

连通图的定义是:若从顶点i到顶点j有路径相连(当然从j到i也一定有路径),则称i和j是连通的,如果图中任意两点都是连通的,那么图被称作连通图。下图中左图就是一个连通图,而右图不是。

从七桥问题到四色猜想

图三 能一笔画吗

欧拉注意到,如果一个图能一笔画成,那么一定有一个起点开始画,也有一个终点。图上其它的点是“过路点”。这些点有什么特征呢?“过路点”是“有进有出”的点,有一条边进这点,那么就要有一条边出这点。“起点”是有出无进的点,“终点”是有进无出的点。这也就解释了为什么一个能够一笔画出的连通图中,为什么至多有两个奇点,请读者们自己细细揣摩一下。我们甚至可以得出结论,凡是由偶点组成的连通图,画时可以把任一偶点为起点,最后一定能以这个点为终点画完此图,而凡是只有两个奇点的连通图,画时必须把一个奇点为起点,另一个奇点终点。

下面小编为你们介绍两个图论中的着名问题~

拉姆塞理论

假设在一次聚会上,你坐的那桌有六个人,你是否知道无论你们互相是否认识,必定有3个人,他们或者彼此认识或者彼此都不认识?这便是拉姆塞理论的基本形式,称为“拉姆塞定理”。拉姆塞定理的一个经典证明方法就是通过图论实现的。证明方法如下:

我们把每个人看作平面上任三点不共线的点,若两人认识就用黑线将对应两点连接,不认识则用红线连接。于是命题转化为:如果在平面上给出六个(任意三个不共线的)点,只能用红线和黑线在它们之间连接,证明必存在一个三边颜色相同的三角形。

从七桥问题到四色猜想

图四 建模

考虑其中任意一个点A,设其余的点为BCDEF,那么根据抽屉原理,AB,AC,AD,AE,AF这五条边中至少有三条是同一种颜色的。那么我们不妨设AB,AC,AD都是红色的。

1)如果BC,BD,CD这三条都是黑色的,那么BCD就是一个黑色三角形,满足条件

2)如果BC,BD,CD这三条中至少有一条红色,那么结合AB,AC,AD都是红色,可以找到一个红色的三角形。

于是这六个点被红黑两种颜色连接的15条线段中,必存在一个三边颜色相同的三角形。

拉姆塞理论具体是说,当集会人数大于或等于6时,则必定有3个人,他们或者彼此者认识或者彼此都不认识,则6称为拉姆塞数,记r(3,3)。进一步地,当集会人数大于等于18时,必存在4个人相互认识或相互不认识,也即r(4,4)。至今r(5,5)的精确数值还没有确定,但是可以确定的一点是,r(n,n)存在并是一个精确数值,甚至可以求出它的上界和下界。

四色问题

说到图论,不得不提大名鼎鼎的“四色问题”。如大家所熟知的,四色问题是任何一张地图只用四种颜色就能使具有共同边界的国家着上不同的颜色,用数学语言来表达就是,将平面任意地细分为不相重叠的区域,每一个区域总可以用1234这四个数字之一来标记而不会使相邻的两个区域得到相同的数字。

从七桥问题到四色猜想

图五 用四色填涂的中国地图

在1976年6月,美国伊利诺大学哈肯和阿佩尔在美国伊利诺斯大学的两台不同的电子计算机上,用了1200个小时,作了100亿判断,完成了四色定理的证明,轰动了世界。但是计算机终究只是在庞大的数据上取胜,这样的证明不符合数学严密的逻辑体系,因此四色问题作为“世界近代三大数学难题之一”,至今仍吸引着无数数学爱好者投身其中。现在主流的两个研究方向分别是逻辑证明和拓扑证明。

在“四色问题”的研究过程中,不少新的数学理论随之产生,也发展了很多数学计算技巧。如将地图的着色问题化为图论问题,丰富了图论的内容。不仅如此,“四色问题”在有效地设计航空班机日程表,设计计算机的编码程序上都起到了推动作用。


(声明:本文仅代表作者观点,不代表本站观点,仅做陈列之用)

[责编:大鱼]

郑重声明:本文版权归原作者所有,转载文章仅为传播更多信息之目的,如作者信息标记有误,请第一时间联系我们修改或删除,多谢。

欢迎扫描关注我们的微信公众平台!

欢迎扫描关注我们的微信公众平台!