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

四色定理 (2-1)

一个很有名的例子是这个对四色定理的简短的证明(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染色了。

数学联邦政治世界观提示您:看后求收藏(同人小说网http://tongren.me),接着再看更方便。

相关小说

幸运值爆表的我在恐游专心搞事业 连载中
幸运值爆表的我在恐游专心搞事业
爱我一周可以吗
幸运值爆表指的是在这样的恐怖游戏还能结识很多生死之交啦当然在游戏中会有一点啦但不会给女儿太多的女主光环!每个人都会闪闪发光!
0.5万字1个月前
父子双星(紫胤真人,配时)影 连载中
父子双星(紫胤真人,配时)影
192***026_3508790693
严厉父君管教儿子,教给儿子十八般武艺,希望他可以撑起保护仙界的大任,却因魔族的的阴谋,而牺牲自己,护佑天下众生,告诫儿子要像他一样保护天下苍......
1.7万字1个月前
团队作战:永不放弃! 连载中
团队作战:永不放弃!
伊洛染曦
“荧!相信我,你可以的!我们陪你!”——遇到困难,我们陪你一起!“棐,如果可以,我希望,我们能永远在一起!所以,一起努力吧!”——爱情,在生......
1.8万字1个月前
锦瑟(卿与华年) 连载中
锦瑟(卿与华年)
经年旧梦
自由发挥中
10.5万字1个月前
万界之我可以无限许愿 连载中
万界之我可以无限许愿
貌贪
一个无缘无故死掉的人,在获得许愿系统的情况下,先是斗破立志去遍所有世界
16.2万字1个月前
凋敝之双重人格 连载中
凋敝之双重人格
符华(赤鸢)
光明与黑暗共同的化身啊,打破命运的枷锁,还原真相吧!(第二季)
4.6万字1个月前