四色猜想证明

《四色猜想证明》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、四色猜想的证明四色猜想的内容是：如果把地图上有共同边界的国家涂成不同颜色，那么只需要4种颜色就足够了。要证明四色猜想，首先需要定义一些新的概念：1、国家的表示法——点由于该猜想的内容中不涉及与国家形状有关的问题，而只涉及国与国之间的相邻关系，因此任何一个国家都用点来表示。2、相邻与不相邻在叙述时，用符号“=”表示相邻，用“#”表示不相邻，如果用图示法表示相邻与不相邻则要复杂一些，先看下图：(a)(b)(c)图1在图1（a）与（b）中，分别用了直线和曲线连接两个国家A和B，表示国家A与B相邻，为了简便起见，这里只用直线表示相邻，图1（c）中是已知A与B相邻，叫你判断C与D

2、能否相邻，连接CD、CD与AB相交，相交是否就是不相邻呢？我们先看一组图:图2图2是把图进行等分后的结果，从三等分开始，如果每一份代表一个国家，这表示等分后的所有国家相聚于一点，从四等分后的国家A、B、C、D可知，如果国家之间点的接触算是相邻，则A与B，C与D都为相邻，显然这时的A与B，C与D是交叉相邻，与图1（c）中的情况相同,此时A与B，C与D的交点表示接触点。若点的接触不算相邻，那么连接A与B的直线可以看作一道墙，在这中间不能有任何直线通过。因此，由于C与D的连线与AB相交，据此判断出C与D不能相邻。但是当相邻用曲线进行表示，C与D却能够相邻，这是否说明用直线表示

3、相邻有问题呢？当然不是，仔细分析就可以发现，用曲线表示相邻同样不能有相交的情况出现，因此，用直线表示相邻时，适当移动C或D的位置就可以使C与D相邻。3、完全相邻这是一个关键问题，可以这么说，没有这一概念的证明都是伪证明，现在给出完全相邻的定义：在一个面上（可以是平面也可以是曲面）给定N个国家，如果这N个国家两相邻，那么我们就称这N个国家完全相邻。由于1个国家没有相邻关系，因此上面的N要求要大于1。如果是3个国家完全相邻，它们的相邻关系为：（这三个国家分别设为1、2、3）1=2，1=3，2=3有了以上这些概念之后，就有了证明四色猜想的基础。定理1：在一个面上（可以是平面也

4、可以是曲面）给定N个国家，如果这N个国家完全相邻，那么需要用N种颜色进行区分。（N>1）证明：N个国家完全相邻，它们的相邻关系为：1=2，1=3，1=4……，1=N2=3，2=4，2=5……，2=N3=4，3=5，3=6……，3=N…………………………………N-2=N-1，N-2=NN-1=N首先把N个国家都涂上不同的颜色，假定它们涂上的颜色名与国家名相同，就有了N种颜色，现在要证明的是，这N种颜色一种也不能少。可以假设第k种颜色可去掉(1=

5、用不同的颜色进行区分，矛盾。因此结论成立。定理2：在平面上，如果存在N个国家完全相邻，那么N值不能大于4。证明：在证明之前，首先需要指出的是，如果点的接触算是相邻，从前面图2的等分圆中可以看出，分成的N个国家产生了完全相邻，此时N值没有不大于4的限制，因此这里所说的完全相邻中的相邻并非指点的接触，而是指线的接触。现在来证明此定理，先看N=1的情况。当N=1时，由于没有构成相邻关系，因此不存在完全相邻。当N=2时，可以建立完全相邻关系，用图表示为：当N=3时，由于相邻关系用直线连接，如果表示国家的点在同一直线上，则两边的点无法用直线直接连接，因此要建立完全相邻关系，只要使

6、三点不在同一直线上就行了。这里值得注意的是，此图只揭示了相邻关系，以及由相邻关系所形成的封闭的域。但它并没有表示出这三个国家具体的形状。比如说，由一个国家包围两个国家，由两个国家包围一个国家，或者三个国家中无包围关系，这三种完全相邻情况都可以用此图进行说明。而此图也反过来说明了这三种情况都能构成完全相邻。那么此图又是怎样对这三种情况进行“说明”的呢？先看第一种情况，由一个国家包围两个国家，此时只要过点1作一个圆，使2、3两点在圆的内部即可，用图表示为：由于相邻关系没有说明国家的包围关系，不过根据相邻关系可以对国家之间所有的包围关系一一表示出来。由两个国家包围1个国家可以

7、用下图表示：由1、2两点为起始点作圆弧，使第3点在圆弧内，圆弧表示1、2两国的形状延伸，在考虑形状延伸时不能出现相交。而三个国家中无包围关系则由相邻关系图上就能感知到。另外，如果相邻关系用曲线表示，由三点没有在同一直线上的限制。如：此图与用直线表示相邻时的图等价，但是用曲线表示相邻并不直观，这也就是采用直线表示相邻的原因。事实上现在可以看出，N=3时的完全相邻必须建立在N=2时的完全相邻基础上，即3个国家完全相邻必须建立在2个国家完全相邻基础上，据此得出以下引理：引理N个国家的完全相邻必须建立在N-1个国家的完全相邻基础上。证明：如果N个