广义棱柱和补棱柱中的超欧拉图

发布时间：2020-04-29 00:46

【摘要】：超欧拉问题是图论研究中的一个非常经典的问题,许多实际问题以及理论上的知名问题都可以转化为超欧拉图来解决.一个图是超欧拉图,是指它包含一个生成欧拉子图.相比于欧拉图已经有了较为简单的特征刻画,超欧拉图的判定问题则是NP-完全的.在图论中,由一个图或者两个图出发去构造新的图,并研究该图的性质,是一个很有趣的研究领域.本文主要研究图G的广义棱柱α(G),补棱柱GG以及有向图D对H的α-广义棱柱中的(有向)超欧拉问题.全文共分为四章.第一章概述与超欧拉问题密切相关的Catlin的约化方法,与本论文相关的研究背景,以及文中常用的定义、符号和术语.第二章首先介绍李霄民等人在研究广义棱柱的超欧拉性质方面的研究结果,然后我们刻画了完全二部图、长度不超过6的圈,以及树的广义棱柱是超欧拉图的充要条件.Haynes等人引入了两个图的补直积作为笛卡尔积的推广.补棱柱是补直积的一个有趣特例.第三章研究完全二部图、路、圈的补棱柱是超欧拉图的充要条件.最后研究两条有向路的字典式积的有向可迹性.作为广义棱柱概念的推广,我们在第四章首先给出两个有向图D对H的α-广义棱柱αH(D)的概念,然后研究αH(D)的超欧拉性质.
【学位授予单位】：山西大学
【学位级别】：硕士
【学位授予年份】：2018
【分类号】：O157.5

【相似文献】

相关期刊论文 前10条

1 桂起权;;逻辑圆论(一种由欧拉图导出的三段论系统)[J];武汉大学学报(哲学社会科学版);1981年02期

2 安明强;熊黎明;;超欧拉图、可折叠图及匹配[J];应用数学学报;2016年06期

3 李霄民;;判定超欧拉图的一个新方法[J];西南大学学报(自然科学版);2007年04期

4 李登信,王斌,李宵民;关于判定超欧拉图的收缩法[J];重庆工商大学学报(自然科学版);2003年01期

5 路浩;;关于赋权欧拉图的均匀初级圈覆盖[J];西安交通大学学报;1988年06期

6 潘洪;刘枫;;推广循环序列的计算机解[J];上海建材学院学报;1989年01期

7 张建州;一类欧拉图的全着色[J];电子科技大学学报;1989年03期

8 李晓璞;刘娟;;关于l-路和图的超欧拉性[J];西华师范大学学报(自然科学版);2018年03期

9 李霄民;李登信;;超欧拉图判定方法的一个注记[J];湖北大学学报(自然科学版);2007年03期

10 PaulA．Catlin,李相文;最小次数至少为4的超欧拉图(英文)[J];数学进展;1999年01期

相关博士学位论文 前1条

1 李赤松;访问控制中授权一致性问题的研究[D];华中科技大学;2012年

相关硕士学位论文 前10条

1 王刘岩;广义棱柱和补棱柱中的超欧拉图[D];山西大学;2018年

2 余三平;边连通度与超欧拉图的研究[D];中北大学;2010年

3 熊鸣;3-边连通基本5-边连通图的超欧拉图[D];华中师范大学;2012年

4 司沛;超欧拉图及相关问题性质研究[D];重庆大学;2008年

5 陈慧敏;在C_k(l，，m)中的k-超欧拉图[D];华中师范大学;2015年

6 王斌;超欧拉图的判定及Catlin-猜想的研究[D];西南师范大学;2003年

7 李良辰;超欧拉图和带约束条件的频率分配的近似算法[D];华中师范大学;2009年

8 赵红艳;欧拉图与矩阵环的多项式恒等式[D];湖北大学;2013年

9 薄祥智;中间P_2-图的边连通性[D];新疆大学;2010年

10 关晓溪;从逻辑图到图示逻辑[D];华东师范大学;2009年

本文编号：2644048