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

匹配可扩图的若干新结论

作　者: 张文勇
导　师: 赵飚
学　校: 新疆大学
专　业: 应用数学
关键词: 完美匹配 k-可扩图导出匹配可扩图偶匹配可扩图
分类号: O157.5
类　型: 硕士论文
年　份: 2010年
下　载: 21次
引　用: 0次
阅　读: 论文下载

内容摘要

匹配理论是图论的核心内容之一.由于得到应用领域的支持,并与其他理论课题发生密切联系,受到众多学者的关注,产生出许多含义丰富而深刻的理论成果.例如:刻画偶图具有完美匹配的Hall定理;刻画一般图具有完美匹配的Tutte定理;不具有完美匹配图的Gallai (?) Edmonds结构定理等;都是影响深远的传世之作.同时关于匹配的一系列研究专题不断涌现出来,匹配可扩性( k-可扩性,导出匹配可扩性,偶匹配可扩性等)就是其中之一.匹配可扩图之间的关系密切,构成一个整体:k-可扩的(k = m(G)) (?)偶匹配可扩的(?)导出匹配可扩的(?) 1-可扩的(?)基本的,其中m(G)是图G的最大匹配的基数.本文所涉及的图均为无向、有限、简单图.本文主要研究了与图的导出匹配可扩性、偶匹配可扩性有关的一些问题,共分三章.第一章,我们介绍匹配理论的研究背景和一些基本概念,对各类匹配可扩性问题研究的历史与现状进行了一定程度的综述.最后介绍了本文的研究内容和主要结果.第二章,我们研究了导出匹配可扩图的一些基本性质、范型条件、度和-连通度条件.第三章,我们研究了偶匹配可扩图的范型条件、度和-连通度条件.

全文目录

摘要  3-4
Abstract  4-6
第一章引言  6-16
  1.1 匹配理论的研究背景  6-7
  1.2 基本概念  7-8
  1.3 匹配可扩性研究综述  8-14
    1.3.1 k-可扩图  8-10
    1.3.2 导出匹配可扩图  10-11
    1.3.3 偶匹配可扩图  11-12
    1.3.4 基本图  12-13
    1.3.5 k-因子临界图  13-14
  1.4 本文的研究内容及主要结果  14-16
第二章导出匹配可扩图的结构性质及度型条件  16-26
  2.1 基本结构性质  16-17
  2.2 范型条件  17-19
  2.3 度和-连通度条件  19-26
    2.3.1 预备知识  19-20
    2.3.2 度和-连通度条件  20-26
第三章偶匹配可扩图的结构性质及度型条件  26-31
  3.1 范型条件  26-28
  3.2 度和-连通度条件  28-31
    3.2.1 预备知识  28-29
    3.2.2 度和-连通度条件  29-31
参考文献  31-34
硕士在读期间完成论文清单  34-35
致谢  35

匹配可扩图的若干新结论

内容摘要

全文目录

相似论文