满足某些特殊条件的平面图边染色问题研究

来源 :山东大学 | 被引量 : 0次 | 上传用户:qfcyzf2573
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
本文讨论的图均为简单无向有限的平面图。对于一个图G=G(V(G),E(G)),V(G),E(G)分别表示其顶点集合和边的集合。对于顶点v∈V(G),我们用d(v)表示其度数,△(G)和δ(G)分别表示G中顶点的最大度和最小度,简记为△和δ。在图论符号中我们常略去字母G分别用V,E,v和ε代替V(G),E(G),v(G),ε(G)。   图的染色问题,是图论的主要研究问题之一。图的染色一般分为边染色、点染色、全染色以及其它特定染色。本文讨论了平面图的边染色问题,证明了两个主要结论。   图G的一个k-边正常染色是指k种颜色在E(G)上的一种分配,使得相邻的两条边染以不同的颜色。若图G有一个k-边正常染色,则称G是k-边可染色的。图G的边色数是指使G为k-边可染色的最小值k,记为x(G)。   边染色问题有下面的著名定理:   Vizing定理(1964)设G是无环的非空简单图,则△(G)≤x(G)≤△(G)+1。   对于有重边的图G,设μ(G)表示G中边的最大重数,Vizing定理实际上证明了一个更一般的结论:△(G)≤x(G)≤△(G)+μ(G)。   Vizing定理提出了图的一个分类问题:若图G满足x(G)=△(G),则称G为第一类图;若图G满足:x(G)=△(G)+1,则称G为第二类图。确定一个图属于第一类还是第二类是很困难,目前仅对少量图判明了它们所属的类。路、树、二部图、偶数阶完全图,轮图都是第一类图;奇圈、奇数阶完全图都是第二类图。一般情况下一个图属于第几类图,尚没有好的充分必要的判别条件。已经知道存在最大度是2、3、4、5的第二类平面图,且Vizing(1965)已证明:不存在最大度≥8的第二类平面图。Sanders and Zhao[1]证明了最大度为7的平面图是边染色第一类图。目前尚不知道是否存在最大度为6的第二类平面图。   在本文中我们主要研究平面图的边染色问题,其中短圈是指长度小于等于5的圈。我们通过对顶点和面上的值进行重新分配,运用欧拉公式证明了:若G是△(G)=6的平面图,且G中不含相邻的短圈,则x(G)=6;若G是△(G)=5的平面图,且G中不含相交的3-圈与短圈,则x(G)=5,即G是第一类图。
其他文献
本文主要从数学上研究因种群中个体在免疫力、易感程度、自然和因病死亡率、行为模式等方面存在差异,而对某种疾病表现出的相异特质对传染病动力学性态的影响.文中引入具有常
延迟问题也称时滞问题,它在各个领域都有广泛应用,是目前各学科普遍面临的重要研究对象,分数阶延迟微分方程是其中一个新型的研究方向。与经典微分方程相比,分数阶微分方程能够更
本文主要考虑非线性的Choquard方程解的存在性与多重性的问题,第一类研究的是带有权函数和Hardy-Littlewood-Sobolev临界指数的方程,主要利用变分法和Ljusternik-Schnirelmann
论文来源于晋西铁路车辆有限公司双轴高精度同步调速控制磨合机控制系统的设计项目,系统中的异步电机采用交流电机矢量控制方法,并针对交流电机的数学模型是一个高阶、非线性、强耦合的多变量系统,以及矢量控制的不完全解耦性等缺点,利用了模糊控制技术来改善上述缺点。论文运用了一种将矢量控制与模糊控制相结合的交流电机协调控制方法,并将此方法成功的应用于试验系统设计中。系统构建了一个货车转向架的实际运行环境,通过两
时序分析方法作为现代数据处理的方法之一,广泛应用于各类实际工程领域中。它要求建模所用的观测数据样本不少于50个,而且历史数据越多越准确,建模预测结果也越可靠。但在实际应用中,由于各种原因,观测数据样本不允许很大,有时甚至只有十几个,在这种情况下,就需要研究小样本的时序建模方法。近年来随着我国经济的发展,人均国民生产总值显著增长,但由于影响人均国民生产总值的因素众多,且变化难以把握,这就给预测带来了