 四色猜想证明
四色猜想证明
本人在学离散数学遇到四色问题，思考后得出以下证明，请网友们不另赐教！谢谢！
四色问题的内容是：“任何一张地图只用四种颜色就能使具有共同边界的国家着上不同的颜色。”用数学语言表示，即“将平面任意地细分为不相重迭的区域，每一个区域总可以用1，2，3，4这四个数字之一来标记，而不会使相邻的两个区域得到相同的数字。
以下是本人粗略证明：
要证明此问题，只要证明地图中不存在５个或５个以上区域两两相邻的情况，这样才能只用四色来解决问题．
要证明不存在５个或５个以上两两相邻的区域的情况，只须证明不存在５个区域两两相邻的情况存在．
这点我用反证法来证明；
假设存在５个两两相邻的区域的情况，则我从每个区域内各取一个点，共５个点，用线把他们两两连接起来表示他们两两相邻．（即对偶图）
故得到K5子图或其同构．它是非平面的．（K5和K3,3图为非平面子图已经得到严格证明．附：库拉托夫斯基定理：一个图是平面图的充分必要条件是该图不含有K5或K3,3二度同构的子图）．
然而因为假设５区域是两两相邻的，就是说两两区域内的点可以用线连通（通过共同的边）而不与其他连线相交叉，即：假设的５区域两两相邻图是平面图．
如上所述，产生了矛盾，所以假设是错误的．平面图不存在５个两两相邻的区域的情况．也就是说：不存在５个或５个以上区域两两相邻的情况．
类似可证明，只用三色是不能解决着色问题的．因为四个两两相连的区域的情况是很容易找到的．比如里外两个三角形：abc,ABC，其中a-A,b-B,c-C.则出现四个两两相连的区域情况． 这里三色不可能解决问题，肯定有两个相邻区域着上相同的颜色！
扩展开来，对于整个地图，任意抽取５个国家，如果他们两两相连，则不能只用四种颜色就能使具有共同边界的国家着上不同的颜色．但是如上证明，这样的５个国家在平面图中是不存在的．
所以，任何一张地图只用四种颜色就能使具有共同边界的国家着上不同的颜色．
另：同样可得到：平面图只存在最多四个区域两两相连的情况．
|
[返回] 计算机科学论坛 →
计算机理论与工程 → 『 理论计算机科学 』 → 四色猜想证明
(订阅本版)
2007/9/12 13:57:00
顶端 
用点着色太证明面着色是没有问题的～经典教科书上就是这么做的～问题在于不存在K5并不代表平面图可4..(143字) － chenminyi，2008年9月23日
新浪微博
