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

四色定理

一个很有名的例子是这个对四色定理的简短的证明(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),接着再看更方便。

相关小说

白梓萱与王静 连载中
白梓萱与王静
白梓萱54341348
“东关小学就像那五只小羊一样,快乐,幸福,美丽”“只有露西,并不像只小羊”“东关小学又是一个美丽团结的羊村”“善良团结”“有时候村里也可能混......
0.2万字5个月前
原创终极一家之爱会不会痛 连载中
原创终极一家之爱会不会痛
旭梦如夏
我是敏敏爱博君禁止辱骂禁止上升真人,原创不易,重新写,夏美崩溃失去哥哥是否接受令团长的喜欢,夏美当盟主,孙权很爱夏美这个大姐,还有阿香,周瑜......
9.0万字5个月前
缤纷多彩小故事 连载中
缤纷多彩小故事
风雪轮
多个故事,应该是很简洁的一些故事,一个故事开头结尾结束的很快
3.9万字5个月前
穿成反派大小姐后我躺赢了 连载中
穿成反派大小姐后我躺赢了
空花亦落果
常年排行垫底的系统菁菁被前辈扔到了反派大师姐身边,任务竞是阻止她崩坏位面!!菁菁欲死无泪,战战兢兢的跟着这个暴躁大师姐走过一个又一个位面。本......
1.7万字2个月前
珩时 连载中
珩时
安逸_liberty
世界背景:这是个有异能者和魔兽的世界,这些异能者都归国家的科学家研究。(此为幻想类世界观,与现实世界无关)基本消息:每6个异能者分为一队,按......
0.6万字2个月前
倚靠在时光的背后爱着你 连载中
倚靠在时光的背后爱着你
时光荏苒,初心依旧
王进不知不觉中迷恋上高帅,岁月匆匆,她究竟能不能和高帅真正走在一起呢?……
15.1万字1个月前