数学联邦政治世界观
超小超大

四色定理

一个很有名的例子是这个对四色定理的简短的证明(Alfred Kempe, 1879),直到11年后才有人(Percy Heawood, 1890)指出了这个证明的错误。

这个证明需要用到一个引理,由于证明并不是很复杂(用欧拉公式)而且不是本答案重点(ie 它的证明是对的),我们就不证它了:

引理 一个n>=3个顶点的平面图G最多有3n-6条边。

现在我们来证明四色定理。

定理 对任何平面图G,都可以给G的每个顶点分配一个颜色,使得任何G中的边的两个顶点颜色都不同。

这个定理的描述和通俗版本的不太一样:四色定理的通俗版本是说,任何一个平面上的地图都能用四种颜色染色使得相邻国家的颜色不同。我们可以想象每个国家有一个首都(G的顶点),每两个相邻国家的首都之间都有一条不一定是直线的路(G中的边)。于是通俗版本的四色定理就变成了上面的图论描述。

证明:

设G是一个n个顶点的平面图。n<=4的情况显然正确。现在对n进行数学归纳法:当n>4时,取一个G的度(相邻顶点的数量)最小的顶点v,由之前的引理我们知道v的度最多是5。根据归纳法假设,图G-v(ie将v移除后的图)是可以用四种颜色染色的。现在将G-v用四种颜色染色,然后考虑与v相邻的点。如果它们没有用到全部4种颜色那么我们就可以用剩下的颜色染v了。不然,在平面上画出G(取一个G的drawing),然后分类讨论:

(1)v的度是4。设和v相邻的顶点按顺时针顺序为a,b,c,d,不妨设它们的颜色按顺序分别为1-4。现在补充一个定义:称一条G-v中的路径为(i,j)-路径,如果路径上的顶点的颜色按顺序依次间隔为i和j。现在考虑由a出发的所有(1,3)-路径。如果c不在任何这样一条路径上,那么我们直接把所有这样的路径上的1和3交换即可让a用3染色同时不破坏剩下的图G-v的四色染色。然后用1来染v即可。不然,我们有一条从a到c的(1,3)-路径。由于G是平面图而且abcd是按顺时针排列的(见下图),我们知道不可能存在从b到d的(2,4)-路径了,于是把从b出发的(2,4)-路径上的2和4交换即可;

(2)v的度是5,和v相邻的顶点按顺时针顺序为a,b,c,d,e,且颜色按顺序为1,2,3,4,1(只是一种情况)。考虑从b开始的(2,4)-路径,如果d不在任何一条这样的路径上那么和第一种情况类似交换b开始的(2,4)-路径上的2和4即可;不然如果b到d有一条(2,4)-路径,从c到a和e就无法有(1,3)-路径了(见下图),不然G不是平面图。于是和第一种情况类似可以解决这种情况;

(3)v的度是5,和v相邻的顶点按顺时针顺序为a,b,c,d,e,且颜色按顺序为1,2,3,1,4。注意到实质上不同的染色只有这种情况和上面的第二种。现在如果e不在b开始的(2,4)-路径上,或者e不在c开始的(3,4)-路径上,我们都可以交换b或c开始的对应路径上的颜色从而解决;不然,e有一条到b的(2,4)-路径,而且有一条到c的(3,4)-路径。但是这样一来,a到c就无法有(1,3)-路径,而且d到b也无法有(1,2)-路径了(见下图),于是我们交换a的(1,3)-路径上的1和3,以及d的(1,2)-路径上的1和2,于是a变成了颜色3,d变成了颜色2。现在我们就可以把v用1染色了。

综上所述,如果G-v 可以用四种颜色染色,G也能用四种颜色染色。于是任何平面图G都能用四种颜色染色。

数学联邦政治世界观提示您:看后求收藏(笔尖小说网http://www.bjxsw.cc),接着再看更方便。

相关小说

时光机恋曲 连载中
时光机恋曲
参宿列队
刘文和一个异国女孩拯救时空的故事,不甜不要钱。
3.3万字5个月前
遇到你们,不再空虚 连载中
遇到你们,不再空虚
蓝猫爱吃小无鱼
在我将要“死亡”之时,是你们让我让我获得生的希望……真的吗?……(啊啊啊啊啊写的太烂了!!!)
0.8万字3个月前
没有原因的爱 连载中
没有原因的爱
清风吹晓梦
因为儿时的一次偶然,江田喜欢上了顾辰,经历了多年的努力终于和顾辰分到一个班,并且是同桌,开始江田却没有勇气告白,终于在这这一天江田将自己的心......
2.2万字2个月前
神仙爱情手札 连载中
神仙爱情手札
青衣如故QYRG
渣爹再婚后,他被继后的儿子宠哭了。【1v1,双洁,日久生情,远古洪荒,无逻辑,勿考究。】经常修文
3.3万字2个月前
巫女日記 连载中
巫女日記
Sumphote
架空世界,主角安以琪·苏·图兰,一半萨摩一半库兰,讲述其上大学后发生的一系列事情,不断成长,渐渐明白自己意欲何为,想要坚持父母那个梦想——建......
9.0万字1个月前
长相思之入颖相思改篇版 连载中
长相思之入颖相思改篇版
雪雨森林
长相思改篇,若有不喜欢的大大们可以不看,请大大们不喜勿喷。
0.7万字3周前