| 【中文题名】 | 极大平面图最简非树型着色的统计分析与生成 |
| 【英文题名】 | |
| 【学科专业】 | 基础数学 |
| 【论文级别】 | 硕士论文 |
| 【投稿时间】 | 2005-6-30 |
| 【中关键词】 | 极大平面图,同构,最简非树型四着色,四着色算法,Tait,猜想 |
| 【英关键词】 | maximal planar graph,isomorphic,chromatic polynomial,four coloring algorithm,Tait conjecture, |
| 【分类导航】 | 数理科学和化学>数学>代数、数论、组合理论>组合数学（组合学）>图论> |
| 【论文摘要】 | 本文首先应许教授利用四着色求极大平面图自同构与判断同构最好使用最简着色的理论要求,在对偶二色子图下对极大平面图的着色形态进行了繁简界定和特性码设置。以此对着色进行了区分,得到了由简到繁的着色形态如:PP型、PT型、TT型、SPP型、SPT型、STT型、CPP型、CPT型、CTT型…接着在对许教授求取着色程序的改进、完善与扩充的基础上提出了求取极大平面图所有着色的方案,并在程序上给予了实现。现在能求取阶数在40以下极大平面图所有着色或绝大部分着色,其中能实现求取所有着色图的最大阶数是43。进而利用上面方案处理了近百个例图,以不同的深度求取了它们的着色,给出了记录。然后统计分析了所得到的着色,发现从PP型到CPP型这7种最简单的着色类型就可覆盖这些个例图,而且发现了CPP型(最简非树型的一种)覆盖的例图个数最多,最简非树型这一大类着色类型覆盖了几乎所有例图(除了两个阶数很小的例图g9a、g12h)。接着单独对最简非树型这一大类着色进行了较为详细的统计分析,发现最简非树型着色不仅在极大平面图中覆盖面广,而且在找到的着色中涉及着色的比例也很高,高达85.25%。这一切凸现了最简非树型着色所占有的重要地位。接着对这一类... |
| 【论文题纲】 |
|
摘要 |
2-5 |
|
Abstract |
5-10 |
|
极大平面图最简非树型四着色的统计分析与生成 |
10-54 |
|
第一章 问题的说明 |
10-19 |
|
第一节 四色问题 |
10-11 |
|
第二节 工作基础、工具及进行的主要工作 |
11-14 |
|
第三节 基本概念和符号 |
14-16 |
|
第四节 本文例图的来源与说明 |
16-17 |
|
第五节 着色类型的繁简界定、特性码设置 |
17-19 |
|
第二章 求取全部着色方案与对所得结果的统计分析 |
19-26 |
|
第一节 对许寿椿教授求取着色程序的改进、完善与扩充 |
19-20 |
|
第二节 对各例图的系统处理与处理记录 |
20-24 |
|
第三节 各着色类型的图名表 |
24-25 |
|
第四节 各例图的最简着色与最简着色类的统计分析 |
25-26 |
|
第三章 最简非树型四着色的统计分析 |
26-35 |
|
第一节 最简非树型四着色的再分类、统计分析与相关性质 |
26-32 |
|
一．最简非树型四着色的再分类 |
26-30 |
|
二．对最简非树型四着色的统计分析 |
30-32 |
|
第二节 对例图着色观察分析获得的一些新认识 |
32-33 |
|
第三节 用最简非树型四着色求自同构与判断图同构的实例 |
33-35 |
|
一．用最简非树型四着色求自同构例子 |
33-34 |
|
二．用最简非树型四着色判断图同构例子 |
34-35 |
|
第四章 直接寻找最简非树型四着色方案之扩面状态树法 |
35-41 |
|
第一节 前言 |
35-36 |
|
第二节 相关术语和符号 |
36-37 |
|
第三节 三次图三边着色的若干性质 |
37-38 |
|
第四节 基于扩面的边三着色算法 |
38 |
|
第五节 计算实例 |
38-41 |
|
第六节 对扩面状态树方案的评价 |
41 |
|
第五章 直接寻找最简非树型四着色方案之破圈法 |
41-47 |
|
第一节 对已找到着色的形态分析 |
41 |
|
第二节 一种找新着色方法——破圈法 |
41-45 |
|
一．单稍生长破圈(一次只破一个圈的情况) |
42-44 |
|
二．双稍生长破圈(同时破两个圈的情况) |
44-45 |
|
第三节 相关计算结果 |
45-47 |
|
第四节 对破圈法的评价 |
47 |
|
第六章 直接寻找最简非树型四着色方案之降阶法 |
47-53 |
|
第一节 已找到着色的统计分析 |
47-48 |
|
第二节 图降阶的方法与步骤 |
48-49 |
|
第三节 降阶的实例 |
49-53 |
|
第四节 对降阶法的评价 |
53 |
|
第七章 对几个着色方案综合分析 |
53-54 |
|
致谢 |
54-55 |
|
参考文献 |
55-56 |
|
| 【DOI】 | LunWen.ID:2.2008.11514 |
