论文部分内容阅读
在图论中，有关哈圈和哈路的问题一直是图论学者研究的重点之一.随着Dirac和Ore将哈圈与度约束条件联系起来后，有关哈密尔顿性的度约束条件成为了学者们研究的热点.二部有向图是图论中的一类重要的图，有关二部有向图的哈密尔顿性也是图论学者研究的热点之一.本文研究了二部有向图在度约束条件下最长圈，哈圈以及哈路的存在性. 本文共分为四章. 第一章是绪论，介绍了研究背景和基本概念. 第二章研究了二部有向图在半度和约束条件下最长圈的存在性，并得到以下结论. 设D是具有二分类(X，Y）的二部有向图，其中|X|=a(a≥2)且|Y|=a+k（k=1或2）.若对D中任意的两个属于不同部集的顶点u和v,uv(∈)A(D)，满足d+(u)+d-(v)≥a+2+([)k/2」，则D中包含长为2a的圈. 第三章将强连通平衡二部有向图的局部结构和度约束条件结合在一起，研究了强连通平衡二部有向图在度约束条件下哈圈的存在性，得到以下结论. 设D是2a个顶点的强连通平衡二部有向图，其中a≥2.若对D中每个控制对{x,y}，有d(x)≥2a-2且d（y）≥a+2或者d(y)≥2a-2且d(x)≥a+2，则D中包含一个哈圈或同构于有向图H1（见文第13页）. 第四章研究了平衡二部有向图在不相邻顶点的度和约束条件下哈路的存在性，并证明出以下结论 设D是2a个顶点的平衡二部有向图，其中a≥2.若对D任意不相邻的顶点u和v，满足d(u)+d(v)≥3a-1，则D有哈路. 这个定理的下界是最优的.