局部半完全有向图中的哈密尔顿分解和泛弧的研究

来源 :山西大学 | 被引量 : 0次 | 上传用户:element_li
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
在图论中,有关哈密尔顿分解和泛弧的问题一直是图论学者们研究的重点.随着Bang-Jensen在1990年提出局部半完全有向图的概念,局部半完全有向图中的哈密尔顿分解和泛弧的问题也开始受到研究工作者的广泛关注.  没有2-圈的局部半完全有向图是局部竞赛图.2012年,Bang-Jensen和Huang(J Combin Theory Ser.B.2012,102:701-714)证明了2-弧强的局部半完全有向图包含两个弧不相交的强连通生成子图当且仅当图D不是偶圈的二次幂,并提出了任意3-强的局部竞赛图包含两个弧不相交的哈密尔顿国的猜想.本文主要研究局部半完全有向图中弧不相交的哈密尔顿路和哈密尔顿圈.2016年,Bai等人(Discrete Mathematics.2016,339:2063-2065)研究了竞赛图中的泛弧问题,本文研究了局部半完全有向图的子类——圆有向图中的泛弧问题,并将竞赛图中的结论推广到了圆有向图中.  针对这些问题,本文共分为五章.  第一章,介绍了有向图的基本概念,以及问题的研究背景.  圆有向图作为局部半完全有向图的一个重要的子类,一直是人们研究局部半完全有向图中各种问题的起点.第二章,讨论了圆有向图中的弧不相交的哈密尔顿路和哈密尔顿圈,证明了:  (a)2-强的圆有向图中包含弧不相交的哈密尔顿路和哈密尔顿圈当且仅当它不是偶圈的二次幂;  (b)任意3-强的圆有向图中必包含两个弧不相交的哈密尔顿圈;  (c)任意4-强的圆有向图中必包含一个哈密尔顿圈和两个哈密尔顿路,使得它们两两弧不相交;  (d)将这些结论推广到正圆有向图中.  第三章,研究了圆可分解的局部半完全有向图中弧不相交的哈密尔顿路和圈,证明了任意3-强的圆可分解的局部半完全有向图中包含两个弧不相交的哈密尔顿圈,从而说明了Bang-Jensen和Huang的猜想对圆可分解的局部竞赛图成立.并刻画了包含弧不相交的哈密尔顿路和哈密尔顿国的2-强的圆可分解的局部竞赛图.  第四章,研究了非圆可分解的局部竞赛图中弧不相交的哈密尔顿路和圈,证明了任意2-强的非圆可分解的局部竞赛图中包含两个起点和终点分别不同的弧不相交的哈密尔顿路.并结合圆可分解的局部竞赛图的结论,将Thomassen的关于竞赛图的结论(任意2-强的竞赛图包含两条弧不相交且起点和终点互不相同的哈密尔顿路)推广到局部竞赛图上.  第五章,设uv是有向图D中的一条弧,如果D中任意顶点和弧uv都包含在某个公共圈中,则称弧uv是D的一条泛弧.本章证明了圆有向图R的每条弧都是泛弧当且仅当R是一个圈或者R是2-强连通的且R不属于一类特殊的圆有向图,并给出了判断是否一个圆有向图的每条弧都是泛弧的多项式时间算法.
其他文献
偏微分方程是现代数学的一个重要分支,在物理学、微分几何、计算数学、图像处理等大量学科中都有许多重要的应用.非线性发展方程是其中一类重要的偏微分方程,其解的衰减和爆破
本文对超Rabinovich混沌系统的特性进行了深入的研究,同时探讨了该混沌系统的同步问题,尤其以线性耦合反馈同步和参数调节自适应同步为研究的核心内容.  首先简要地介绍有
最小二乘估计是线性回归问题中应用最为广泛一种的估计。然而,当变量间存在复共线性问题时,最小二乘估计就会有所限制。为此,K.J.Liu提出了一种新的有偏估计-LIU估计。在设计阵
众所周知,多处理机网络的基础拓扑通常以图为数学模型,其中图中的顶点表示处理机,图中的边表示处理机间的直接通讯联系.很多网络间的通讯联系都具有方向,因此,以有向图为网络的数
μ基是新近出现在几何造型领域中研究曲线和曲面性质与计算的一种代数工具,它提供了一种联系曲线和曲面的参数表示与隐式表示之间的桥梁。基于μ基的隐式化方法,表示紧凑且效率
可压微极性流体是指流体中散布着粒子的悬浮液,比如血液、有添加剂的润滑油和聚合物溶液等。与经典的可压Navier-Stokes方程主要差别是放弃Euler-Cauchy应力原理的假设,考虑流