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

不包含三边形四边形五边形的极图

作　者: 董国承
导　师: 杨元生
学　校: 大连理工大学
专　业: 计算机软件与理论
关键词: 极图禁止子图笼正则图围长
分类号: TP391.41
类　型: 硕士论文
年　份: 2003年
下　载: 44次
引　用: 0次
阅　读: 论文下载

内容摘要

图论（Graph Theory）是数学的一个分支，它与数学的其他分支有密切的关系。这些分支包括群论、矩阵论、数值分析、概率论、拓扑学和组合论等。事实上，图论为任何一个包含二元关系的系统提供了一个数学模型；利用图直观、漂亮的表现特性可以使人对现实的系统有清晰的了解。这个领域内的许多问题，即使是对图论一无所知的人，都是非常容易理解的，但是想要得到这些问题的结论却要使聪明的数学家绞尽脑汁。随着计算机科学与数学的发展，图论已经应用到了各个领域，其中包括物理学、化学、通讯科学、计算机技术、土木工程、建筑学、运筹学、生物遗传学、心理学、社会学、经济学、人类学和语言学等等，几乎包括了人类社会的所有领域。图论已经成为人们研究自然科学以及社会科学的一个重要工具。极图理论是图论中的重要组成部分。极图问题中最主要的一类问题是：给定一族图ψ={G₁，G₂,…，G_m}，ex（n；ψ）表示由n个顶点组成的不包含任一G_i∈ψ的图的最多边数。EX（n；ψ）表示由n个顶点组成的不包含任一G_i∈ψ 的边数最多的图（极图）的集合。在不包含多边形的极图问题中，对于ψ={C₄}的极图问题，Clapham等人给出了所有n≤21的极图（Journal of Graph Theory，Vol．13，no．1，（1989），29-47），杨元生等人给出了所有22≤n≤31时的极图（UTILITAS MATHEMATICA，41，（1992），204-210）；对于ψ={C₃，C₄}的极图问题，Garnick等人给出了n≤24的所有极图（Journal of Graph Theory，Vol．17，no.5，（1993），633-645）．本文主要研究了ψ={C₃，C₄，C₅}时的极图问题，给出了n≤42时ex（n；{C₃,C₄,C₅}）的值以及n≤42时所有的极图集合EX（n；{C₃,C₄,C₅}）：对于n＞42时的情形，本文给出了ex（n；{C₃,C₄,C₅}）的上界。

全文目录

0 前言  6-7
1 极图的相关概念  7-15
  1．1 本文涉及的图论概念  7-10
    1．1．1 图的基本概念  7-8
    1．1．2 路  8
    1．1．3 树  8-9
    1．1．4 常用的图和标记  9
    1．1．5 常用的图的运算  9-10
  1．2 极图理论  10-15
    1．2．1 Tur（?）n原始极图问题  10-14
    1．2．2 一般极图问题  14-15
2 不包含多边形的极图问题  15-17
  2．1 不包含禁用三边形的极图  15
  2．2 不包含禁用四边形的极图  15
  2．3 不包含禁用三边形、四边形的极图  15-16
  2．4 一些其他的极图结论  16
  2．5 本文工作  16-17
3 不包含三边形四边形五边形极图的边数  17-41
  3．1 基本的定义  17
  3．2 基本引理  17-20
  3．3 顶点个数不超过42的不包含三边形四边形五边形的极图边数  20-41
4 不包含三边形四边形五边形极图的构造  41-54
  4．1 构造极图算法分析  41-42
  4．2 FEG算法的基本步骤  42-44
  4．3 FEG算法正确性的证明  44-45
  4．4 FEG+算法及正确性证明  45-54
5 研究结果  54-57
6 进一步工作和展望  57-58
7 参考文献  58-59
8 致谢  59-60

不包含三边形四边形五边形的极图

内容摘要

全文目录

相似论文