【摘 要】
：
关于图论的研究已经有二百多年的历史,早在1736年Euler就用图论方法解决了著名的哥尼斯堡七桥问题.而在十九世纪中叶,四色猜想被提出后,图的染色问题成为图论中一个非常重要的研究课题.一百多年以来,四色猜想一直引领着图论的发展,直到1976年,Appel和Haken两人借助计算机证明了该猜想,至此四色猜想变成四色定理.随着对四色定理的深入研究,图的染色理论进入了迅猛发展期.图的染色理论在计算机理论
【基金项目】
：
国家自然科学基金,编号: 11671232；
论文部分内容阅读
关于图论的研究已经有二百多年的历史,早在1736年Euler就用图论方法解决了著名的哥尼斯堡七桥问题.而在十九世纪中叶,四色猜想被提出后,图的染色问题成为图论中一个非常重要的研究课题.一百多年以来,四色猜想一直引领着图论的发展,直到1976年,Appel和Haken两人借助计算机证明了该猜想,至此四色猜想变成四色定理.随着对四色定理的深入研究,图的染色理论进入了迅猛发展期.图的染色理论在计算机理论,网络设计,组合最优化等方面应用广泛,例如网络中的数据传输,Hessian矩阵的计算.图的染色问题有很多,诸如点染色、边染色、面染色和全染色问题等,其中最基本的染色问题之一是图的点染色.图的正常点染色是把图的顶点集分解为一些互不相交的独立集的并的方法.近年来,许多学者在正常点染色的基础上添加约束条件,由此产生一些特殊的点染色并进行研究.本文旨在讨论图的一类特殊的点染色问题-面唯一极大染色.给定平面图G的一个正常点染色,若对G的每个面f,与f关联的顶点所染颜色的极大颜色在与f关联的顶点中仅出现一次,则称此染色是G的面唯一极大染色.平面图G存在面唯一极大染色所需最小颜色数,称为G的面唯一极大色数,记为χfum（G）.用|f（G）|表示平面图G的内部面个数.2019年,Lidicky等人提出一个关于平面图的面唯一极大染色的猜想:若G是平面图且G的导出子图G[X]无圈,其中X={v∈V（G）:dG（v）≥4},则χfum（G）≤4.论文通过运用构造法、反证法及提前染色等方法研究了阿基米德图,哈林图以及一类具有大度点限制的平面图的面唯一极大色数.得到如下结论:（1）.若图G是阿基米德图,则χfum（G）=4;（2）.若图G是哈林图,则3≤χfum（G）≤4且界为紧的;（3）.若图G是3-正则哈林图且|f（G）|三0,1（mod 3）,则χfum（G）=4;（4）.若图G是平面图,其任一圈至少包含2个3--点,则χfum（G）≤4.结论（1）确定了阿基米德图的面唯一极大色数;结论（2）确定了哈林图的面唯一极大色数的上界与下界,并且这两个界是紧的;结论（3）证明了满足|f（G）|三0,1（mod 3）的3-正则哈林图G的面唯一极大色数是4;结论（4）证明了上述猜想对于任一圈至少包含2个3--点的平面图成立.
其他文献
在互联网的推动下,经济发展进入新的阶段,为现代化工厂的发展创造了新机遇。自动导引车（AGV）采用锂电池供电且无需人工操控,其节能、高效、低成本的特点保证了现代化工厂运输环节的迅捷、稳定。在运输生产过程中,中央调度系统对AGV的监管和调度能够保证其高效、稳定地运行。本文在现有AGV的基础上,开发出一套适用于保证高铁轨道板生产的AGV调度系统。本文主要内容如下:首先,对项目需求进行分析,设计了AGV运
微流控技术因其高效的传质传热效率、高度集成化以及低样品消耗的优势在近些年取得了迅猛的发展,在细胞生物学、生命科学、纳米材料合成及生化分析检测等多个领域均有广泛的应用和极佳的应用前景。基于微流控技术的生物化学检测及纳米材料合成其本质为生化反应,而微流体的温度控制则是这些反应顺利进行的关键因素,因此微流体的温度控制对微流控技术在生化反应领域中的应用十分重要。本文概述了微流体温度控制及传热特性的国内外研
电池极片轧机是提高电池极片致密度的重要设备,为了进一步提高电池极片的轧制精度和厚度一致性。论文基于对目前轧机结构的分析,提出一套以牌坊结构优化为核心的牌坊式短应力极片轧机。论文重点分析了短应力线牌坊结构的优化过程,并通过动力学分析与仿真研究的形式对核心牌坊结构和极片轧机整体系统展开研究分析,为提高电池极片的生产质量以及极片轧机结构设计与分析提供了一定的指导意义。论文主要从以下几个方面展开研究。1.
在交通事故发生时,对行人和车内乘员造成重度损伤的比例维持较高水平。在众多的交通事故中,下肢损伤是正面碰撞中最常见的损伤。对于行人而言:我国现阶段所使用的下肢撞击器不能反映交通事故中下肢损伤的具体情况。本研究基于不同年龄的中国人体下肢有限元模型与五种常见的典型汽车前围有限元模型,通过数值分析研究年龄差异和汽车前围形状对下肢损伤的影响趋势。研究结果显示满足较低的前围离地间隙和较大的接触高度对行人下肢比
路灯杆清洗装置是一款自动捕捉路灯杆、对路灯杆实施智能化清洗的高空作业机械。而捕捉路灯杆的过程需要路灯杆清洗装置在空间中的运动轨迹保持较高的精度。该装置的臂架系统为轻质多连杆机构,是典型的多自由度柔性系统,运动时存在柔性形变,导致路灯杆清洗装置在运动时产生轨迹误差,影响清洗质量。对于高空作业机械而言,风载荷作用因素是不可或缺的研究内容。本文具体研究内容如下:首先,参考高空作业车的结构设计、依据相关规
制造业是经济发展必不可少的一部分。而机械加工是制造业的基础。伴随着中国现代化的进程,国家对制造业的要求越来越高。因此精密加工与特种加工在机械加工中所占的比例也来越重。304不锈钢因为具有较高的强度和硬度,能够在高温高压的情况下保证精度和工件成型性,能够适应各种酸性碱性等腐蚀环境,使用环境场合越来越多。但不锈钢的塑性大、韧性高、导热性差,车削加工时塑性变形严重。易产生晶体移位和晶格畸变出现加工硬化现
路径规划技术是智能驾驶研究领域的一个重要组成部分,是智能车完成行驶任务的前提。根据研究课题的需要,为实现在复杂环境下能够规划出满足智能车运动学约束并安全避障的路径,研究了一种改进快速随机拓展树（RRT）算法同时融合了四阶贝塞尔曲线优化的路径规划方法。在分析了基本算法原理和优缺点的基础上明确了可以进行算法改进的方向,通过引入角度约束策略、目标偏向策略、邻域重构策略等三个方面改进了基本算法,利用改进算
随着我国经济的高速发展和工业制造智能化水平的不断提高,我国的机器人市场也进入到了高速生长期,年销量连续六年居世界首位。然而机器人的大量应用显示出其普遍具有负载自重比低的问题。机器人在大部分工作时间中承受的载荷要远小于其额定载荷,这就使机器人容易出现“大马拉小车”的能耗现象,不仅限制了机器人的工作能力,也造成了能源上的浪费。我国的可持续发展战略中明确提出要实现节能减排,发展绿色经济,因此,提高机器人
随着智能机器人的不断发展与更新,协作型机器人取得了快速发展并成为了当今研究的热点。机器人可以帮助人类高效完成简单、重复性的工作,在军事、航天、康复医疗、工业等领域具有广泛应用,然而,在不确定性环境下或意外事故发生时,机器人决策能力下降,并不能完全代替人类完成任务,赋予机器人一定的感知能力以提升人机协作高效性、柔顺性是当今研究的重要问题。但是,在接触式人机协作中,受当前柔性阵列皮肤传感器研究不成熟、
人工智能的思想一经提出,各行各业都随之发生着变化,在制造业中智能工厂、智能制造等一系列衍生词语相继被提出,尤其是智能制造的理念已被重点关注和研究开发。智能制造能够部分替代人类在制造过程中的脑力劳动,使生产智能化、高效化、个性化,是未来制造业的发展趋势。因此企业想要在竞争的独占鳌头,取得优势,急需适应多品种、小批量的生产模式,提高企业对于变幻莫测的市场的及时响应能力,以及对生产时发生的突发事件的及时