图上关于点不交子图的若干结果

发布时间：2017-10-14 13:03

  本文关键词：图上关于点不交子图的若干结果

  更多相关文章： 不交的θ图 完全独立生成树 Ore

【摘要】：图论是一门近些年飞速发展的数学学科,它是组合数学的一个重要分支.1736年欧拉发表了图论的首篇文章解决了著名的哥尼斯堡七桥问题.从19世纪中叶开始,图论进入第二个发展阶段,这一时期,图论问题大量出现,如地图染色的四色问题、由“周游世界”游戏发展起来的哈密尔顿问题等.进入20世纪,随着计算机科学的不断发展,图论在各个领域的广泛应用也越来越受到数学界和其他科学界的重视.本文仅考虑简单、无向有限图,这些图不包含重边以及环.设G是一个图,x和y是G中的两个相异的顶点,θ图定义为三条内不交的路的集合,这些路有相同的的起点和终点且起点和终点这两个顶点是互异的.树指的是连通且不含圈的无向图,生成树是指包含了图G的所有顶点的图,且该图是树.设T1和T2是G的两个生成树,如果对G的任意两个顶点x和y,T1和T2中的x-y路是内不交的,则称T1和T2是G的两个完全独立的生成树.G的哈密尔顿圈是指包含了G的所有顶点的圈.本文主要考虑了以下几个问题：两个完全独立生成树存在的度和条件,三个内不交的θ图的极值函数.全文共有四章.第一章介绍了图的基本概念及所研究问题的历史背景和发展情况.第二章主要研究了三个内不交的θ图的极值函数.主要结论如下：任意顶点数n≥12,边数至少为max{「3n+79/2」,「11n-33/2」}的图包含三个内不交的θΟ图.第三章主要研究了两个完全独立生成树的度和条件.主要结论如下：顶点数n≥7的图包含两个完全独立的生成树,如果这个图中的任意两个不相邻的顶点的度和至少为n.最后,本文的每章末尾,均提出了一些问题,以待进一步讨论和研究.
【关键词】：不交的θ图 完全独立生成树 Ore's条件 极值函数
【学位授予单位】：宁夏大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O157.5
【目录】：

• 摘要4-5
• ABSTRACT (英文摘要)5-7
• 主要符号对照表7-8
• 第一章 引言8-14
• 1.1 基本概念和术语8-9
• 1.2 问题的研究背景9-10
• 1.3 已有结论及本文的结果10-14
• 第二章 存在三个点不交的θ图的极值函数14-24
• 2.1 基本概念及术语14
• 2.2 主要引理及其证明14-17
• 2.3 主要定理1.3.9的证明17-23
• 2.4 可进一步讨论的问题23-24
• 第三章 两个完全独立生成树存在的度和条件24-35
• 3.1 预备知识24
• 3.2 主要引理24-25
• 3.3 主要定理1.3.14的证明25-34
• 3.4 讨论34-35
• 参考文献35-37
• 致谢37-38
• 个人简介38

【参考文献】

中国博士学位论文全文数据库 前1条

1 邹青松;图包含指定长度的圈和泛弧问题的研究[D];山东大学;2011年

，

本文编号：1031182