第169章 这就很离谱！

　　【此章废话极多，多半是四色定理理论相关，不看也不影响故事主线】

　　临渊羡鱼，不如退而结网！

　　看着章杉展露出来的数学以及语言功底，叶未央很羡慕，但没有望而却步，继续着她原本的学习计划~

　　章杉现在是哑巴吃黄连，有苦说不出。

　　虽然洋洋洒洒地写了不少，但他知道远远没达到一篇SCI论文的标准。

　　倒不是知识的含金量不够，关键是现在章杉这篇文章中，语言不够凝练。

　　在这种情况下，里面包含再多真知灼见也是不行的！

　　正式情况下一篇SCI论文字数有三四千字符的，也有好几万字符的。

　　虽然研究方向不同，作者能力水平各有高下，但他们的文章无一例外都力求干练。

　　话虽如此，瑕不掩瑜，尽管章杉目前写的有些冗长，但此时他充分体会到之前学到的各项技能厚积薄发~

　　因为SCI基本都是以英文进行写作，故此需要具有一定的英语基础，语法不能有错，而且除了懂一些常规英语单词外，还要清楚自己方向相关的专业名词，避免错误。

　　这些对章杉来说都是小菜一碟~

　　再者写论文的话要选择目前比较热门的研究方向，再根据自己研究的方向找出目前存在的问题，并提出自己的一个解决方法，方法的提出需具有一些创新性。

　　而章杉也完全没必要担心这些，系统的碎片某种程度上既提供了书单，也框定了选题方向。

　　正常写论文的流程，提出解决方案后，有时需要先利用电脑，下载一些关于研究需要的仿真软件进行仿真，在电脑仿真软件中验证自己的方法是否可行和有效。

　　尽管他还没有进行到这一步，但章杉觉得这并不是一个问题。

　　虽然从来没有用过仿真软件，但对于能应用很多编程软件的章杉来说，这简直手到擒来~

　　~

　　说起来关于四色猜想的证明：

　　“只需要四种颜色为地图着色”最初是由法兰西斯·古德里在1852年提出的猜想。

　　然鹅这个猜想，一开始并没有引人重视。

　　较早对该定理作出“证明”的人是伦敦律师兼数学家阿尔弗雷德·布雷·肯普。

　　肯普的证明是基于对国家数目进行的归纳法。

　　首先容易证明国家数不多于4时四色定理成立。肯普假设当国家数目不多于n时四色定理成立，他的目的是证明n+1个国家构成的地图都可以约化为不超过n个国家构成的地图，从而证明四色定理成立。

　　肯普首先证明一个有关平面图的结论：任意地图中必定存在一个国家，其邻国数目小于等于5。证明很简单，在图论版本中，地图被转换成简单平面图。

　　而一个简单平面图中，设V为顶点数，E为边数，F为区域数，则由于每个区域至少由三条边围成，每条边正好隔开两个区域，所以区域数和边数满足：2E　　≥　　3F。假设每个国家都至少有6个邻国，也就是说每个顶点都连出不少于6条边，那么由于每条边对应两个顶点，所以顶点数和边数满足：2E　　≥　　6V。合起来就有：

　　V+F≤E

　　但这与图论中著名的欧拉公式：V　　+　　F　　=　　E　　+　　2矛盾。

　　因此不可能每个国家都有不少于六个邻国，必定有一个国家邻国数目不超过5。

　　接下来肯普考察n+1个国家中邻国数目最小的国家，称之为A国。A国邻国的数目不超过5个。如果A国的邻国数目不超过3个，那么可以把A国“去掉”（比如和其中一个邻国连成一体），形成一个n个国家的地图，这个地图可以用4种颜色着色，而原来的3个邻国至多用了3种颜色。这时候将A国“放回去”，染上第4种颜色，就等于找到给原地图4-着色的方法[8]。

　　这种能够“去掉”一个国家，减少国家数的局部后来被称为“可约构形”（reducible　　configuration）。

　　接下来肯普证明A国有4个邻国和5个邻国的情况仍然是可约构形，于是都能够化为不多于n个国家的情况。因此任何n+1个国家的地图仍然可以用四种颜色染色，因而通过归纳法可知，四色定理成立。

　　肯普的采用的方法后来被称为“肯普链”方法（Kempe　　chain）来证明可约性~

　　尽管肯普的做法后来被人找出错误，但肯普的思想却延续了下来。

　　20世纪起，欧洲数学界对四色定理的研究出现停滞。相反地，这个问题在美国得到更多的关注。

　　不少杰出的数学家研究了这个问题，并作出很大贡献。一部分的努力是修正肯普的证明；

　　另一方面的努力则是将四色问题进行转化，以使用更多有力的数学工具。

　　对四色问题的转化从并未停止过。

　　从拓扑学的版本转化至图染色的版本后，有人又在1898年提出新的变形。

　　肯普和其他科学家已经注意到，证明四色问题只需要考虑三个国家有共同“交点”的情况，更多国家有共同交点的情形可以转化为前者。

　　因此这样对应的染色图中，每个顶点恰会连出三条边。这样的图被称为“三度图”（trivalent　　map）。

