互动科普

本文以加德纳难四色图为例，具体介绍了我们的一个着四色算法．该算法可对给定的四连通极大平面图，给出多种四着色解。

一、加德纳难四色图

图1是著名数学专栏作家马丁·加德纳(Martin Gardner)在1975年4月1日的《科学美国人》上发表论文的附图．加德纳在原图下写了一句话：。四色定理被推翻了。正文中他说，这个地图不能用少于5种颜色，使相邻区域着不同色。他说这是四色猜想的反例。细读加德纳的文章得知，此图是他从美国一位图论专家1974年投给《组合数学》杂志的论文中摘引的。按常规运作，这篇论文要等到1978年才能刊出，加德纳在得知此文后抢先公布了。加氏恐怕没有经由专业专家的评审，他这种作法是严肃、认真的吗?原来这期《科学美国人》的出版日：4月1日，是美国的愚人节。按美国习俗，这一天是可以大开玩笑、制造奇闻的．因而，尽管加德纳氏行文认真、严肃，论说肯定，但我们不能认为这是美国科学家认真研究的正式结论。这只是某个或某些美国科学家的看法，由于原图制作者是专业图论专家，这表明按当时研究工作状况，这张图的四着色是不易给出的．我们就姑且以。加德纳难四色图称之．

图1中各区域(国家)的边界都是直线．其实，数学上考虑地图着色时，其边界形态、区域大小都并不重要．重要的是国家间的邻接关系．为了集中研究这本质的邻接关系，数学家把地图(Map)着色转化为图(GraPh)的点着色。图(Graph)是离散数学中的对象。图2便是地图图1相对应的图(Graph)。图有两个要素：点集和边集。对图1中的每个区域都取一点(可以设想该点是该国的首都)，两个国家有公共边界时，便把两国家对应的点用一条边相连接(可以设想这边是连接两国首都的路)。图2与图1是对应的。图1的区域四着色，使相邻两国着不同的颜色，等价于图2的节点着四色，使每个边的两国着不同颜色。图2中1号点对应于图1中1号区域，⋯。细心读者会发现图2共有109个点。这是因为图1中11O号区域被3个区域包围。与之对应的110号点应落在图2的三角形89，90，108之间，是三度点。图2有了正常四着色时，89，90，108因两两相邻，而着三种不同颜色。其中110区域只要着第四色就可以了。我们以后所说的加德纳难四色图，更多时候便指图2。图2有109个点，作为讲解用图，它要占用较大版面。为简化和节省，我们给出与图2结构相类似的图3。讲解算法步骤时常用图3为例。图3的节点数是41。以后我们也用G109、G41分别标识图2和图3中的图。这正是我们研究的四连通极大平面图。G41实际上是简化的加德纳图。

二、简化加德纳圈G41的两个四着色的手工模拟

我们先以G41为例，以人工模拟的方式介绍算法的主要步骤．对G41这样的图，要直接给出正常四着色．至今并无有效办法．我们不妨为了进一步先退两步．先给出一个有冲突边(该边两靖着相同颜色)的四着色，再设法把冲突边消减，直至冲突边敷为零．

观察图3可见，这是以1号点v1为参照点的层圈结构图。与v1相邻的点(2，8，4，5)组成四圈；和v1距离为2的点组成总六圈(6，7，8，9，10，11)；⋯距离为5的点组成十一圈。对每个圈都着二色，便得图3a。该着色有四条冲突边：(30，40)，(30，38)，(30，36)，(34，36)。这些冲突边两靖点都着●。与●相关的二色子图有G(●，▲)、G(●，O)、G(●，△)．图3a中用粗实线标出二色子图G(●，▲)．观察G(O，△)，可见，它包含一个三圈：(29，20，40)，其余的边都不在任何圈上，对G(●，△)重新着二色，除三圈上必然要保留一个冲突边，其它冲突边均可消去．图3b便是处理结果f可以把它看成是图3a中对G(●，△)以40为参照点，距离为奇数的着△，为偶数的着。得到的。其中仅剩下一个冲突边(29，30)在图3b中粗实线标出G(△，▲)的一部分．冲突边(29，30)不是任何圈的边．在粗实线标出的子图上，从29，19⋯3各点的枝上做二色变换，便可消去冲突边(29，30)得正常四着色如图3c。

