与四色定理等价的几个命题

《与四色定理等价的几个命题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、应用数学MATHEMATICAAPPLICATA2000,13(3):59～62X与四色定理等价的几个命题谢力同刘桂真(山东大学数学研究所,济南250100)提要:本文论述与四色定理等价的几个新命题.从而给出了平面三角剖分及圈上的4染色集的一些新性质.将平面图的4可染色问题转化为圈上的4染色来研究,这将更便于用计算机来寻找关于四色定理的更简单的证明方法,也为探索四色定理的理论证明提供了新的途径和方法.关键词:图;平面三角剖分;四色定理;染色AMS(1991)主题分类:05C15四色定理于1976年由Appel和Haken用计算机进

2、行了证明.当时他们需要检查约1500个平[1]面图的可约性.1997年Robertson等人对四色定理给出了新的计算机证明,只需检查633个平面[2]图.但尚无理由说明所需检查图的个数已达到最少.近年来W.T.Tutte.等人仍希望对四色定理能给出一个理论证明或者找到更简单的计算机证明.Whitney和Tutte为了探讨四色定理的理论[3]证明曾将平面图的4染色化为圈上的4染色来研究并提出了一个蕴含四色定理的猜想.我们曾[4]证明了[3]中的猜想不成立,并提出了新的等价命题来修正[3]中的猜想.文献[5],[6]和[7]研究了与四

3、色定理有关的一些问题.文献[8]探讨了四色定理的理论证明,提出了新的等价命题.本文是文[4]的继续.提出了与四色定理等价的新命题.提供了新的方法来利用计算机或从理论上来探讨四色定理的新证明.另外本文的方法也可用来研究平面近三角剖分的新性质.本文中所考虑的图皆指无环连通图,它可以有重边.若能用n种颜色染图的顶点,使邻接的顶点有不同的颜色,则称该图是n可染色的,并称该染色为图的一种n染色.著名的四色定理是说任意平面图都是四可染色的.一个平面三角剖分是指每个面都是三角形面的平面图.设平面图G有一个指定的面的边界Q1是一个边数为r≥3的图

4、,其余面都是三角形面,则称它为以Qr为界环的平面近三角剖分.与四色定理等价的另一说法是任意平面三角剖分是4可染色的.我们将从这种等价性来讨论问题.设Qr是有r个顶点P1,P2,⋯,Pr的圈,其中Pi与Pi+1邻接,1≤i≤r,Pr+1≡p1(modr)且r≥3;记为Qr=(P1,P2,⋯,Pr).用Qr表示有r个顶点的界环,我们总假定Qr的顶点是标定的,即顶点的标号不同的图认为是不同的图.下面定义几种有关界环的运算.设G是以Qr为界环的平面近三角剖分.若r≥4,我们在以Qr为边界的面(可能是外部面)内33加一条新边e=P1Pr-1

5、,形成一个新圈Qr-1=(P1,P2,⋯,Pr-1),并从G得到一个新的以Qr-1=3(P1,P2,⋯,Pr-1)为界环的平面近三角剖分,记为G.当P1和Pr-1在G中邻接时,由于我们将新边X国家自然科学基金和高等学校博士学科点专项科研基金资助课题收稿日期:1999211230©1994-2009ChinaAcademicJournalElectronicPublishingHouse.Allrightsreserved.http://www.cnki.net60应用数学200033e加在以Qr为边界的面内,新图G没有以新边e和原

6、边P1Pr-1形成的面,即G仍为平面近三角33333剖分.G比G多一个面.将这种运算记为G=TG,Qr-1=TQr.′′′对r≥3,在以Qr为边界的面内取一个新点Pr+1,连接Pr+1与P1,Pr+1与Pr.用这两条新边代+++替Qr的边P1Pr形成一个新圈Qr+1.从G得到一个以Qr+1为界环的平面近三角剖分G.记这种运++++算为G=TG,Qr+1=TQr.′′′′′如果我们对Qr的顶点重新编号为P1,P2,⋯,Pr,使Pi+1=Pi,1≤i≤r-1,而P1=Pr,则得′′到一个与Qr编号不同的新的界环Qr.从G得到一个以Qr

7、为界环的平面近三角剖分G′.将这种运算′记为G′=PG,Qr=PQr.这里尽管G与G′是同构的,但按我们的约定,顶点标号不同的图G与G′应看为不同的图.文献[4]中证明了任意一个平面近三角剖分都可以通过连续运用上述三种运算从一个三角形得到.这就为证明平面图的某些性质提供了用归纳法的一种途径.图G是以Qr为界环的平面近三角剖分,则G的任意一个顶点染色就导出Qr上的一个染色.因[3,5]此人们将平面图的染色问题化为圈Qr上的染色问题来研究.显然每个圈都是4可染色的.设Sr•是圈Qr上所有4染色的集合,设2r是Sr的所有子集构成的集合.

8、设A={A,B,C,D}是圈Qr上的+一个4染色,其中A,B,C,D分别为染4种颜色的顶点集合.不妨设P1∈A,Pr∈B,A在TQr=+Qr+1上导出的染色为A′和A″,其中A′={A,B,C∪{Pr+1,D},A″={A,B,C,D∪{Pr+1}