学位论文 > 优秀研究生学位论文题录展示

几类特殊平面图上的二人对策着色

作　者: 沈邦玉
导　师: 周兴和
学　校: 南京师范大学
专　业: 运筹学与控制论
关键词: 对策着色放松对策着色可行色放松对策色数二叉树树外部平面图三角剖分拟对偶图最小控制集轮图扇图
分类号: O225
类　型: 硕士论文
年　份: 2004年
下　载: 35次
引　用: 0次
阅　读: 论文下载

内容摘要

这篇文章讨论在图上的二人对策着色：设t，d是正整数，X是t种颜色的集合。由Alice开始，Alice和Bob两个人轮流选取X中的颜色对图G的顶点进行着色，每次每人着一个顶点。如果图G的顶点x着颜色c后，由图G着颜色c的顶点导出的子图的顶点最大度至多是d，则称颜色c对顶点x来说是可行色。每次Alice和Bob必须用可行色对图G的未被着色的顶点进行着色。如果图G的所有顶点都被着色或者还有顶点没有可行色去着色，则着色结束。Alice的目标是实现对图G的所有顶点进行可行着色，而Bob的目标就是要破坏Alice实现她的目标。这篇文章主要运用分裂已着色顶点的方法证明了如果图G是树的学位论文">二叉树，且d≥2，则x_g^（d）（G′）≤2。如果图G是树且d≥3，则x_g^（d）（G）≤2设G是外部平面图且d≥2，G′是G的2-连通的三角剖分。若T_G′是一条路，则x_g^（d）（G）≤5。设G是外部平面图且d≥3，G′是G的2-连通的三角剖分，D是T_G′的最小控制集。若T_G′[D]是一条路，则x_g^（d）（G）≤5。另外还讨论轮图与扇图的对策着色。

全文目录

摘要  4-5
Abstract  5-6
1 前言  6-13
  1.1 基本概念  6-8
  1.2 图的着色与对策着色  8-10
  1.3 已有的相关结论  10-13
2 树上的对策色数  13-24
  2.1 二叉树上的对策着色  13-21
  2.2 树上放松度为3的对策色数  21-24
3 外部平面图上的对策着色  24-28
4 轮图与扇图的对策色数  28-31
参考文献  31-34
致谢  34

几类特殊平面图上的二人对策着色

内容摘要

全文目录

相似论文