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

有向图中若干问题的研究

作　者: 徐根玖
导　师: 李学良
学　校: 西北工业大学
专　业: 应用数学
关键词: Caccetta-H(?)ggkvist猜想 Seymour二出度猜想围长顶点度点可迁图原子原子匹配原子收缩图结合数
分类号: O157.5
类　型: 硕士论文
年　份: 2004年
下　载: 163次
引　用: 1次
阅　读: 论文下载

内容摘要

本篇论文主要研究有向图中的有向圈，讨论有向图中的围长g（D）（最短有向圈的长度）与图的顶点度以及结合数之间的关系，并重点分析了点可迁图类。论文源自于有向图中两个具有一定相关性的猜想： Caccetta-H（?）ggkvist猜想若有向图D满足δ⁺（D）≥d，那么g（D）≤[n/d]。 Seymour二出度猜想任一有向图D中都存在顶点ν∈V（D），使得|N⁺⁺（ν）|≥|N⁺（ν）|。在论文的第一章，我们介绍了论文中涉及的一些基本的图论概念和术语，本论文的研究内容以及论文中所得到的主要结果。第二章综述了上述两个猜想的研究进展。重点介绍了Caccetta-H（?）ggkvist猜想的特殊情形：d≥n/3，给出了与Caccetta-H（?）ggkvist猜想或其特殊情形等价的相关猜想。证明了Seymour二出度猜想成立等价于该猜想在强连通有向图上成立。第三章讨论理论和应用上都非常重要的特殊图类——可迁图。我们将许多无向点可迁图的结果平行地推广到有向点可迁图中，同时得到了一些不同与无向图情形的结论。证明了Caccetta—H（?）ggkvist猜想和Seymour二出度猜想均在可迁图上成立．重点讨论了点可迁图的连通性及连通度，提出了原子匹配、原子收缩图、原子稳定子群等一些新的概念，在此基础上进一步分析了点可迁图的结构特征，完善了现有的点可迁图的连通性理论。特别地，给出了Cayley图连通度的精确表达式，推广并改进了Doorn和孟吉祥的结果，并在最后分析了一些达到最优连通度的Cayely图类。第四章将有向图的度条件（顶点的邻域）与围长的关系进行了推广，考虑结合数（点集合的邻域条件）与围长的关系。由于若无向图G的结合数b（G）≥3/2，则G中存在三角形，而Caccetta-H（?）ggkvist猜想研究有向图中存在有向三角形的条件，受此启发，我们在有点向图中引入结合数的概念。在此基础上，论文讨论了有向图结合数的性质，得到了结合数的范围并论证了给定结合数的有向图的摘要存在性，提出了关于结合数与围长之间联系的两个猜想.同时，还给出了几类特殊有向图的结合数，并分析了结合数与有向图连通性及连通度之间的关系. 最后，我们对本论文的结果加以总结，归纳了文章中提出的或遗留的问题，给出了论文中提到的有向图中尚未解决的猜想之间的相互关系，并对进一步的研究给予展望.

全文目录

摘要  3-5
Abstract  5-9
第一章绪论  9-19
  1.1 引言  9-10
  1.2 问题的引入  10-12
  1.3 本文的主要研究工作和研究成果  12-19
第二章有向图中的两个重要猜想  19-25
  2.1 Caccetta-H(?)ggkvist猜想  19-23
  2.2 Seymour二出度猜想  23-24
  2.3 本章小结  24-25
第三章可迁图及Cayley图  25-48
  3.1 可迁图及Cayley图的定义  25-32
    3.1.1 有向图的同构与可迁  25-28
    3.1.2 群的图表示及Cayley图  28-32
  3.2 原子，原子匹配  32-34
    3.2.1 原子及其性质  32-33
    3.2.2 原子匹配  33-34
  3.3 原子收缩图及其稳定子群  34-38
    3.3.1 原子收缩图  34-36
    3.3.2 原子的稳定子群  36-38
  3.4 点可迁图与中子  38-40
  3.5 C-H猜想和Seymour二出度猜想在点可迁图上成立  40-42
  3.6 Cayley图的连通度与K-优性  42-47
    3.6.1 可迁图和Cayley图的连通度  42-44
    3.6.2 Cayley图的k-优性  44-47
  3.7 本章小结  47-48
第四章结合数与围长  48-56
  4.1 有向图结合数的定义  48-50
  4.2 给定结合数的有向图的存在性  50-52
    4.2.1 特殊有向图的结合数  50-51
    4.2.2 具有给定结合数的有向图的存在性  51-52
  4.3 结合数、连通性与围长  52-55
    4.3.1 有向图的结合数与连通性  53
    4.3.2 有向图的结合数与围长  53-55
  4.4 本章小结  55-56
论文中猜想之间的相互关系  56-57
结束语  57-59
参考文献  59-63
致谢  63-64

有向图中若干问题的研究

内容摘要

全文目录

相似论文