四色定理证明以及其漏洞
需积分: 16 141 浏览量
2009-02-23
13:31:50
上传
评论
收藏 1.9MB DOC 举报
四色定理简洁证明及其漏洞
鲁晨光
http://survivor99.com/lcg
四色定理：任何一张正规地图（每一点最多和三个国家相连）只用四种
颜色就能使具有共同边界的国家着上不同的颜色。
证明如下：
假设存在一个数目 N, 国家数目达到 N 时， 就可以构造一个地图――它
必须用五种颜色着色（四色不够）。这也就是假设去掉其中任何一个国家，数
目成为 N-1 时， 它应当可以用四种颜色着色。
现在我们用反证法证明。
假设我们能够证明：如果 N-1 个国家的地图能用四色着色， 把去掉的一
个加上去也能， 那么我们就证明了不存在这样一个 N, 也就证明了四色定理。
根据欧拉定理, 任何一个地图， 必然存在一国（称之为 X 国）， 其相邻
国家数目不大于 5。 或者说， 其邻国可能是 1 个， 2 个， 3 个， 4 个， 或 5 个。
这样，我们就从 N 国地图中拿掉 X 国，这时它应当可以用四色着色。现
在，如果我们能证明，把 X 国放回到着好四色的 N-1 国地图中， 通过系统颜色
变换，也能用四色着色， 这样就证明了四色定理。
假如 X 国邻国只有 1，2，3 国， 这是简单的，着第四种颜色就是。现在
考虑四邻国和 5 邻国。
前人已经通过 2 色通道的概念，证明四邻国可以为 X 国着色而不增加颜
色数目。参看图 1 （其中 R,G,B,Y 分别表示红，绿，蓝，黄四色）
图 1 四邻国问题
一个二色通道是由交替着上两种不同颜色的国家连成的。上面两个通道
BY 通道和 RG 通道总有一个是不通的。 假设 RG 通道不通， 则把和 R 国以及
与之相连的 RG 通道 1 上的国家的颜色 R 和 G 互换，再把 X 国着上 R 就行了.
剩余27页未读，继续阅读
资源评论
