四色猜想证明.docVIP

四色猜想的证明 四色猜想的内容是：如果把地图上有共同边界的国家涂成不同颜色，那么只需要4种颜色就足够了。 要证明四色猜想，首先需要定义一些新的概念： 1、国家的表示法——点 由于该猜想的内容中不涉及与国家形状有关的问题，而只涉及国与国之间的相邻关系，因此任何一个国家都用点来表示。 相邻与不相邻 在叙述时，用符号“=”表示相邻，用“#”表示不相邻，如果用图示法表示相邻与不相邻则要复杂一些，先看下图： (b) (c) 图1 在图1（a）与（b）中，分别用了直线和曲线连接两个国家A和B，表示国家A与B相邻，为了简便起见，这里只用直线表示相邻，图1（c）中是已知A与B相邻，叫你判断C与D能否相邻，连接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却能够相邻，这是否说明用直线表示相邻有问题呢？当然不是，仔细分析就可以发现，用曲线表示相邻同样不能有相交的情况出现，因此，用直线表示相邻时，适当移动C或D的位置就可以使C与D相邻。 完全相邻 这是一个关键问题，可以这么说，没有这一概念的证明都是伪证明，现在给出完全相邻的定义： 在一个面上（可以是平面也可以是曲面）给定N个国家，如果这N个国家两相邻，那么我们就称这N个国家完全相邻。 由于1个国家没有相邻关系，因此上面的N要求要大于1。 如果是3个国家完全相邻，它们的相邻关系为：（这三个国家分别设为1、2、3） 1=2，1=3，2=3 有了以上这些概念之后，就有了证明四色猜想的基础。 定理1：在一个面上（可以是平面也可以是曲面）给定N个国家，如果这N个国家完全相邻，那么需要用N种颜色进行区分。（N1） 证明：N个国家完全相邻，它们的相邻关系为： 1=2，1=3，1=4……，1=N 2=3，2=4，2=5……，2=N 3=4，3=5，3=6……，3=N ………………………………… N-2=N-1，N-2=N N-1=N 首先把N个国家都涂上不同的颜色，假定它们涂上的颜色名与国家名相同，就有了N种颜色，现在要证明的是，这N种颜色一种也不能少。可以假设第k种颜色可去掉(1= QUOTE k=N)，则第k种颜色就可以用其他N-1种颜色中的一种所取代。即存在2个国家所涂的颜色相同，而根据题意，这2个国家相邻，必须要用不同的颜色进行区分，矛盾。因此结论成立。 定理2：在平面上，如果存在N个国家完全相邻，那么N值不能大于4。 证明：在证明之前，首先需要指出的是，如果点的接触算是相邻，从前面图2的等分圆中可以看出，分成的N个国家产生了完全相邻，此时N值没有不大于4的限制，因此这里所说的完全相邻中的相邻并非指点的接触，而是指线的接触。 现在来证明此定理，先看N=1的情况。 当N=1时，由于没有构成相邻关系，因此不存在完全相邻。 当N=2时，可以建立完全相邻关系，用图表示为： 当N=3时，由于相邻关系用直线连接，如果表示国家的点在同一直线上，则两边的点无法用直线直接连接，因此要建立完全相邻关系，只要使三点不在同一直线上就行了。 这里值得注意的是，此图只揭示了相邻关系，以及由相邻关系所形成的封闭的域。但它并没有表示出这三个国家具体的形状。比如说，由一个国家包围两个国家，由两个国家包围一个国家，或者三个国家中无包围关系，这三种完全相邻情况都可以用此图进行说明。而此图也反过来说明了这三种情况都能构成完全相邻。那么此图又是怎样对这三种情况进行“说明”的呢？ 先看第一种情况，由一个国家包围两个国家，此时只要过点1作一个圆，使2、3两点在圆的内部即可，用图表示为： 由于相邻关系没有说明国家的包围关系，不过根据相邻关系可以对国家之间所有的包围关系一一表示出来。 由两个国家包围1个国家可以用下图表示： 由1、2两点为起始点作圆弧，使第3点在圆弧内，圆弧表示1、2两国的形状延伸，在考虑形状延伸时不能出现相交。 而三个国家中无包围关系则由相邻关系图上就能感知到。 另外，如果相邻关系用曲线表示，由三点没有