科学网 › 标签 › 五色定理

标签: 五色定理

相关帖子	版块	作者	回复/查看	最后发表

没有相关内容

相关日志

四色猜想的逻辑证明: pingguo 2019-11-15 14:07; 四色猜想的逻辑证明证明思路运用五色定理。设想有一张足够大的由 M 个国家构成的五色地图，该地图上有若干个五色区域，任意选定其中一个五色区域，我们可以沿着该五色区域的边界将它从地图上裁剪下来（无论该五色区域与外界构成怎样的相邻关系）。一种颜色代表一个国家，很显然，该五色区域由五个国家相邻构成，用 S1 、 S2 、 S3 、 S4 、 S5 表示这五个国家并代表它们各自不同的颜色。第一步，我们不难证明：由五个国家构成的五色区域在平面上并不存在，只需要着四种颜色就足够了。证明这一点，我们只须将五个国家所能构成的全部相邻关系逐一列举出来即可。第二步，从地图上任意取出的一个五色区域（实际只需四种颜色），我们发现，该五色区域必定有两个国家不相邻，而且其中一个国家必定被其他三个国家所包围而不可能再与其他任何国家相邻。假设这个被包围的国家是 S5 ，包围它的国家是 S1 、 S2 、 S3 ，与它不相邻的国家是 S4 。显然我们可以将国家 S5 的颜色改为 S4 ，也就是，我们可以将原来从地图上取出的五色区域改为四色区域而不改变其原有的相邻关系。（以上，我们只考虑其中仅两个国家不相邻的情形，也就是不考虑少于四种颜色着色的由五个国家构成的相邻关系。）第三步，从地图上取出的五色区域，将其改为四色之后，再放回到地图上原来的位置；很显然，原地图的国家之间相邻关系不变且着色不变。同理，我们可以将整个地图上所有的五色区域改为四色，也就是说，我们可以按照同样的方法为地图重新着色，使之变为一张足够大的由 M 个国家构成的四色地图，即对于任何一张地图而言，只需四种颜色着色就足够了。证明完毕。更为一般情形的讨论设想有一张足够大的由 M 个国家构成的 N 色地图（ N ≤ M ），在这张地图上，必定至少有一个由 N 个国家构成的 N 色区域。任意选定其中一个 N 色区域，用 S1 、 S2 、…… Si 、…… Sn 表示这 N 个国家并代表它们各自不同的颜色。在选定的这个由 N 个国家构成的 N 色区域上，去掉一个国家 Si （沿着 Si 国的边界线将它剪下来），从而得到一个（ N-1 ）色的区域（注意！这个过程是可逆的：我们可以将剪下来的 Si 重新放回去）。将 N 色区域与（ N-1 ）色的区域进行比较：我们发现，由（ N-1 ）个国家构成的（ N-1 ）色区域，当它与 Si 相邻从而构成由 N 个国家构成的 N 色区域，只有当 Si 与这（ N-1 ）个国家中的每一个国家构成两两相邻关系时才有可能。当 M=2, M= 3, M=4 时，即由 2 个国家相邻可构成 2 色地图、 3 个国家相邻可构成 3 色地图、 4 个国家相邻可构成 4 色地图。当 M=5 时，我们发现，由 5 个国家相邻并不能构成 5 色地图，最多只能构成 4 色地图。要说明这一点，我们只须将五个国家所能构成的全部相邻关系逐一列举出来即可。接下来，用反证法，假设存在一张足够大的由 M 个国家构成的五色地图，按照前面的第一步、第二步、第三步证明思路，进行证明。本文中的证明方法可能为三维空间乃至多维空间中的相关问题提供了一个解决思路。两种基本相邻关系——本证明的逻辑起点平面或球面上， A 、 B 两个国家相邻有且只有两种方式：一种是， A 国家的部分边界与 B 国家的部分边界相邻；另一种是， A 国家的全部边界与 B 国家相邻，即 A 国家被 B 国家所包围（无需考虑 A 国家与 B 国家完全重合的情形，因为这在四色问题上没有意义）。需要指出的是，图中的红色与绿色可以互换，即，当只有两个国家相邻时，下图中的国家 A 与国家 B 是等价的：哪一个为红色，哪一个为绿色，意义是一样的（在下文的表述中同样的情形不再说明）。设想有一张由 m+1 个国家构成的地图，它显然可以视为由 m 个国家与某一个国家 A 以任意可能的方式相邻构成的。当 m=1 时，即为最初两个国家构成的地图；当 m=k 时，即为由 k+1 个国家构成的任意可能的地图。 1、如果地图由两个国家相邻构成，需要两种颜色。 2、如果地图由三个国家相邻构成，最少需要两种颜色，最多需要三种颜色；只有当这三个国家两两相邻的时候，才需要三种颜色。 3、如果地图由四个国家相邻构成，最少需要两种颜色，最多需要四种颜色；只有当这四个国家两两相邻的时候，才需要四种颜色。如下图： 4、如果地图由五个国家相邻构成，最少需要两种颜色，最多需要五种颜色；只有当这五个国家两两相邻的时候，才需要五种颜色。实际上，平面或者球面上最多只能构造四个两两相邻的国家。增色定理由 n 个国家构成的地图最多需要 n 种颜色，并且，只有当这 n 个国家两两相邻时才需要 n 种颜色。这一点不难证明。设 n 个国家的名称与颜色分别为 S1 、 S2 、 S3 ，……， Sn ，假设该地图只有前 n-1 个国家两两相邻，第 Sn 个国家仅与其中的 k 个国家相邻（ k ＜ n-1 ），那么，国家 Sn 颜色只要与这 K 个国家的颜色不同即可，它可以取与之不相邻的（ n-k-1 ）个国家的任意一种颜色。同理，可以假设该地图只有前（ n-2 ）、（ n-3 ）、（ n-4 ）、……、 5 、 4 个国家两两相邻，得到类似的结论。推论在由 m 个国家构成的 n 色地图上，以任意可能的方式增加一个国家 A ，若国家 A 与该 n 色地图上的 k 个国家相邻（ k ＜ n ），则由此构成的 m+1 个国家地图仍为 n 色地图；只有当国家 A 与该 n 色地图上的 n 个国家都相邻，才需要 n+1 种颜色。推论不难证明。 n 色地图意味着这个由 m 个国家构成的地图，它的某个局部必须用 n 种颜色着色，即该地图的某个局部有 n 个国家两两相邻。附件一四色猜想相关概念及五色定理内容的介绍四色猜想的提出四色猜想是弗伦西斯·格斯里（ FrancisGuthrie1831-1899 ）提出的， 1852 年他在给弟弟的信中写到：“每幅地图都可以只用四种颜色着色，使得有公共边界的相邻国家着上不同的颜色。”四色猜想又称四色定理、四色问题。格斯里的话中包含两个需要明确的概念：一个是相邻；另一个是国家，即平面或球面上的一个区域。为此给出两个定义。两个需要明确的概念 1 、单连通：一个区域内的任何两点，如果可以在其内部（即不穿过其边界）用一条曲线相邻，则称这个区域是单连通的。四色猜想中涉及到的区域均指的是单连通区域。 2 、相邻：平面或球面上的两个区域，如果只有一条公共边界，就说这两个区域是相邻的。五色定理的内容将一个平面分成若干区域，给这些区域染色，且保证任意相邻区域没有相同颜色，那么所需颜色不超过五种。附件二平面或者球面上最多只能构造四个两两相邻的国家证明这一点，只须例举出全部五个国家相邻的情形即可。我们不妨从两种基本相邻关系出发，来更清晰地说明这一点。 1-1 前面我们已经知道，平面或球面上， A 、 B 两个国家相邻有且只有两种方式：如图一、图二。图 1 图 2 图 1 、图 2 与第三个国家相邻，如 2-1 及 2-2 2-1 图一与第三个国家相邻，有如下三种方式图 3 图 4 图 5 2-2 图二与第三个国家相邻，有如下两种方式图 6 图 7 图 3 、图 4 、图 5 、图 6 、图 7 与第四个国家相邻，如 3-1 、 3-2 、 3-3 、 3-4 、 3-5 3-1 图三与第四个国家相邻，有如下四种方式图 8 图 9 图 10 图 11 3-2 图四与第四个国家相邻，有如下四种方式图 12 图 13 图 14 图 15 3-3 图 5 与第四个国家相邻，有如下两种方式（以下略）从以上可知，两个国家相邻有两种方式；三个国家相邻有五种方式…… 由三个国家相邻的五种方式，与第四个国家相邻即构成全部四个国家相邻的方式，最多只需四种颜色即可。注：这里发表的是改进后的版本，原文 2016 年 2 月 2 日发表于科学网博客。王平 2019 年 11 月 15 日数学的美妙之处在于它是简单性与深刻性相统一的事物。诸多真与美的事物也是如此。数学的困难之处在于，你感觉自己直接面对着上帝，却从不知道上帝在哪里。如果把数学视为一个游戏，它也许是唯一一个上帝愿意陪你玩的游戏，可是你永远不知道上帝怎么玩。正文中的一些插图未显示，请下载本文的PDF文档：四色猜想的逻辑证明-20191115.pdf 我的更多数学论文，请点击进入：关于哥猜的再猜想微分中值与积分中值关系定理罗尔定理引用辅助函数的证明方法利用不定方程的对称性巧证费马大定理; 个人分类: 数学|4680 次阅读|0 个评论

更多...

帐号		自动登录	找回密码
密码			注册

关闭 安全验证

标签: 五色定理

相关帖子

相关日志

关闭安全验证