一种平面图色数的计算方法

《一种平面图色数的计算方法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、一种平面图色数的计算方法（蒋友皎广西玉林市537000）0引言任何一个连通平面图都是五色图。但是后来在平面图上经过多次试验，没有找到一种平面图一定要用5种颜色的。在一百多年前，有人猜测只要用4种颜色就够了，这就是世界上著名的4色猜测问题。这个猜测一经提出，迷住了许多数学家，但是谁都无法用数学的方法证明它。直到1976年，Appel和Haken两人宣布了四色理论的证明方法。他们用大型电子计算机分析了2000多种图包括几百万种情况，花了大量的机器时间，终于证明了这个问题，[1]从而解决了一百多年来引人关注的难题。Sincetheprovingofthetheorem,efficientalgor

2、ithmshavebeenfoundfor4-coloringmaps2requiringonlyO(n)time,wherenisthenumberofvertices.In1996,NeilRobertson,DanielP.Sanders,PaulSeymour,andRobinThomascreatedaquadratictimealgorithm,improvingona[2][3][11]quarticalgorithmbasedonAppelandHaken’sproof.ThisnewproofissimilartoAppelandHaken'sbutmoreefficien

3、tbecauseitreducedthecomplexityoftheproblemandrequiredcheckingonly633reducibleconfigurations.Boththeunavoidabilityandreducibilitypartsofthis[4][11]newproofmustbeexecutedbycomputerandareimpracticaltocheckbyhand.In2001the[5][11]sameauthorsannouncedanalternativeproof,byprovingthesnarktheorem.In2005Benj

4、aminWernerandGeorgesGonthierformalizedaproofofthetheoreminsidetheCoqproofassistant.Thisremovedtheneedtotrustthevariouscomputerprogramsusedtoverify[6][11]particularcases;itisonlynecessarytotrusttheCoqkernel.显然这不是纯理论上的严格证明，在计算机的辅助工作下四色定理的证明完成了，但是是否存在不需要借助计算机的纯数学方法的证明呢？本文将运用方程组计算连通平面图的色数，对连通平面图的色数作出判定

5、。1基本性质定义1一个无向图是一个有序的二元组,记作G，其中（1）V≠称为顶点集，其元素称为顶点或结点。[7]（2）E称为边集，它是无序积V&V的多重子集，其元素称为无向边，简称边。定义2设G=为无向图，ek=(vi，vj)∈E，则称vi，vj为ek的端点，ek与vi或ek与vj是彼此相关联的。若vi≠vj，则称ek与vi或ek与vj的关联次数为1，若vi=vj，则称ek与vi的关联次数为2，并称ek为环。任意的vl∈V，若vl≠vi且vl≠vj，则称ek与vl的关联[7]次数为0。在图的定义中，用G表示无向图，D表示有向图，但有时用G泛指图(无向的或有向的)，可是D只能

6、表示有向图。另外，为方便起见，有时用V(G)，E(G)分别表示G的顶点集和边[7]集，若

7、V(G)

8、=n,则称G为n阶图，对有向图可做类似规定。在图G中，若边集E(G)=,则称G为零图，此时，又若G为n阶图，则称G为n[7]阶零图，记作Nn，特别地，称N1为平凡图。在图的定义中规定顶点集V为非空集，但在图的运算中可能产生顶点集为空集的运算结[7]果，为此规定定点集为空集的图为空图，并将空图记为。[7]无论在无向图中还是在有向图中，无边关联的顶点均称孤立点。定义3在无向图中，关联一对顶点的无向边如果多于1条，则称这些边为平行边，平行边的条数称为重数。在有向图中，关联一对顶点的有向边如果多于1条

9、，并且这些边的始点和终点相同(也就是它们的方向相同)，则称这些边为平行边。含平行边的图称为多重图，[7]既不含平行边也不含环的图称为简单图。定义4设G=为一无向图，v∈V，称v作为边的端点次数之和为v的度数，[7]简称为度，记做dG(v)，在不发生混淆时，简记为d(v)。定义5设G=为一平面图，面W由w条边组成，称w作为边的面次数之和为W的度数，简称为度，记做dG(w)，在不发生混淆时，简