时间：2022-10-23 01:19:50
【摘要】为了给四色定理问题的研究提供启示，本文对N元环经过三角形划分后所得平面三角形拼接图的着色问题进行了研究，本文结论可归纳如下.（1）任意N元环划分所得三角形拼接图均含有N-2个三角形和N-3条非环上边.（2）任意N元环划分所得三角形拼接图中，至少存在两个三角形由连续三个环上点构成.（3）任意N元环划分所得三角形拼接图都符合三色定理.
【关键词】四色定理;图论;平面图;数学归纳法
【中图分类号】O157 AMS（2000）主题分类：05C15
【基金项目】阜阳师范学院自然科学项目（2013FSKJ05ZD， 2014FSKJ01ZD）
一、引 言
四色定理是图论中未经证明的一个问题，这一看似简单的问题被认为是近代三大数学难题之一.这一定理指出，对于任何地图，采用四种颜色对各个国家进行着色即可保证任何两个相邻国家具有不同的颜色，这一问题于1852年由英国制图员Guthrie提出，距今已有160余年时间.1879年Kempe最早提出被称作Kempe链的“换色法”对于这一假设进行了证明.但1890年，Heawood发现Kempe的证明过程中存在错误，指出Kempe实际证明了任何地图均可实现五着色的命题.1976年，美国数学家Appel、Haken和Kock曾采用计算机经过一百多亿次逻辑判断方法证明了四色定理;但直到21世纪，纯粹的数学证明方法依然没能获得.
为了给四着色问题的研究提供启示，本文将进行一类由N个顶点形成的多边形划分为三角形拼接图后所得图形着色问题的研究.本文将按如下顺序进行论述.首先介绍地图着色问题的简化处理以及文献中五色定理的染色方法，然后讨论N元环三角形拼接图的性质，最后证明N元环三角形拼接图符合三色定理.
二、五色定理简介
文献中五色定理的介绍很多，但由于多数文献采用图论专业术语进行描述，所以无法达到浅显易懂的效果.为此，本文作者打算用通俗语言对五色定理进行重新描述，以尽可能地达到无论专业数学工作者或业余数学爱好者均能看懂的效果.
1.地图着色问题的简化处理
一般在研究地图着色问题中可先对地图进行“点面翻转”操作，这一操作可具体描述如下.考虑一类简单地图，地图中只存在三个国家交界点的情况且每个国家周围至少有三个邻国.此时，每个国家都可看作多边形“面”，每个三国交界点即为一个“点”;整个地图有数个多边形“面”和数个三国交界“点”构成.现把原地图中每个多边形“面”变成一个“点”同时把每个三国交界“点”看成一个“面”.如果两国交界，则用一条线把代表两个国家的点连接起来.此时原地图中所有三国交界点均会变成三角形面，原地图变成由三角形面拼接而成的多面体图形.为了简便起见，本文把这种经“点面翻转”后获得的由三角形拼接而成的多面体叫做“TH体”（其中T取自triangle，H取自hedron）.原地图的四着色问题变为研究TH体的四着色问题（下文中字母代表国家，面代表多国交界点）.
图1 四国交界点示例 以上TH体中只有三个国家交界的情形，如果实际地图中存在四个或四个以上国家共享一个交界点的非TH体情形（如美国地图有四州共用交界点情形）或其他如国中之国以及一个国家只和两个国家交界的非TH体情形等，均可转变为TH体.例如一个国家若只与两个国家交界，则可以先去除这个国家，待完成着色问题后，再将这个国家增添到原来的位置，染上与周边两个国家不同的颜色即可.再如，存在四国交界点的情形也可转变为TH体.如图1所示（图1中非四国交界区未画出），图1（a）中A，B，C，D四点代表四个国家，四边形面ABCD代表四国交界点.此时图1（a）不属于TH体.但若连接图1（a）中AC两点，即可将图1（a）变为如图1（b）所示的TH体.若图1（b）符合四色定理，则断开AC连线后，所得图形必然符合四色定理.也就是说，非TH体的着色问题均可通过TH体的着色问题完成.
2.五色定理的相关介绍
五色定理可用数学归纳法证明;即已知四个国家构成的地图符合五色定理，现假设N个国家构成的地图符合五色定理，那么若能在此基础上证明N+1个国家构成的地图符合五色定理，则命题成立.现以TH体为地图基本模型描述五色定理的证明过程.
我们先来考察TH体的相关性质.TH体是一种多面体，依据多面体欧拉公式，顶点数（N）、面数（F）、边数（E）符合式（1）.TH体中每条边被两个面共享，每个面均由三条边构成，所以有式（2）成立，且由式（1）和式（2）可得式（3）.假设TH体中每个点均与其他6个或6个以上点相连，考虑到每条边被两个顶点共用，可知TH体的边数E与顶点数N关系符合式（4）.由于式（4）与式（3）矛盾，可知以上假设不成立.即任意TH体中至少有一个顶点只与5个或5个以下其他顶点相连.
N+F=E+2.
（1）
2E=3F.
（2）
E=3N-6.
（3）
E≥3N.
（4）
因此，对于一个N+1顶点的TH体，必有一个顶点只与5个或5个以下其他顶点连线.若此点与其他3个顶点相连，则可去除此点以及由此点引出的三条连线，获得一个N顶点的TH体.依据假设，此N顶点TH体可进行五着色.待着色完成后，再把刚去除的这个顶点添加到N顶点TH体原位置上并染上与周围三点不同的颜色，即可完成N+1顶点TH体的五着色过程.若N+1顶点TH体中有一点与其他四点相连，则去除此点后将产生一个四边形，把此四边形划分为两个三角形后可获得一个N顶点TH体.依据假设 N顶点TH体可五着色.待着色完成后将去除的点添加到N顶点TH体原位置上并染上与周围四点不同的颜色，即可完成N+1顶点TH体的五着色过程.若N+1顶点TH体中有一点与其他五点相连，如图2（a）中A点，则需检查B点和D点间有无连线，分别考察B和D有无连线两种情况.
图2 A点与周围五点相连情况 若B和D有连线，则存在三角形面ABD（此三角形面不属于原N+1顶点TH体的外表面），沿着ABD所在的面将TH体切割为左边和右边共两个共享面ABD的TH体;这两个TH体的顶点数均小于或等于N，所以这两个TH体均可五着色.假设用Ⅰ、Ⅱ、Ⅲ、Ⅳ、Ⅴ五种颜色对左边TH体着色，并把A，B，D分别染上Ⅰ、Ⅱ、Ⅲ三种颜色.再假设对右边TH体采用（1）、（2）、（3）、（4）、（5）五种颜色进行着色，把A，B，D分别染上（1）、（2）、（3）三种颜色.然后用一组新的颜色1、2、3、4、5对以上两个TH体进行换色操作.用1取代两TH体中的Ⅰ和（1），用2取代两TH体中的Ⅱ和（2），用3取代两TH体中的Ⅲ和（3），用4取代以上两TH体中的Ⅳ和（4），用5取代两TH体中的Ⅴ和（5）.则换色后两个TH体中A，B，D三点对应颜色均为1，2，3.再沿着原切割面ABD把两个TH体对接起来即得一个符合五色定理的N+1顶点TH体.
若B和D无连线，则去除A点，并把B和D融为一点，如图2（b）所示.此时N+1顶点TH体变为N顶点TH体，依据假设，任何N顶点TH体均可五着色.待图2（b）对应的N顶点TH体完成五着色后，将去除的A点恢复并染上与周围四点不同的颜色即可完成 N+1顶点TH体的五着色过程.至此，我们完成了任意N顶点TH体的五着色证明.
三、N元平面TP图的着色问题
设有N个点两两相连构成一个平面N元环.现对平面N元环中的任意两点进行两两相连（要求连线过程中保持任意两条连线不相交）对N元环进行切割划分，直至原N元环内没有四边形或四条边以上的多边形为止，此时称获得的平面图叫“N元平面TP图”（其中T取自triangle，P取自polygon）.例如，图3即为N=11和N=12两个N元平面TP图的结构示例.接下来我们来研究N元平面TP图的性质.
图3 N=11和N=12的两个TP图 1.N元平面TP图的结构
定理1：N元平面TP图中有N-2个三角形和N-3条环内边.
证明：N元平面TP图有N条环上边;设图中有K条环内边和F个三角形.因为每条环内边被用来构建两个三角形而每条环上边只被用来构建一个三角形，所以可得边数与三角形数的关系式（5）.
2K+N3=F.
（5）
对于一个N元环，在划分为TP图过程中内角和不变.所以F个三角形的内角和等于原N元环的内角和，由此得出式（6）.显然F=N-2，进而可得K=N-3.即N元平面TP图中有N-2个三角形和N-3条环内边，证毕.
180F=180（N-2）.
（6）
定理2：N（N>3）元平面TP图中，至少有两个三角形为原N（N>3）元环上紧邻三点构成的三角形.
证明：N元平面TP图可视为由N-2个三角形拼接而成，且此时图中有N-3条环内边和N条环上边.显然，当N大于3时N元环上任何连续三条边不能形成三角形.所以N元平面TP图中的任何三角形，不可能拥有三条环上边，即N元TP图中任意三角形最多拥有两条环上边.另外，在N元TP图中，任意一条环上边不可能参与构建两个或两个以上的三角形.现N顶点TP图中有N-2个三角形，有N条环上边.为了尽量少地出现一个三角形拥有两条环上边的情况，可让每个三角形均拥有一条环上边;此时N-2个三角形共用去N-2条环上边，但还剩下两条环上边.由于任何三角形不能拥有三条环上边，所以这两条环上边只能分别分配到两个三角形中去.这就造成N（N>3）元TP图中至少有两个三角形拥有两条环上边.只有环上紧邻三点才可构成属于同一个三角形的两条环上边，所以至少有两个三角形为N（N>3）元环上紧邻三点构成，证毕.
若把某个拥有两条环上边的三角形从N顶点TP图中切除，则可得一个N-1元TP图，即为这个被切除的拥有两个环上边的三角形可看作外接在N-1元TP图上;我们把这种拥有两个环上边的三角形称为“外接三角形”.
2.N元平面TP图的三着色证明
图4 当N=3，4，5时TP图的三色方案 当N=3，4，5时，若不考虑TP图中各个点的差别以及各条边长的差别，则所得TP图均只有如图4所示的一种结构花样（其他结构花样可由图4经旋转获得，不能独立存在）.如图4所示（图中1，2，3表示三种颜色），N=3，4，5时对应TP图均可三着色.
定理3：任何N元平面TP图都可三着色.
证明：现采用数学归纳法证明定理3，假设N元TP图可以实现三着色，再证明N+1元TP图也可三着色.定理2指出，N+1（N>3）元平面TP图中至少有两个外接三角形，现把其中的一个外接三角形标记为ABC;其中AB和BC均为环上边，AC为非环上边.则沿着AC边切去外接三角形ABC，可获得一个N元平面TP图.即此N+1元平面TP图可以看作由一个N元平面TP图和一个三角形拼接而成.显然，切去的三角形是可三着色的，设其三种颜色为Ⅰ、Ⅱ、Ⅲ.依据数学归纳法假设，N元平面TP图可三着色.现对切割后产生的N元TP图进行三着色，设对应三种颜色为x、y、z.假设对切割后产生的N元TP图和三角形ABC分别进行三着色.设N元TP图中点A和点C分别着色为x和y（其他点着色暂不考虑）;三角形中A，B，C三点分别着色为Ⅰ、Ⅱ、Ⅲ.现用另外三种颜色1，2，3取代N元TP图和三角形ABC的颜色.取代操作规定为：用1取代x和Ⅰ;用2取代y和Ⅲ;用3取代z和Ⅱ.经过颜色取代后，N元TP图和三角形ABC中点A均为颜色1，点C均为颜色2;现把两图沿切割边AC拼接起来，则所得N+1元TP图只具有三种颜色1，2，3，即为N+1元TP图可三着色.结合图4中N=3，4，5时可三着色的事实，可知任意N元TP图均可三着色，证毕.
四、结 论
本文研究了由N元环经连线划分所得N元平面TP图的性质.得出N元平面TP图中有N-2个三角形和N-3条环内边;且所得三角形中至少有两个三角形为N元环上紧邻三点构成.并在此基础上证明了N元平面TP图是可三着色的.本文结论对四色定理的证明有一定的启示意义.在接下来的工作中，我们将在此基础上逐步展开关于四色定理的后续研究工作.
【参考文献】
[1]王利民，张利明，吕国：使用四色定理求解图形着色的数学模型[J].河北建筑工程学院学报，2006（24）：102～103.
[2]王礼萍，王慧蓉：平面图四色问题的一个必要定理[J].哈尔滨师范大学自然科学学报 2003（19）：29～30.
[3]Kempe，A.B.：On the geographical problem of the four colours[J].American journal of mathematics 1879（2）：193～200.
[4]Kempe，A.：How to color a map with four colours without coloring adjacent districts the same color[J].Nature 1879（20）：275.
[5]Heawood，J.：On the fourcolor map problem[J].Quart.J.Pure Math 1898（29）：270～285.
[6]陈明，李刚：四色定理证明的探讨[J].山东理工大学学报：自然科学版 2013（27）：10～12.
[7]Appel，K.，Haken，W.，Koch，J.：Every planar map is four colorable.Part II：Reducibility[J].Illinois Journal of Mathematics 1977（21）：491～567.
[8]谢力同，刘桂真.与四色定理等价的几个命题[J].应用数学 2000（13）：59～62.