【摘 要】
：
哈密尔顿问题是结构图论中一个经典的研究课题,该问题与著名的四色问题存在着紧密联系.哈密尔顿问题在运筹学、通讯网络、社交网络、计算机科学、编码理论以及复杂性理论中都有着广泛应用.故而受到众多学者的青睐.本文主要研究图论中与哈密尔顿性质相关的一些问题,包括连通偶因子问题,哈密尔顿问题,最长圈问题以及哈密尔顿连通问题.全文共分为七章,下面分章节具体叙述本文的主要工作.第一章给出本论文的一些符号和术语,叙
论文部分内容阅读
哈密尔顿问题是结构图论中一个经典的研究课题,该问题与著名的四色问题存在着紧密联系.哈密尔顿问题在运筹学、通讯网络、社交网络、计算机科学、编码理论以及复杂性理论中都有着广泛应用.故而受到众多学者的青睐.本文主要研究图论中与哈密尔顿性质相关的一些问题,包括连通偶因子问题,哈密尔顿问题,最长圈问题以及哈密尔顿连通问题.全文共分为七章,下面分章节具体叙述本文的主要工作.第一章给出本论文的一些符号和术语,叙述图的哈密尔顿性相关问题的发展和国内外与此类问题相关的研究现状,并简单介绍本论文的结构,研究内容和主要结果.第二章利用禁用子图的概念来研究图的连通偶因子的存在条件.证明了顶点数至少为3,连通且局部连通的禁用K1,s+2的图包含一个连通的偶的[2,2s]-因子.第三章主要利用导出圈的性质来判断图的哈密尔顿性.证明了 3连通的线图,若它不含长度超过8的导出圈,则该线图是哈密尔顿图,这一结果可以推广到重爪图上.同时证明了对于3连通的无爪图,若它的每个长度至少为4的导出圈中至多含有8条非奇异边,则该无爪图是哈密尔顿图;若它每个长度至少为4的导出圈中至多含有11条非奇异边,则要么它是哈密尔顿图,要么它的闭包是经过收缩可变为Petersen图的那些图的线图.任意2连通的无爪图,若它最长的导出圈的长度不小于n-2,那么该图是哈密尔顿图.上述这些结果都是最好可能的.第四章研究了最小度δ ≥ 3的n阶无爪图,若它含有长度超过4n-2δ-4/δ+2的导出圈,则它是哈密尔顿图.当δ ∈ {3,4}时,上述下界是最好可能的.当δ ≥ 5时,虽然我们不知道它是不是最好可能的,但是有例子表明:δ ≥ 5时,这一结果最好可能的界不会小于4n-4δ-4/δ+2.第五章证明了下面的结果:设G是顶点数为n连通度为κ（G）的图,且有κ（G）≥k≥ 2 与n≥2 + 1,则图G的每一个最长圈包括度数至少为d的所有顶点,这里d = max {[n/2],n-3k+2}.结合独立数的条件,获得了如下结论:设G是阶数为n,独立数为α的k连通图,则图G的每一个最长圈包括度数超过d0的所有顶点,这里d0=（α-k）n-kα+k2 +α2-2α/α.第六章介绍图G的加强闭包GM的定义及性质,并利用这一概念,证明了,如果图G满足一些附加条件时,G是哈密尔顿连通的当且仅当其闭包cl（G）是哈密尔顿连通的.具体结果为:任意一个2连通的无爪图G,其最小度δ（G）≥3,如果G有一个无漏斗的加强闭包GM,那么G是哈密尔顿连通的当且仅当cl（G）是哈密尔顿连通的.第七章总结本论文所做的主要工作,对今后的研究工作做一展望.
其他文献
变桨轴承是大型风力发电机组关键易损部件,静态性能和疲劳性能直接影响风电机组安全稳定运行。面对激烈的市场竞争和个性化产品研发需求,寻求可靠适用的变桨轴承设计分析技术尤为重要。对此,基于轴承分析理论和ISO标准,运用非线性有限元分析技术,建立了变桨连接系统模型,进行了静态力学分析和疲劳寿命研究,并提出了提高轴承疲劳性能的有效方法。主要研究内容如下:首先,建立了“叶根-轴承-螺栓-轮毂”连接系统有限元模
目前,天然气开采由于钻前、钻进、完井工艺过程涉及的环境风险因素较多且复杂,环境风险不确定,难以综合评估整个天然气开采过程的环境风险高低程度,成为当前天然气开采环境风险管理的难点。为了解决当前天然气开采环境风险难以量化问题,本文结合天然气开采工艺特点,从天然气开采全过程进行分析,构建了用于评价天然气开采全过程环境风险评估的指标体系,为天然气开采行业提供一些综合评估环境风险的思路和决策依据。该体系包括
现代社会的数据越来越庞大,对能够有效处理数据,进行数据压缩,减小存储空间的工具的需求变高。而张量的TT分解无疑是一个强大的数据压缩工具,它不仅在理论上被证明了该方法高效处理高维数组的可行性,还提供了确切可行的算法。但它的缺点也很明显,TT分解的计算量随着张量的阶数呈指数增长。本文主要是探究新的TT分解算法,希望能够提供新的思路,使其能在一定程度上减少一些计算代价。本文主要完成了两项工作:一是基于块
人体内生物小分子氨基酸含量失衡导致众多疾病的发生,故对其含量检测意义重大。生物传感器检测氨基酸作为一种新兴方法已成为研究热点,但酶-底物、抗体-抗原等传感器由于识别元件对测试条件要求较高而限制其应用。分子印迹聚合物（MIP）作为一种人造仿生材料不但具备特异性识别能力,而且其对于测试环境适应性更强,故常用于构建电化学生物传感器。基于此,本文构建了两种分子印迹电化学生物传感器用于检测生物样品（人血清和
本文在研究国内外已有的水稻直播机并结合农艺生产要求,分析水稻直播生产的影响因素,发现水稻水直播种植中水稻易倒伏,植株疏密不均匀。针对这一问题设计一种通过传感器测速并用电机自动调控穴距的控制系统,和通过风机控制水稻播深的吹种装置。并以此设计一种主动排种水稻水直播机,满足水稻的精量穴直播作业要求。通过理论分析,对关键部件进行设计和研发,并进行流体仿真分析,台架试验,田间试验验证其可行性,本文的主要研究
农产品物流是农产品流通体系建设的重要组成部分,其保证了农产品从产地到销地的流通质量与效率,推动了农村经济的发展并能够提高城镇居民的生活质量。为推动农产品流通体系的建设,各地纷纷加大了农产品物流基础设施的投入,农产品物流园区数量近年来逐渐增多。然而,这些园区在运营过程中却出现了用地供应短缺等问题,这些问题的出现正是因为在园区建设前缺乏科学的决策与规划。为规避这些问题,充分发挥农产品物流园区的效率,充
谐波齿轮传动是一种新型传动形式,相比于传统刚性齿轮传动,该传动形式具有体积小,质量轻,传动比大,传动精度高以及传动平稳等优点,在航空航天、医疗器械、机器人等高精密传动领域应用广泛。由于在谐波传动中存在单个零件的制造误差与零部件间的装配误差,其对系统的力学性能与啮合性能影响较复杂,因此,研究谐波传动的制造误差、装配误差对谐波传动啮合特性与柔轮应力的影响规律具有重要的意义。本文以无公切线双圆弧齿廓谐波
土石堤坝是我国水利工程建设的重要组成部分，其隐患问题严重威胁着工程安全，随着地球物理探测技术呈现多样性发展，综合物探技术的研究对堤坝隐患的及时发现和治理有着极为重要的意义，通过对目前常用于土石堤坝隐患探测的地球物理探测技术原理和应用特性进行梳理分析，总结了常用物探技术的局限性和适用条件；概括了综合物探技术的体系原则，阐述了基于GIS的综合物探数据分析系统；指出了目前综合物探技术发展中存在的问题和局
随着经济社会的进步,微机电系统的发展方兴未艾,对能量供应系统的也提出了更高的要求。微尺度燃烧器使用燃料作为储能介质,能量密度大,相比于锂离子电池要高出23个数量级,非常具有发展潜力。但目前微尺度燃烧尚未成熟,总的来看,微尺度燃烧主要面临的问题有:1、由于大面容比造成的热量损失;2、时间尺度的约束;3、过于狭小的通道造成的火焰不稳定。本文采用实验手段、化学反应动力学分析以及计算流体力学方法,对微尺度
卫星通信具有覆盖率高、传播距离远、组网灵活以及不受地理条件限制等优势,在航天测控、移动通信、数字广播电视等领域获得了广泛的应用。由于卫星通信信道的开放性,处于波束覆盖范围内的任意接收机均可对卫星信号进行监听,如何保障卫星通信的安全性是一个十分重要的问题。物理层安全技术利用信号设计、编码、调制等方法在物理层实现保密通信,能够兼顾无线通信的可靠性以及安全性;然而,由于信号维度的限制,传统单频信号在利用