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

论文摘要

本文首先应许教授利用四着色求极大平面图自同构与判断同构最好使用最简着色的理论要求,在对偶二色子图下对极大平面图的着色形态进行了繁简界定和特性码设置。以此对着色进行了区分,得到了由简到繁的着色形态如:PP型、PT型、TT型、SPP型、SPT型、STT型、CPP型、CPT型、CTT型…接着在对许教授求取着色程序的改进、完善与扩充的基础上提出了求取极大平面图所有着色的方案,并在程序上给予了实现。现在能求取阶数在40以下极大平面图所有着色或绝大部分着色,其中能实现求取所有着色图的最大阶数是43。进而利用上面方案处理了近百个例图,以不同的深度求取了它们的着色,给出了记录。然后统计分析了所得到的着色,发现从PP型到CPP型这7种最简单的着色类型就可覆盖这些个例图,而且发现了CPP型(最简非树型的一种)覆盖的例图个数最多,最简非树型这一大类着色类型覆盖了几乎所有例图(除了两个阶数很小的例图g9a、g12h)。接着单独对最简非树型这一大类着色进行了较为详细的统计分析,发现最简非树型着色不仅在极大平面图中覆盖面广,而且在找到的着色中涉及着色的比例也很高,高达85.25%。这一切凸现了最简非树型着色所占有的重要地位。接着对这一类着色本身,即它所含的圈连通分支与两树连通分支这两个结构部分分别进行了统计,并给出了一些相关性质。本文通过对一批非Hami lton三次图的对偶极大平面图的处理,对这一类图给出了一些认识,并提出了二元(多元)良偶性哈圈的概念,对Tait猜想进行了修整。本文还给出了利用最简非树型着色求极大平面图自同构的实例,尝试了用最简非树型着色判断极大平面图同构,给出了一些文献中所给图是同构图的实例。 本文后半部分在前面部分分析的基础上给出了三个直接寻找最简非树型着色的试探性方案。方案一从两个树连通分支的角度出发,利用极大平面图和其对偶图之间的关系,给出了以面扩树的方案。这一方案可在完全控制下完整的找出最简非树型着色,只是时效性不好,只能适用于阶数到21左右的图。己得到的着色中存在其对偶二色子图里连通片含圈较多的着色,对其圈上少许点的颜色作一下变换就有可能得到新的着色,同时也会将含圈的连通分支数减少,最后有可能使得其只含有一个含圈的连通分支,这就成了最简非树型着色,这就是方案二所采用的破圈法。这个方案时效性强,没有阶数的限制,可作拾遗之用,但是局限性很大—必须以含圈连通分支较多的着色为基础。方案三从阶数过大是一切己有着色算法计算时间指数级增长的根本原因、一些点数比较少的树在已找到着色的对偶二色子图中频频出现这两个事实出发,给出了给大图(阶数比较大的极大平面图)降阶的方案。图例使用了59阶的极大平面图,它的一个二次降阶图中经还原就找到了3760个着色,其中有1486个最简非树型着色,这说明由这个方案可以扩大处理图的范围,但时效性依然不好,所得着色不可避免的有缺失。本文最后综合分析了己有的着色方案,表明了从最简非树型着色中的圈连通枝部分或树连通枝部分出发寻找大图最简非树型着色的有效算法这一目标还没有达到;而只有通过综合利用上面的方案和导师提出的方案以扩大处理图的范围。 关键词:极大平面图,同构,最简非树型四着色,四着色算法,Tait猜想

论文目录

• 摘要
• Abstract
• 极大平面图最简非树型四着色的统计分析与生成
• 第一章 问题的说明
• 第一节 四色问题
• 第二节 工作基础、工具及进行的主要工作
• 第三节 基本概念和符号
• 第四节 本文例图的来源与说明
• 第五节 着色类型的繁简界定、特性码设置
• 第二章 求取全部着色方案与对所得结果的统计分析
• 第一节 对许寿椿教授求取着色程序的改进、完善与扩充
• 第二节 对各例图的系统处理与处理记录
• 第三节 各着色类型的图名表
• 第四节 各例图的最简着色与最简着色类的统计分析
• 第三章 最简非树型四着色的统计分析
• 第一节 最简非树型四着色的再分类、统计分析与相关性质
• 一.最简非树型四着色的再分类
• 二.对最简非树型四着色的统计分析
• 第二节 对例图着色观察分析获得的一些新认识
• 第三节 用最简非树型四着色求自同构与判断图同构的实例
• 一.用最简非树型四着色求自同构例子
• 二.用最简非树型四着色判断图同构例子
• 第四章 直接寻找最简非树型四着色方案之扩面状态树法
• 第一节 前言
• 第二节 相关术语和符号
• 第三节 三次图三边着色的若干性质
• 第四节 基于扩面的边三着色算法
• 第五节 计算实例
• 第六节 对扩面状态树方案的评价
• 第五章 直接寻找最简非树型四着色方案之破圈法
• 第一节 对已找到着色的形态分析
• 第二节 一种找新着色方法——破圈法
• 一.单稍生长破圈（一次只破一个圈的情况）
• 二.双稍生长破圈（同时破两个圈的情况）
• 第三节 相关计算结果
• 第四节 对破圈法的评价
• 第六章 直接寻找最简非树型四着色方案之降阶法
• 第一节 已找到着色的统计分析
• 第二节 图降阶的方法与步骤
• 第三节 降阶的实例
• 第四节 对降阶法的评价
• 第七章 对几个着色方案综合分析
• 致谢
• 参考文献