超欧拉图及相关问题性质研究

论文摘要

欧拉图是可以从图中的任意一点出发,经过图中的每条边正好一次,最后返回起点的图。欧拉图问题是图论的边行遍性问题中的一个基本问题。超欧拉图是存在欧拉生成子图的图,也可以定义为含生成闭迹的图。超欧拉图问题也是图论研究中一个非常重要的问题,该问题研究的主要目的在于实际生产的安排过程中,通过判定某个给定图是否为欧拉图,从而决定后续基于欧拉图的优化算法是否可行。本文主要工作包括:1.回顾了可折叠图和超欧拉图的历史背景、基本概念、发展现状,介绍了超欧拉图的主要研究方向,相关问题和本课题的研究意义。2.从图解序列,收缩操作,简化图,可折叠图和欧拉生成子图的定义、相关性质以及图与度序列的关系入手,借鉴判定某个图的度序列是否可图解的经典方法,对可折叠图解序列和超欧拉图解序列逐步深入讨论,最后给出判定某个给定的图解序列是否为可折叠图解序列或超欧拉图解序列的充分条件,并给出了相应证明。3.对于r≥0,r -超欧拉图是指在图G中对于任意的X ? E （ G）满足X≤r,G都有欧拉生成子图H ,使得X ? E （ H）。类似的,可以定义r -欧拉连通图,强r -欧拉连通图和r -边欧拉连通图。本文分析了使k -边连通图必定是r -超欧拉图的k的最小取值的研究思路,总结其方法并加以推广,研究了使k -边连通图必定为上述3种欧拉连通图的k的最小取值,并根据r的取值范围不同进行划分,分别确定了k值。4. Catlin提出的用收缩法判定超欧拉图在理论证明中效果很好,但在判定具体图时却不易操作。本文在提出一个对树中的任意偶顶点子集两两配对使得配成对的两顶点间有唯一路径,且所有路径边不交的算法的基础上,结合某类图具有的特殊结构,给出并证明了一个较为实用的判定超欧拉图的充要条件,并由此判定条件证明了当m≥4, n≥4时,m×n型网格图是超欧拉图。

论文目录

• 摘要
• ABSTRACT
• 1 绪论
• 1.1 问题的提出，研究意义及现状
• 1.1.1 问题提出
• 1.1.2 研究意义
• 1.1.3 国内外研究现状
• 1.2 本文的研究目的和研究内容
• 1.2.1 本文的研究目的
• 1.2.2 本文的研究内容
• 1.3 图论相关基础知识
• 1.3.1 欧拉图，超欧拉图和可折叠图
• 1.3.2 收缩图和简化图
• 1.3.3 其他相关知识
• 2 可折叠图解序列和超欧拉图解序列
• 2.1 引言
• 2.2 Catlin 提出的相关定理
• 2.3 可折叠图解序列
• 2.3.1 提出引理
• 2.3.2 证明定理
• 2.4 超欧拉图解序列
• 2.4.1 提出引理
• 2.4.2 证明定理
• 3 含指定边生成迹的欧拉连通图
• 3.1 引言
• 3.2 三种带参数r 的欧拉连通图定义
• 3.3 Catlin 提出的相关定理
• 3.4 r -欧拉连通图和强r -欧拉连通图的讨论
• 3.4.1 提出引理
• 3.4.2 举例说明下界
• 3.4.3 r -欧拉连通图和强r -欧拉连通图具体取值确定
• 3.5 r -边欧拉连通图的讨论
• 3.5.1 提出引理
• 3.5.2 r -边欧拉连通图的具体取值确定
• 4 实用超欧拉图判定
• 4.1 引言
• 4.2 新定理提出
• 4.2.1 引入问题实例
• 4.2.2 提出配对算法
• 4.2.3 提出新定理
• 4.3 新定理应用
• 5 总结与展望
• 5.1 本文的主要工作
• 5.2 进一步的研究设想
• 致谢
• 参考文献
• 附录
• A. 作者在攻读学位期间发表的论文目录
• B. 作者在攻读学位期间参与的科研项目