　　有数学家观察到，如果三度图中任意由边围成的区域，边的个数都是3的倍数，那么图可以被4-染色。他进一步发现，只要存在一种给图的顶点赋值+1或-1的方法，使得每个区域的顶点数字之和都被3整除，那么图可以被4-染色。可以证明，4-染色和存在赋值方法是等价的。

　　在美国，数学家对四色定理的研究从未停止过。

　　除了约翰·霍普金斯大学的皮尔斯以及斯多利等人外，另一个研究者是保罗·温尼克。从当时的学术圣地哥廷根大学毕业的温尼克来到美国后在肯塔基大学任教。他1904年发表的论文中已经出现了可约性的雏形。然而美国数学界在四色问题上首次实质性的进展出现在1912年後。普林斯顿大学的奥斯瓦尔德·维布伦（经济学家托尔斯坦·范伯伦的侄子）是这波浪潮的先锋。他的工作重心是拓扑学，1905年证明了若尔当曲线定理。对庞加莱发展出的新代数工具有深入了解的他，很自然地开始对四色定理的研究。他使用有限几何学的观念和有限域上的关联矩阵作为工具，将四色问题转化成有限域系数空间上的方程问题。这个方向被后来的密码学家、数学家威廉·托马斯·塔特称为“量化方法”（the　　quantitative　　method）。同年，他的普林斯顿同僚乔治·戴维·伯克霍夫也开始探索这个方向，但一年之后他开始转向肯普的方法，也即是塔特所称的“定性方法”（the　　qualitative　　method），并提出可约环（reducible　　ring）的概念。1913年，伯克霍夫发表名为《地图的可约性》（The　　Reducibility　　of　　Maps）的论文，利用可约环证明了：由不超过12个国家构成的地图都能用四色染色。1922年，伯克霍夫的学生菲利普·富兰克林运用同样的方法，将结论加强到：不超过25个国家构成的地图都能用四色染色。由于别克霍夫首次证明四色定理对不超过12个国家的地图成立，历史上证明的可染色地图的国家数上限记录被称为别克霍夫数。

　　伯克霍夫等人的证明是肯普的方法的延续和系统化，归纳为寻找一个不可避免的可约构形集（an　　unavoidable　　set　　of　　reducible　　configurations）。

　　这个理念已经体现在肯普的证明中。

　　他首先说明任一地图中必然存在以下四种构形：2邻国国家、3邻国国家、4邻国国家和5邻国国家；然后证明每种构形都是可约构形。后来希尔将这种分类方式称为“不可避免集”。

　　伯克霍夫的构想是使用反证法：反设存在至少需要五种颜色染色的地图，那么其中必然存在国家数最小的“极小五色地图”（five-chromatic　　map）。这个地图必然是“不可约的”（irreducible）。而只要找到一组构形，使极小五色地图中不可避免地会出现其中一种构形，并且每个构形都是可约的，那么就能够通过约化，将地图的国家数减少，从而导致矛盾。

　　肯普找的不可避免集由四种构形组成，但他无法证明最后一种（5邻国国家）的可约性，因此伯克霍夫开始寻找刻画不可避免集的新方法。

　　他提出以相邻国家连成的环来将整个地图M分为三个部分：环内部分A、环外部分B以及环本身R。若环上的国家数为n就称其为n-环。如果R的任意染色都不妨碍A进行染色，那么就可以“忽略”A而将M的染色问题约化为B+R的染色问题。这时便称A+R是可约构形，R称为可约环。伯克霍夫证明了：当R是4-环，或者R是5-环且A中国家不止一个，或者A+R是“伯克霍夫菱形”时，A+R都是可约的构形。因此极小五色地图不可能包含这些构形。

　　富兰克林进一步证明：极小五色地图中必定包含三个邻接的五边国（5邻国的国家），或者邻接的两个五边国与一个六边国，或者邻接的一个五边国和两个六边国。他从而得出一系列的可约构形，形成了25国以下地图的不可避免的可约构形集。因此推出，极小五色地图必定至少包含26个国家。

　　富兰克林发现，极小五色地图必定包括以上6种情形之一。

　　这种方法的终极目标是找到所有地图的不可避免的可约构形集。然而随着国家数增多，要找到不可避免集并证明其可约化性就越难。这主要是因为随着环的增大，染色的方法数目会迅速增大。染色方法有31种，而12-环则有22144种。因此对大环围成的构形验证可约性是十分繁杂的工作。

　　1926年，C.N.Reynolds将别克霍夫数从年，富兰克林将其推进到年，C.E.Winn将之提高到35。而直到1968年，别克霍夫数才更新为40。

　　四色问题研究的下一个突破并不是在美国，而是由哥廷顿大学出身的德国数学家亨利·希尔带来的。

　　他在1948年提出不可避免集的存在性，但他提出的不可避免集可能包含10000个构形，其中还有18-环的庞大构形。希尔的另一个成果是在1969年提出“放电法”（discharging　　method），为寻找不可避免集给出了系统的方法。

