第170章 这就很离谱（第4页）

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

这种方法的终极目标是找到所有地图的不可避免的可约构形集。

然而随着国家数增多，要找到不可避免集并证明其可约化性就越难。

这主要是因为随着环的增大，染色的方法数目会迅速增大。

6-环的4-染色方法有31种，而12-环则有22144种。

因此对大环围成的构形验证可约性是十分繁杂的工作。

1926年，C.N.Reynolds将别克霍夫数从25提高到27。

1938年，富兰克林将其推进到31。

1941年，C.E.Winn将之提高到35。

而直到1968年，别克霍夫数才更新为40。

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

他在1948年提出不可避免集的存在性，但他提出的不可避免集可能包含10000个构形，其中还有18-环的庞大构形。

希尔的另一个成果是在1969年提出“放电法”

（dischargingmethod），为寻找不可避免集给出了系统的方法。

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

构造出放电法的同时，借助于计算机来验证构形可约性的工作也飞速进展。

希尔在KarlDürre的帮助下在1965年设计了第一个算法来验证构形的可约性。

他们使用的是Algol60语言，在德国汉诺威技术学院计算机中心的一台CDC1504A电脑上首次运行。

1967年前，由于内存不足，只能验证12-环以下的构形。

而希尔找出的不可避免集含有的大构形可以达到14-环甚至更多，计算机的能力并不足以快速完成可约性的验证。

当时美国的计算机技术领先于欧洲，因此希尔希望能够借助美国的大型计算机来证明四色定理。

1967年，美国纽约布鲁克海文国家实验室（BNL）应用数学院院长邀请希尔来美国访问，并允许他使用当时世界上最快的计算机CDC6600。

其后几年，希尔两度到美国寻求大型计算机的使用机会。

这段时间中，Dürre将程序用FORTRAN进行重写。

抱着在德国最终解决四色问题的希望，希尔回到德国，但令他失望的是，德国学术界对他的计划持否定态度，并不愿为他的程序拨出计算时间。

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

哈肯在1948年曾经旁听过希尔提出不可避免集的课程，之后对四色定理产生了持续的兴趣。

两人通过信件交流合力作出很多进展，为最终解决四色问题铺平道路。

1971年，阿佩尔也开始在哈肯的介绍下研究四色问题。

然而当时哈肯对解决四色问题的前途感到悲观，因为寻找并验证合适的不可避免可约构形集实在过于复杂，即便借助计算机也需要过多的时间。

塔特当时也认为，即便最乐观的估计中，不可避免集也要包含至少8000个构形。

然而塔特等人也将希尔的工作介绍到美国（当时希尔的工作只在德国发表过），并引发了很多人的热情。

包括弗兰科·阿莱尔、爱德华·雷尼尔·斯瓦特、弗兰科·R·伯恩哈特等人都开始寻找不可避免集以及检验可约性。

哈肯和阿佩尔依赖于计算机的工作能力，因此不断改良放电过程。

他们将通过放电过程寻找不可避免集的算法和验证可约性结合起来，当某个不可避免集的构形不是C-可约（可约性的一种）或难以被验证为C-可约的时候，就放弃这个不可避免集，以提高效率。

本章未完，点击下一页继续阅读