极大平面图最简非树型着色的统计分析与生成

《极大平面图最简非树型着色的统计分析与生成》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、第二节工具与方法我们所使用的主要软件是Maple数学软件，Maple中的networks工具包强大的图论计算功能，为我们的工作带来了极大的方便。我们的理论研究都是在许教授已有的研究成果基础上展开的，许教授的getSome4colors程序实现了求批量正常四着色。进一步，许教授又编写了getTfc程序，利用已找到的正常四着色生成相关联的全部四着色树，利用这种方法处理最小的65个极大平面图，53个图得到全部四着色解，而且这些解的数目通过色多项式得以验证是正确的。课题组在许寿椿教授的带领下，从“做例子”出发，用电脑作为工具(主要工作是用Maple在微机上完成的)，做尽量多的例图，设法给出它们的四着色

2、，努力发掘更丰富的涉及四着色属性的事实和材料。从对这些新材料的观察中发现规律，提出并论证猜想。作者继承了许教授的理论和研究方法，并在此基础上，通过计算实验、观察、猜想、论证，不断反复日口进的方法，得到了自己的～些研究成果，并建立了一个能够集中体现这些成果的极大平面图的对称性分析软件平台，其主要功能包括极大平面图四着色解的分类与统计，极大平面图自同构群的求解、极大平面图四着色解的自同构群+基着色的表示及两个极大平面图是否同构的判断，同时作者还编写了一些绘图函数，用以弥补对Maple软件在极大平面图绘制方面的不足。第三节术语和符号一、基本定义和符号本文中的术语与符号同于【1】，由于同构四着色等相关

3、概念为【1】中首次提出，还不为同行所知，择要重述如下：定义1同构含有n个点的两个图G=(V，E1)和图H=(U，E2)存在一个置换(o：i—o(i)，=1，2⋯n．；使vi—uo(i)。如果对G的任意边(v。，vb)∈Ej充分必要的有(uo(a)，u0(b))∈E2，就是说G与H同构，记为G竺H，此时称。为G与H的一个同构置换。定义2同构四着色与同构四着色类图G=(V，E)的一个四着色，是指如下的分解V=VIUV2tOV3UV4VlnV2=击i≠j若(u，v)∈E则必定有1．1，v属于不同的所，G的这样的一个四着色C可简记为C={Vl，V2，V3，V4}图G和它的两个四着色CI={VI’，V2

4、7，V37，V47}C2={Vl”，V2”，V3”，V4”)C，和Q各自的六个二色子图分别记为G7Ⅱ和G”o1≤i

5、、Gj3、G⋯G23、G24，规定出G12U(334．(V12uV34，E12U1334)=(V，Ea)构成的对偶二色子图为Ga，类似地，由G13uG24构成的对偶二色子图为Gb，由G14tOG23构成的对偶二色子图为Gc。定义4基着色集四着色集合CBase={cl，c2，⋯Ci⋯)，若CBase中任何两个元素都是相互不同构的，图G的任何一个同构着色类都在CBase中有代表元，则称CBase为图G一个基着色集，CBase中的每个具体元素称为一个基着色．二、四着色的分类和最简四着色的解释“四色问题”是近150年来始终未能完美解决的著名难题，不过值得可喜的是近年来许寿椿教授在极大平面图的四着色求解

6、方面取得了实质性的6喜人进展，根据文献[13】已经可以利用计算机获得大部分极大平面图的全部四着色，【1]中给出了用四着色求自同构群的几个定理和相关算法，再用四着色求解原图自同构群时，自然总要选择最简单类型的四着色。为此，我们先对大量例图的四着色进行一下仔细的观察与分类。在获得批量四着色的基础上，通过大量的实例的观察研究，发现根据四着色的对偶二色子图的类型，我们可以将四着色分为四种类型：T型，即该着色为2一树型，或说只有一组对偶二色子图为树型，如图1．2所示，其中图1—2．a为树型，图】．2．b和l一2．c都为非树型：TT型，即该着色为4．树型，或说有两组对偶二色子图为树型，如图1．3所示，其中

7、图l一3．a和1．3．b为树型，图1．3．c为非树型；TTT型，即该着色为6一树型，或说三组对偶二色子图全为树型，如图1-4所示，其中图I-4．a、l一4．b和1—4．c都是树型：noT型，即该着色为非树型，或说三组对偶二色子图全不是树型，如图1．5，其中图1．5．a、1．5．b和1．5．c都是非树型。随着问题的不断深入，只用T、TT、TTT和noT对四着色进行分类已经不能满足要求，例如由两条路构