　　人工寻找不可避免构形集和验证构形可约性过于缓慢，数学家开始考虑使用当时新出现的计算机作为辅助，以提高验证的效率。构造出放电法的同时，借助于计算机来验证构形可约性的工作也飞速进展。

　　希尔在Karl　　Dürre的帮助下在1965年设计了第一个算法来验证构形的可约性。他们使用的是Algol　　60语言，在德国汉诺威技术学院计算机中心的一台CDC　　1504A电脑上首次运行。1967年前，由于内存不足，只能验证12-环以下的构形。而希尔找出的不可避免集含有的大构形可以达到14-环甚至更多，计算机的能力并不足以快速完成可约性的验证。

　　当时美国的计算机技术领先于欧洲，因此希尔希望能够借助美国的大型计算机来证明四色定理。1967年，美国纽约布鲁克海文国家实验室（BNL）应用数学院院长邀请希尔来美国访问，并允许他使用当时世界上最快的计算机CDC　　6600。其后几年，希尔两度到美国寻求大型计算机的使用机会。这段时间中，Dürre将程序用FORTRAN进行重写。抱着在德国最终解决四色问题的希望，希尔回到德国，但令他失望的是，德国学术界对他的计划持否定态度，并不愿为他的程序拨出计算时间。

　　在数次访美时，希尔开始与沃夫冈·哈肯合作。

　　哈肯在1948年曾经旁听过希尔提出不可避免集的课程，之后对四色定理产生了持续的兴趣。两人通过信件交流合力作出很多进展，为最终解决四色问题铺平道路。1971年，阿佩尔也开始在哈肯的介绍下研究四色问题。然而当时哈肯对解决四色问题的前途感到悲观，因为寻找并验证合适的不可避免可约构形集实在过于复杂，即便借助计算机也需要过多的时间。塔特当时也认为，即便最乐观的估计中，不可避免集也要包含至少8000个构形。然而塔特等人也将希尔的工作介绍到美国（当时希尔的工作只在德国发表过），并引发了很多人的热情。包括弗兰科·阿莱尔、爱德华·雷尼尔·斯瓦特、弗兰科·R·伯恩哈特等人都开始寻找不可避免集以及检验可约性。哈肯和阿佩尔依赖于计算机的工作能力，因此不断改良放电过程。他们将通过放电过程寻找不可避免集的算法和验证可约性结合起来，当某个不可避免集的构形不是C-可约（可约性的一种）或难以被验证为C-可约的时候，就放弃这个不可避免集，以提高效率。两人设定了很多经验性的修正规则，比如设定三个经验性的“障碍”（三种特定的构形），当某个构形中含有这种障碍就直接认为是不可约的；又比如构形的大小不能超过14-环，等等。

　　1975年，哈肯找到一种很好的放电过程，但难以化为算法程序。于是两人暂时开始回归纸笔计算。这时候他们得到当时还是博士学生的约翰·科赫的支持，后者对他们提供了可约性验证算法工作上的帮助。1976年3月，他们终于得到一个由1936个构形组成的不可避免集，对应的放电过程由487条规则构成。同时伊利诺伊大学的主电脑也更换成运算速度更高的IBM　　360，为计算节省大量时间。经过电脑1200小时的验证，他们终于在6月得出：1936个构形都是可约构形。这代表着四色定理最终的解决[2]:35。这时候他们的几个竞争对手如阿莱尔、斯瓦特等的工作也将近尾声。

　　1976年6月22日，哈肯和阿佩尔首次在美国数学协会（M.A.A.）于多伦多大学召开的美国数学学会（A.M.S.）夏季会议公布他们的结果。不久，伊利诺伊大学数学系的邮戳上加上了“四种颜色就够了”（FOUR　　COLORS　　SUFFICE）的一句话，以庆祝四色猜想得到解决。9月，美国数学学会的公告专栏上刊登了两人证明四色定理的消息。

　　1977年，哈肯和阿佩尔将结果写成名为《任何平面地图都能用四种颜色染色》（Every　　planar　　map　　is　　four　　colorable）的论文，分成上下两部分，发表在《伊利诺伊数学杂志》。

　　至此，困扰人们长达长久的四色问题终于被解决了。

　　可以看得出来长久人们围绕着四色猜想主要进行的工作都是围绕着可约性验证进行的。

　　在这一过程中，诸如计算机这样的新工具对简化运算带来了很大帮助~

　　良好的工具对科研会提供良好的助力~

　　然鹅工具太先进也不是什么好事情！

　　章杉从系统图书馆内总共看到了9种全新的证明方法。

　　然而有六种都没办法使用！

　　利用量子计算机证明是什么鬼？

　　现有根本没有合适的量子计算机，难道为了这次证明发明点新工具。

　　还有利用特子计算机证明是什么鬼！这就超出章杉的想象力了。

　　再几种更是没眼看~

　　这就很离谱！

　　不过好在还是有三种能用的方法的~

　　只是利用现有的工具即可，证明思路也很巧妙。

　　这就很nice了~

　　：。：


　　(https://www.23hh.com/book/276/276201/1425862.html)


1秒记住爱尚小说网：www.23hh.com。手机版阅读网址：m.23hh.com