导读:本文包含了完备染色论文开题报告文献综述及选题提纲参考文献，主要关键词:完备染色,平面图,完备色数,Halin图
完备染色论文文献综述
孟宪勇,郭建华,苏本堂[1]（2015）在《3-正则Halin图的完备染色》一文中研究指出研究了3-正则(或立方)Halin图的完备染色,针对非轮图的3-正则Halin图,提出了一种具体的完备染色,简单确定了非轮图(Wn)的3-正则Halin图的完备色数是6,且使得3-正则Halin图的完备染色可用计算机实现。(本文来源于《山东大学学报(理学版)》期刊2015年12期）
贾西贝[2]（2015）在《图的若干不完备可区别染色算法研究》一文中研究指出本学位论文主要考虑图的不完备可区别染色问题。图染色是图论中一个非常重要的研究方向,在实际问题中有着很好的应用,排课表问题、任务分配问题、集成电路布线等都可以从图染色的角度来解决。可以说,图染色为一些实际问题的解决提供了一种新的思路和方法。由于实际问题的复杂性,单一的点染色或者边染色并不能完全满足问题的要求,研究者们便提出了各种各样的染色问题,如点(邻点)可区别染色、均匀染色、可约染色等,并得到了很多有价值的理论成果,而不完备可区别染色便是由于实际问题的需要,在正常可区别染色基础上的弱化。由于图的染色问题是一个NP-完全问题,目前解决图染色问题的算法主要依赖于智能算法,但只限于解决特殊图的点染色或者边染色,不能解决全染色和可区别染色问题,而现实中的很多问题所转化的图都具有一定的随机性,所以寻求针对任意一个图的高效的染色算法已成为图论研究者的一个重要的课题。对于不完备可区别染色,已发表的文献中虽然得到了一些理论成果,却没有可行的染色算法,而算法的实现对相关问题的研究具有较高的实际意义。所以,本文根据不完备可区别染色的染色要求,设计出了针对任意一个简单连通图的染色算法,通过大量的测试分析,算法具有较高的染色效率。本文的工作如下:(1)介绍了与本文有关的一些基本染色概念及猜想,同时给出本文有关内容的研究背景、国内外研究动态等。(2)介绍了粒子群算法、遗传算法的基本思想、流程,及其在图染色中的应用,并对这些算法在解决图染色问题的性能上进行了分析。(3)针对任意简单连通图设计了四种不完备邻点可区别全染色算法,包括一种基于正常点染色的邻点可区别E-全染色算法,和叁种基于正常边染色的算法,分别为邻点可区别V-全染色算法、邻点可区别I-全染色算法和邻点可区别VI-全染色算法。前者采用先顶点染色再边染色的方法,而后者采用先边染色再顶点染色的方法。其中,算法中设计的边染色方法,可以解决任意一个图的正常边染色问题,而且根据染色条件的变化还可以解决其它基于正常边染色的全染色或可区别染色问题。文中给出了算法的详细流程及测试,并对算法的正确性、收敛性和时间复杂度进行了分析,最后对算法做了总结。(本文来源于《兰州交通大学》期刊2015-04-01）
胡晓雪[3]（2014）在《平面图的边—面染色和完备染色》一文中研究指出平面图G的一个边-面(或完备)k-染色是指一个映射φ:E(G)∪F(G)→{1,2,…,κ}(V(G)∪E(G)∪F(G)→{1,2,…,κ}),满足对于任意不同的相邻或相关联的元素x,y∈E(G)∪F(G)(x,y∈V(G)∪E(G)∪F(G))都有φ(x)≠φ(y).G的边-面(或完备)色数是指G有一个边-面(或完备)k-染色的数k的最小值,用χef(G)(χvef(G))表示.若G有一个边-面染色π,使得对每个x∈E(G)∪F(G)都有π(x)∈L(x),那么就称G是边-面L-可染的.若对于任意列表｜L(x)｜≥k,G是边-面L-可染的,那么就称G是边-面k-列表可染的.G的边-面列表色数是指G是边-面k-列表可染的数k的最小值,用chef(G)表示.类似的定义完备列表染色,且G的完备列表色数用ckvef(G)表示.关于平面图的边-面染色问题,最早是由Jucovic(1969)和Fiamchik(1971)提出的.后来,Borodin证明了当△(G)≥10时,χef(G)≤△(G)+1,这个结论可以直接拓展到边-面列表染色.于是,Wang和Lih提出了一个问题：对于任意3≤△(G)≤9的平面图G,确定边-面列表色数chef(G)一个紧的上界.平面图的完备染色是Ringel(1965)提出的.Borodin在1993年证明了对于任意△(G)≥12的平面图G,χvef(G)≤△(G)+2.并且后来他提出了一个问题：对于△(G)≤11的平面图G,能否找到χvef(G)一个紧的上界?对于平面图的完备列表染色,Borodin证明了对于任意△(G)≥7的平面图G,chvef(G)≤△(G)+4.Dong证明了若G是△(G)≥6的平面图,则chvef(G)≤△(G)+5.本学位论文主要研究了平面图的边-面染色和完备染色问题,共分四章.第一章我们介绍了基本概念和相关领域的研究现状,并且呈现了本文的主要结果.在第二章中,我们研究了平面图的完备染色,证明了任意△(G)≥9的平面图G是完备(△(G)+2)-可染的.在第叁章中,我们研究了平面图的完备列表染色,证明了下面两个结果：(1)任意△(G)≤5的平面图G是完备(△(G)+5)-列表可染的.(2)任意△(G)≥10的平面图G是完备(△(G)+2)-列表可染的.在第四章我们研究了平面图的边-面列表染色,证明了任意△(G)≥9的平面图G是边-面(△(G)+1)-列表可染的.(本文来源于《浙江师范大学》期刊2014-05-01）
上官敏乐[4]（2014）在《Δ(G)=7且不含有4,5-圈的平面图的完备染色》一文中研究指出用χvef(G)分别表示图G的完备色数.本文证明:若△(G)=7的平面图G且不含有4-圈,5-圈,则χvef(G)≤△(G)+4.(本文来源于《金田》期刊2014年04期）
上官敏乐[5]（2012）在《△(G)=7且不含有4,5,6,7-圈的平面图的完备染色》一文中研究指出用Xvef(G)分别表示图G的完备色数,本文证明:若△(G)=7的平面图G且不含有4-圈,5-圈,则≤△(G)+4。(本文来源于《成功(教育)》期刊2012年18期）
上官敏乐[6]（2011）在《Δ(G)=9平面图的完备染色》一文中研究指出用χvef(G)分别表示图G的完备色数.本文证明:若Δ(G)=9的平面图G且不含有4-圈,5-圈,则χvef(G)≤Δ(G)+4.(本文来源于《浙江树人大学学报(自然科学版)》期刊2011年02期）
上官敏乐[7]（2009）在《Δ(G)=11平面图的完备染色》一文中研究指出用χvef(G)分别表示图G的完备色数.该文证明:若Δ(G)=11的平面图G且不含有叁角形,则χvef(G)≤Δ(G)+3.(本文来源于《浙江树人大学学报(自然科学版)》期刊2009年03期）
温宇鹏[8]（2007）在《若干图类的全染色、完备染色和选色问题研究》一文中研究指出染色问题是图论的重要问题之一。它起源于四色问题的研究。有很强的理论意义和实际意义。目前，随着图的染色问题在现实中被广泛应用，它逐渐成为众多学者研究的重要领域之一。是图论研究中一个很活跃的课题，各类染色问题被相继提出并加以发展、应用。 本文主要研究平面规则网格——方形网格(square mesh)、六角网格(hexagonal mesh)和蜂巢网格(honeycomb mesh)的全染色问题和完备染色问题以及不含4-圈、5圈及相邻3-圈且非3-可选的平面图的选色问题。 首先，根据平面规则网格的结构特性，构造性地给出了方形网格、六角网格和蜂巢网格的全染色方案和完备染色方案，并根据所给出的全染色方案，提出了解决这叁种平面规则网格全染色问题的全染色算法，这叁种算法可以在多项式时间内完成对这叁种平面规则网格的全染色，时间复杂度为O(n~2)：证明了这叁种平面规则网格的全色数为其最大顶点度数加1；方形网格、六角网格的完备色数为其最大顶点度数加3；蜂巢网格的完备色数为其最大顶点度数加4，染色方案是最优的。 其次，对于Montassier等人给出的不含4-圈、5圈及相邻3-圈且非3-可选的平面图给出了新的构造。2006年，Montassier等构造了一个包含506个顶点不含4-圈、5圈及相邻3-圈且非3-可选的平面图(Bordeaux 3-color conjecture and 3-choosability．Discrete Mathematics，306(6)(2006)：573-579)，推翻了Bordeaux 3-色猜想：所有不含5-圈和相交3-圈的平面图是3-可选的。本文构造了一个具有相同性质且包含更少顶点的平面图，这个平面图仅包含380个顶点，目前是含最少点的不含4-圈、5圈及相邻3-圈且非3-可选的平面图。(本文来源于《大连海事大学》期刊2007-02-01）
张苏梅,刘家壮[9]（1998）在《平面图的完备List染色》一文中研究指出设Ｇ是２－连通简单平面图，ｘｖｅｆｌ（Ｇ）为Ｇ的完备Ｌｉｓｔ选择数．本文证明了若Ｇ为最大度Δ（Ｇ）≥７的２－连通外平面图，则ｘｖｅｆｌ（Ｇ）＝Δ（Ｇ）＋１．(本文来源于《青岛大学学报(自然科学版)》期刊1998年01期）
吴建良[10]（1996）在《外平面图的完备染色》一文中研究指出设Ｖ（Ｇ）、Ｅ（Ｇ）和Ｆ（Ｇ）分别为平面图Ｇ的点集、边集和面集。Ｇ的完备色数Ｘｃ（Ｇ）是使得Ｖ（Ｇ）∪Ｅ（Ｇ）∪Ｆ（Ｇ）中相邻或相关联的元素间均染不同色的最少颜色数。本文证明了：对无割点的外平面图Ｇ，有Ｘｃ（Ｇ）≤ｍａｘ｛７，△（Ｇ）＋１｝，其中△（Ｇ）为Ｇ的最大度数。(本文来源于《山东矿业学院学报》期刊1996年02期）
完备染色论文开题报告
（1）论文研究背景及目的
此处内容要求：
首先简单简介论文所研究问题的基本概念和背景，再而简单明了地指出论文所要研究解决的具体问题，并提出你的论文准备的观点或解决方法。
写法范例：
本学位论文主要考虑图的不完备可区别染色问题。图染色是图论中一个非常重要的研究方向,在实际问题中有着很好的应用,排课表问题、任务分配问题、集成电路布线等都可以从图染色的角度来解决。可以说,图染色为一些实际问题的解决提供了一种新的思路和方法。由于实际问题的复杂性,单一的点染色或者边染色并不能完全满足问题的要求,研究者们便提出了各种各样的染色问题,如点(邻点)可区别染色、均匀染色、可约染色等,并得到了很多有价值的理论成果,而不完备可区别染色便是由于实际问题的需要,在正常可区别染色基础上的弱化。由于图的染色问题是一个NP-完全问题,目前解决图染色问题的算法主要依赖于智能算法,但只限于解决特殊图的点染色或者边染色,不能解决全染色和可区别染色问题,而现实中的很多问题所转化的图都具有一定的随机性,所以寻求针对任意一个图的高效的染色算法已成为图论研究者的一个重要的课题。对于不完备可区别染色,已发表的文献中虽然得到了一些理论成果,却没有可行的染色算法,而算法的实现对相关问题的研究具有较高的实际意义。所以,本文根据不完备可区别染色的染色要求,设计出了针对任意一个简单连通图的染色算法,通过大量的测试分析,算法具有较高的染色效率。本文的工作如下:(1)介绍了与本文有关的一些基本染色概念及猜想,同时给出本文有关内容的研究背景、国内外研究动态等。(2)介绍了粒子群算法、遗传算法的基本思想、流程,及其在图染色中的应用,并对这些算法在解决图染色问题的性能上进行了分析。(3)针对任意简单连通图设计了四种不完备邻点可区别全染色算法,包括一种基于正常点染色的邻点可区别E-全染色算法,和叁种基于正常边染色的算法,分别为邻点可区别V-全染色算法、邻点可区别I-全染色算法和邻点可区别VI-全染色算法。前者采用先顶点染色再边染色的方法,而后者采用先边染色再顶点染色的方法。其中,算法中设计的边染色方法,可以解决任意一个图的正常边染色问题,而且根据染色条件的变化还可以解决其它基于正常边染色的全染色或可区别染色问题。文中给出了算法的详细流程及测试,并对算法的正确性、收敛性和时间复杂度进行了分析,最后对算法做了总结。
（2）本文研究方法
调查法：该方法是有目的、有系统的搜集有关研究对象的具体信息。
观察法：用自己的感官和辅助工具直接观察研究对象从而得到有关信息。
实验法：通过主支变革、控制研究对象来发现与确认事物间的因果关系。
文献研究法：通过调查文献来获得资料，从而全面的、正确的了解掌握研究方法。
实证研究法：依据现有的科学理论和实践的需要提出设计。
定性分析法：对研究对象进行“质”的方面的研究，这个方法需要计算的数据较少。
定量分析法：通过具体的数字，使人们对研究对象的认识进一步精确化。
跨学科研究法：运用多学科的理论、方法和成果从整体上对某一课题进行研究。
功能分析法：这是社会科学用来分析社会现象的一种方法，从某一功能出发研究多个方面的影响。
模拟法：通过创设一个与原型相似的模型来间接研究原型某种特性的一种形容方法。
完备染色论文参考文献
[1].孟宪勇,郭建华,苏本堂.3-正则Halin图的完备染色[J].山东大学学报(理学版).2015
[2].贾西贝.图的若干不完备可区别染色算法研究[D].兰州交通大学.2015
[3].胡晓雪.平面图的边—面染色和完备染色[D].浙江师范大学.2014
[4].上官敏乐.Δ(G)=7且不含有4,5-圈的平面图的完备染色[J].金田.2014
[5].上官敏乐.△(G)=7且不含有4,5,6,7-圈的平面图的完备染色[J].成功(教育).2012
[6].上官敏乐.Δ(G)=9平面图的完备染色[J].浙江树人大学学报(自然科学版).2011
[7].上官敏乐.Δ(G)=11平面图的完备染色[J].浙江树人大学学报(自然科学版).2009
[8].温宇鹏.若干图类的全染色、完备染色和选色问题研究[D].大连海事大学.2007
[9].张苏梅,刘家壮.平面图的完备List染色[J].青岛大学学报(自然科学版).1998
[10].吴建良.外平面图的完备染色[J].山东矿业学院学报.1996