为了全面说明消冲突边操作，我们再看例子图4。图4a的着色，是以20号点为参考点，逐层着二色得到的。距离为1、3的层着▲、●，距离为0、2、4的着△、O。可以证明，距参考点距离为常数的点生成子图是外平面图。外平面图都可着三色．当用二色时便可能产生冲突边。图4a显示，除20号点的邻圈(第一层)外，其它各层都有冲突边。全部冲突边共8条，在图中用粗线标记。图4a中又用粗实线标出二色子图G(O，▲)，用粗虚线标出G(●，△)。从图上可见，冲突边(2。5)、(3．4)在G(●，△)的偶圈上．冲突边(6，11)、(8，9)在G(O，▲)的偶圈上，偶圈可以着二色，故此四条冲突边易消去．又冲突边(15，16)不在G(△，●)的任何圈上。在路15-14-18-12上做二色变换，可消去它。消去这5条冲突边后的结果见图4b。图4b上还剩下3条冲突边。用粗实线标出G(●，O)。可见冲突边(17，20)、(28，39)均非圈边，易消去。消去后仍留一冲突边的图见图4c。观察4c可知，冲突边(23，34)于其所在的三个二色子图G(▲，●)、G(▲，△)、G(▲，O)中都在奇圈上。(且其所在两个三角形之另两顶点33、24同为●)。这种冲突边无法直接用二色变换消去．我们就先把它‘移位’。只要把冲突边一端，如点34着O，冲突边便变为(34，35)(见图4d)。观察图4d可知，冲突边(34，35)其所在三个二色子图中仍都在奇圈上。这三个奇圈包括两个三角形24—34—35和34—35—36。此时以冲突边为边的两三角形之另两顶点，24着●，36着△。此种情况下，可证明点36和点24必分属△，●不同连通片，通过一片的二色变换，可能破坏掉冲突边所在的O-△圈。就本例，可在(△，●)二色片36—33—32—31上做二色变换，得图4e．此时冲突边34—35便是二色子图G(△，O)上的非圈边，极易消去．只需把35号点改为△即得正常四着色．

就图3、图4看，可以把消冲突边操作原则小结如下：

(1)对每个含冲突边的二色子图进行处理．当冲突边是非圈边，或冲突边在偶圈上时，对二色子图的重着色可消去这种冲突边。

(2)当冲突边在奇圈上时，对该二色子图重着色，可消去奇圈上多于1个的冲突边，仅保留一个冲突边。

(3)当某冲突边于其所在三个二色子图中都在奇圈上时，并且以此冲突边为对角线的四边形另两点同色化，再重做。

(4)当某冲突边于其所在三个二色子图中都在奇圈上时，可将以此冲突边为对角线的四边形另两顶点也已同色化时，可将冲突边移位后重复以上操作。

(5)上述对某二色子图的各操作，对于其对偶二色子图，或对于本二色子图的其它片都不会造成冲突边的变化．这是二色子图的封闭性。

三、加德纳难四色图的两个四着色解

我们关于四着色算法的实验研究是针对一般四连通极大平面图的．在我们自感设计的算法获得基本成功，在寻找更多例子试算时见到加德纳图。得到该图不久后，我们便计算出它大量的四着色解。由于有了二中G41的具体模拟过程，下面略去各种图，只给出最后结果和步骤的简要说明。

图2中标出的一个四着色，是以图3所示的类似方法得到的。对图2原图，以v1为心的层圈结构中，奇层圈着▲，●二色，偶层圈着△，O二色。开始冲突边有8条，两端点均着●，先利用●-△子图消去6条．剩下两条冲突边(90，108)、(90，100)均为(●，●)型．将108，100改着O，使冲突边移位于(88，108)、(100，109)均为(O，O)型．对108所在片做▲-△色变换，使(88，108)两侧同色化，再对91，109，93⋯所在(O，△)片做二色变换，便得正常四着色，如图2所示．

G109的另一个正常四着色，不再画图，只给出各种颜色的点集分解．该着色步骤与图4相仿．先取72号点为心建立层结构．奇层着▲、▲，偶层着△，O。再进行消冲突处理．最初的冲突边为10或12条．利用●-△和O-▲两子图可消去6条．下面给出一个可能的结果：△：4，7，15，17。19，21，25，33，38，40，44，47，49，55，57，66，68，72，75，7776，82，88，92，100，104，106

O：1，6，8，10，22，24，27，29，31，37，42，45，48，53，61，65，67，70，74，76，80，86，89，96，101，103，107，109，

▲：2，9，11，13，20，23，26，28．35，41，43，46，5052，59，63，69，71，73，78，81，83，85，90，94，98，

●：3，5，12，1416，18，30，32，34，36，39，51，54，56，58，60，62，64，84，87，91，93。95，97，99，102，105，108．

通过多方案计算，包括不同的产生非正常四着色方法及各方法中选择不同动态，我们已经获得加氏图G109的大量四着色解，这些解可待适当时候在因特网上交流。

本文所介绍的算法以作者对极大平面图结构的研究[1—5]为基础．参加本项目的有刘恒军、杨丽丽、潘晓南、许怀皓、尹崇武，朱英等．

图1加德纳难四色地图

图2加德纳难四色图及一个正常四着色

图3简化加德纳图G41的一个四着色过程示意

图4简化加德纳图G41的又一个四着色过程示意