计算机科学论坛--归纳法证明四色问题

贴子主题：归纳法证明四色问题

举报打印推荐 IE收藏夹

本主题类别:

归纳法证明四色问题

以连线表示两条边相邻

（１）当点数（点代表国家）＜＝４时，显然能只用四种颜色解决着色问题．

下面证明：假设n个点能只用四种颜色着色而不会出现相邻点颜色相同的情况，则n＋1个点也能只用四种颜色来解决着色问题．

（２）假设有n－１个点的平面图里的n－１个点能只用四种颜色着色而不会出现相邻点颜色相同，当n个点中去掉其中一个点v时，由假设知其能只用四种解决着色问题：

１．当v的度数＜＝４时，肯定能只用四色解决问题；

２．当v的度数＝４时，而四个相邻点着的颜色数＜４时，同样能只用四色解决问题；

３．当v的度数＝４，而且四个相邻点涂了四种不同颜色，由于相邻的４个点肯定不能两两相邻，否则再与v相邻的话就构成K５图（非平面图）；故这相邻v的四个点肯定　有两个点不相邻的．而且他们是不相连通的．因为如果相连通，则由二度相连的结果知其仍使K５的同构；设那两个点为A,B，A和B不连通和相邻，则可以将其中一个的颜色改为另一个相同，假设A--red,B---blue,则可以将A改为blue，然后将A连通分支的全部blue改为red，red改为blue．这样就不影响n-1个点的图的着色问题．

４．当v的度数＞＝５时，情况与３类似．

　　　当第５个点的颜色是３剩下来的其中一种的话，则不用改任何点的染色即可满足．

　　　当第５个点的颜色是３中的A的颜色时，他和A肯定不相邻，而且他和剩下的除V点的四个点中的其中一个点不相邻，设那点为C，于是第５点和C点的情况和３中的情况相同，用同样的方法解决即可

由此粗劣证明结束　　望各位指点　呵呵


	W 3 C h i n a ( since 2003 ) 旗下站点苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》	46.875ms