四色猜想的证明

四色猜想的证明吴道凌（广东省广州市，510620）摘要：四色猜想至今未得到书面证明。根据其定义的国家概念和着色要求，揭示了无限平面或球面上任意国家及其邻国的构成和着色规律，从而给四色猜想一个书面证明。关键词：四色；猜想；证明；国家；着色中图分类号：O157.5文献标识码：A1852年，英国学者弗南西斯·格思里(FrancisGuthrie)提出，“每幅地图都可以用四种颜色着色，使得有共同边界的国家着上不同的颜色”，这就是后来数学上著名的四色猜想。对此猜想，一百多年来曾有无数学者予以研究，但人工验证均无功而返。1976年，美国数学家阿佩尔(KennethAppel)和哈肯(WolfgangHaken)利用电子计算机，作了大量判断，对四色猜想进行了机器证明，但这一证明不能由人工直接验证，人们必须对计算机编译的正确性以及运行这一程序的硬件设备充分信任，因此并不被人们普遍接受。本文拟根据四色猜想定义的国家概念和着色要求，研究无限平面或球面上国家的构成及其着色规律，寻找对四色猜想的书面证明。1四色猜想相关定义及表述方法四色猜想所指的国家，是指连续的区域，可为单连通区域，也可为多连通区域，不连续的区域不属一个国家。共同边界指相邻国家有无数个共同点，四个或四个以上的国家不交于一点，或者说，这种交点不认为是共同边界，只有这种交点的国家不需区分着色。四色猜想并未限制地图范围，地图可定义在球面或无限平面上。在球面上的任何国家，将存在一个外边界，由一条简单闭曲线构成，在无限平面上的国家，一般也由一条简单闭曲线构成外边界，个别国家也许在某些区间不存在边界（即区域无限延伸），其外边界将由若干段曲线构成，对于这种情况，我们可在其无限远处虚拟若干个国家若干段边界，与实在的若干段边界构成一条简单闭曲线边界，这种做法实际上提高了这些国家的着色要求，因此不影响本命题的论证。如为单连通区域，国家里边将不存在内边界，如为多连通区域，国家里边将存在若干由简单闭曲线构成的内边界。因此，为使命题具有普遍性，把国家定义为具有一个外边界和若干内边界的区域，每一边界均为该国与若干邻国的共同边界构成的简单闭曲线，如图1示。下面把构成一条这种共同边界闭曲线的若干邻国称为一个邻国圈。用小圆圈表示邻国，两国相邻时，用线条连接两个小圆圈，一个邻国在共同边界多处出现时，各处分别用小圆圈表示，并用线条连接各处表示连通。把一个国家表示为由其若干邻国圈构成的闭合圈围闭的区域，如图2示。其中，外闭合圈之外，一些邻国可能跨越闭合圈上的一个或多个邻国与其它一个或多个邻国相邻，一些邻国也可能多处出现在闭合圈上，这些情况将使闭合圈外存在若干邻国之间的连线，同理，每个内闭合圈之内也将可能存在若干邻国之间的连线。另外，邻国里边也许包含若干小区域，两国连邻时，共有边界也许不只一段，多段共有边界之间将存在若干小区域，相当于圆圈及连线里边可能包含若干小区域，各小区域分别由若干国家组成，这些小区域并不影响对所需研究的国家及其邻国的着色讨论，因此，暂不予考虑。除了若干闭合圈围闭的阴影部分区域为所需研究的一收稿日期：2009-3-26作者简介：吴道凌，高级工程师，硕士个国家外，其它圈线围闭的若干区域可以不存在其它国家，也可以存在若干国家。这里未反映国家外可能存在的不属于任何国家的区域情况，对于这种情况，我们可把这种区域也当作国家，只是，如果这种区域有不相连通的多个时，为不与本猜想命题相左，这种区域的着色可不统一。根据国家及共同边界定义，这种表示两国相邻或一国连通的连线总是不相交的。2一个国家及其邻国圈构色2.1国链及三色圈的构色及链接规律若干个国家以某种方式连接而成的构造形式简称构形，使构形相邻国家着上不同颜色的过程简称构色，最多只需三种颜色的构形简称三色构形。由若干个国家一个连接一个形成的一条区域链简称国链（用L表示），除首尾两国仅与一国连接外，其余各国均与另两国连接，当构成国链的国家个数为奇数个（包括一个）时，称为奇链，为偶数个时，称为偶链。现为国链构色，自左至右，当第一个国家着色A时，第二个国家可着色B，以后逢单着色A，逢双着色B，最后一个国家，奇链可着色A，偶链可着色B。由此可见，国链可以两种颜色构色。将上述国链的首尾相接即构成闭合国链，简称国圈，国圈上各国家之间，每一国仅与另两国连接。对国圈进行构色时，两色偶链首尾着色不同，首尾相接时原来的着色即能满足要求；两色奇链首尾着色相同，不能满足国圈着色要求，但只要将首尾中的一个国家改变为第三种着色，国圈即可构色。因此，最多采用三种颜色即可对国圈进行构色。以后将最多只有三种构色的国圈称为三色圈（用S表示）。国链及国圈构色示意图如图3示。将一条国链的两端国分别与一个构形的一个国家连接，或与同一个国家连接，称为链接。如果链接的是一个三色构形，国链构色时在涵盖构形可能有的三色范围内选择颜色，自国链一端开始，受与之连接的构形一个国家的一个约束，首个国家只剩余两种选择，依此类推，倒数第二个也有两种选择，但最后一个多了一个来自构形的约束，如果这个约束与倒数第二个一致，那最后一个仍有两种选择，如果这个约束与倒数第二个不一致，那最后一个仍有一种选择。因此，一条国链链接一个三色构形而成的新构形仍为三色构形，链接不需增加三色或三色以上构形的构色。图4示意了国链与一个三色圈的链接情况。三色圈链接一条国链后，新构形仍为三色构形，继续链接其它国链，构形仍保持为三色构形。将构造一个构形后剩余的区域叫余域（用Y表示）。可以看到，在一个无限平面或球面上，构造一个三色圈后，一般出现两个不相连通或相邻的余域，每个余域均由该三色圈围闭。一条国链链接三色圈后，根据定义，两个被链接国将把三色圈分为两段（当只有一个被链接国时，认为其中一段只有这一个国），分别与国链构成一个新三色圈，国链所在区域构造国链后将再出现两个余域，分别被两个新三色圈围闭。在新构形的余域中再继续构造链接的国链，将可能再出现新三色圈围闭的新余域。当然，上述将区域一分为二的提法是不定的，如果三色圈或国链扩大到充满一个或两个余域，余域将只有一个或不存在，如果某些国家或连接线里面还有余域，余域将可以更多，但无论如何，每个余域均由三色圈围闭，且互不连通或相邻。2.2邻国圈构色考察一个国家的外邻国圈。当邻国圈各国之间每国仅与另两国相接，邻国圈将是一个国圈，最多只需三种构色。但如上所述，一般邻国圈构成的闭合圈外，各邻国之间还可能存在其它连线，这些连线将不可能相交，可能的情况是多条连线层层包围，其中，最外围的一条连线将包围若干个邻国和连线，其外再也不存在邻国之间的连线。把被最外围连线包围的邻国称近邻，一条最外围连线两端的邻国称被链接国，不存在这种跨邻国连线的邻国称邻国链，则一般邻国圈将由若干段近邻、被链接国和若干段邻国链连接而成，如图5（1）示，J1、J2、J3等为各段近邻（各段近邻内各邻国包括被链接国之间的可能连线未示），L1、L2、L3等为邻国链。在不改变各国构形的情况下，将图5（1）等效表示为图5（2），由于各被链接国与各邻国链等最外层邻国（统称远邻）之间每国均与另两国连接，因此，它们将共同构成一个三色圈（图中外圈），简称远邻圈，一般邻国圈可看作各近邻通过被链接国与一个远邻圈连接而成。其中，某段近邻（假设图中J1）对应的两个被链接国如果同属一个邻国，则将其合并为一个表示。处于一条最外围连线范围内的一段近邻，各邻国之间的连线及与被链接国的连线同样不可能交叉，因此，一段近邻与三色圈的连接总可这样构成：自被链接国开始，逐一链接由部分邻国组成的国链。如图6示的一段近邻，就可参照图4与三色圈连接，连接后的构形仍为三色构形，各近邻和被链接国将构成若干三色圈围闭可能存在的各余域。依此类推构造其它近邻，最终形成的一个邻国圈将仍为三色构形，若干邻国围闭的可能存在的各个余域，包括先前暂未考虑的可能存在于各邻国或连线里边的余域，均由三色圈围闭。把若干近邻和被链接国构成的若干三色圈统称为近邻圈。同理可构造任一可能存在的内邻国圈，同样，把其最内层邻国构成的三色圈称为远邻圈，其它邻国构成的三色圈称为近邻圈。因此，可得结论：推论一：任一国家，其所有邻国构成的邻国圈，将由最内和最外层邻国组成的若干远邻圈及其它邻国组成的若干近邻圈构成，所有邻国最多只需三种构色，可能存在的各个余域均由若干邻国组成的三色圈围闭。2.3一个国家构色如上所述，将一个国家着上有别于其邻国圈的最多第四种颜色，将可满足着色要求。此时，该国家及其所有邻国总共最多只需四种构色，各余域由若干邻国构成的三色圈围闭。3双圈构形及其构色在上述任一由三色圈S1围闭的余域中对另一可能国家及其邻国继续构色，同理，该国家的所有邻国将构成若干三色圈，围闭余域中剩余的区域，其中，最外层邻国构成的三色圈S2将与S1共同围闭新余域，其它新余域全部由其自身邻国围闭，如图7示（其它可能三色圈未示）。S1、S2之间，各国家可能存在各种连接情况，部分或全部国家可能是两个三色圈的共同国家（简称共域），因此，S1、S2的着色不一定能够统一，S1、S2的组合构形不一定是三色构形，其中的新余域不一定由三色圈围闭。当S1、S2完全重叠时，全部国家均为共域，S1、S2为同一三色圈；当S1、S2之间各国完全不连接时，它们互不影响，各自可以统一的最多三种颜色构色，其中的新余域仍由三色圈围闭。而一般的组合构形，构色则比较复杂。由两个国圈及两圈之间各国的不同连接组合而成的构形称为双圈。下面对各种可能的双圈构形及其构色予以研究。3.1不可变构形及其连接如图8示，上下两条国链L1、L2，自左至右构造各链的国家及它们之间的连接。首先连接它们左端第一个国家组成基本链，而后在其右边每增加L1或L2一个国家时，该国总与L2或L1现有右端国连接，两条国链这种连接的构形称为不可变构形。不可变构形中不可能再添加国链之间的连接线，构形的这种连接称为充分连接。当所构造国家为L1、L2共域时，不可变构形终结，该共域为其单端域；或者当所构造国家不充分连接（即不与另一国链现有右端国连接）时，不可变构形也终结，构造该国前L1、L2各一个端国为其双端域。不可变构形两端不断构造国家，如果L1、L2闭合成圈前两端分别出现上述终结情况之一，不可变构形将不闭合。本节讨论的就是这种不可变构形，其端部按国家个数不同（即具有单端域或双端域）分两种形式，端部部分国家的一般构造形式如图9示。由图8可见，用A、B、C三种颜色对不可变构形构色时，选定相邻两国构色后，以后连接的每国因总是受到前面两国的约束，在三色中能且只能有一种选择，因此，不可变构形是三色构形，且确定其中相邻两国构色后，在三色范围内每国的着色将不可变。另外，构形中的每个余域均由三个国家围闭，即由三色圈围闭。不可变构形两种端部形式的不同组合，将构成三类构形：两端单域、单双域各一端、两端双域。不可变构形是一种关联构形，即用A、B、C三色对其构色，指定一端构色时，另一端的构色将受到关联而不能任意选择。根据不同类型及其两端构色的不同关联特点，不可变构形可分如下八种：同色构形、异色构形、双异构形、单异构形、顺单构形、错单构形、顺双构形、错双构形，其端部形式及构色特点如图10示。构造不可变构形并以某种形式终结后，再继续构造不可变构形时，这种构形称为两个不可变构形的连接。如图11（1）示，不可变构形的连接有如下三种基本形式：单铰连接：两个不可变构形共有一个单端域。双铰连接：两个不可变构形的同链双端域连接。可变连接：两个不可变构形的单端域连接。另外，不可变构形还可能出现图11（2）示等连接形式，它们相当于在不可变构形之间或在上述一些基本连接部位链接一个或一个以上国家，按照上面论述，这种链接不增加不可变构形或其连接构形构色，因此，研究不可变构形或其连接构形的构色时，可将所有国链链接构形先行约除，剩余的可能连接形式，就只有上述三种基本形式。双铰连接处的余域由四国围闭，如果这四国是三色圈，则必须至少有两国同色，且存在于对角，反之，如果有一个对角国同色，则双铰四国肯定是三色圈。因构成可变连接的两个单端域着色必定相异，因此，就其对不可变构形连接后的构色影响而言，两个