四色猜想的证明.doc

四色猜想的证明【摘要】 四色猜想的证明已经历经了一百多年，这个看似简单的问题，却难倒过大量的数学爱好者. 人们通过不断努力，最终于1976年6月，由哈肯与阿佩尔合作编制一个很好的程序，在美国伊利诺斯大学的两台不同的电子计算机上，用了1200个小时，作了100亿判断，终于完成了四色定理的证明. 但人们不满足于计算机取得的成就，仍在寻找更简单的证明方法. 我在证明四色猜想时，主要采用了转化思想，把四色猜想的证明转化成在平面内是否存在五个图形两两之间存在公共边的证明，再转化成在平面内是否存在五个点两两相连，连线除了顶点之外没有其他交点的证明. 这样就大大简化了四色猜想的证明，把复杂的图论问题转化成了简单的连线问题，使人很容易理解、接受.【关键词】 四色猜想；两两相连；公共边地图四色定理（four color theorem）最先是由一位叫古德里（francis guthrie）的英国大学生提出来的. 四色问题的内容是：“任何一张地图只用四种颜色就能使具有共同边界的国家着上不同的颜色. ”用数学语言表示，即“将平面任意地细分为不相重叠的区域，每一个区域总可以用1，2，3，4这四个数字之一来标记，而不会使相邻的两个区域得到相同的数字. ”这里所指的相邻区域，是指有一整段边界是公共的. 如果两个区域只相遇于一点或有限多点，就不叫相邻的. 因为用相同的颜色给它们着色不会引起混淆.证明之前我们先看一下这个结论，“将平面任意地细分为不相重叠的区域，每一个区域总可以用1，2，3，4这四个数字之一来标记，而不会使相邻的两个区域得到相同的数字”. 这个结论也就是说，在平面中存在四个或四个以下图形两两之间有公共边，而不存在四个以上的图形两两之间存在公共边，我们只需要证明平面内不存在五个图形两两之间有公共边就可以了.我们假设在平面内存在五个图形两两之间有公共边，分别在这五个图形内各取一点，我们可以把这五个点命名为a，b，c，d，e，两两连接这五点，连线在被连接的两个图形内，并且经过它们的公共边. 如果上述假设成立，我们必能作出这样的十条线（ab，ac，ad，ae，bc，bd，be，cd，ce，de），并且这十条线除了顶点之外不会有其他的交点.我们通过作图方法来证明上述结论，证明过程：我们先任选两点a，b，连接这两点得到ab（ab可以是任意曲线，为了简便，我们把它做成直线）.再任取一点c，从c点向a，b做连线，得到ab，ac，bc这三条线，这三条线连接成了一个闭合的图形（图1），并把平面分成了两部分.然后我们再取一点d和a，b，c相连，d点可以在ab，ac，bc这三条线分割平面得到的两部分中的任一部分（图2，图3），这样的六条线ab，ac，ad，bc，bd，cd就把平面分割成了四部分，每部分都是由三个顶点、三条线分割开的.我们再取第五点e，点e可以在由线ab，ac，ad，bc，bd，cd把平面分割成的四部分中的任何一部分内，如果e点在线bc，cd，bd所分割的平面内（图4），那么点e只能和点b，c，d相连，如果要连接点a，必经过bc，cd，bd这三条线中的一条，所以点e在这一部分不能和点a相连，以同样的原理也可以推出当点e在另外三部分的时候，只能和分割这一部分的三个点相连，不可以与第四个点相连. 因此我们可以得到，在平面内，不存在这样的五个点，两两相连后，连线除了顶点之外不相交.从上面的这四个步骤中，我们一步一步推出了结论：在