论文部分内容阅读
【摘要】为了给四色定理问题的研究提供启示，本文对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
【关键词】四色定理;图论;平面图;数学归纳法
【中图分类号】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