一、两类图的全染色问题（论文文献综述）
王超[1]（2021）在《符号图的边染色和全染色问题研究》文中指出令G=（V,E）是一个无环的图,其中V表示点集,E表示边集.符号图Γ=（G,σ）是指在图G的基础上给其边集加一个符号映射σ:E（G）→{+1,-1},使得G的每一条边e都有一个符号σe,称G为符号图Γ=（G,σ）的底图.若σe=1,则e是正边;若σe=-1,则e是负边.一个incidence表示为点-边序对（v,e）,其中v∈V（Γ）,e ∈E（Γ）,v是e的一个端点.用I（r）表示符号图Γ中incidence的集合.若k=2q（若k=2q+1）,符号图r=（G,σ）的一个k-边染色是指存在一个映射f:I（r）→{±1,±2,…,±q}（相应地,f:I（r）→{0,±1,±2,…,±q}）,使得对任意的边e=xy∈ E（Γ）都有f（x,e）=-σef（y,e）.如果对任意相邻的两条边e1=xy和e2=xz使得f（z,e1）≠f（x,e2）,则称f是Γ=（G,σ）上的正常k-边染色.如果符号图r=（G,σ）有一个正常k-边染色,称r是k-边可染的.记符号图r的边色数为χ’（Γ）,定义为使得r是k-边可染的最小正整数k的值.该定义由Behr在2020年提出,可以看出当符号图Γ中的边均为负边时,该定义为图G的正常边染色.此外,Behr在简单符号图r=（G,σ）中证明了 Vizing定理,即△（r）≤χ’（r）≤△（r）+1.本文研究当符号图r=（G,σ）有重边时边色数的上界.本文中还将研究符号图Γ=（G,σ）的点-边全染色.图G的一个正常k-全染色是指一个映射f:V（G）∪E（G）→{1,2,…,k},使得任意两个相邻点,相邻边,相关联的点和边均染不同色.如果图G有一个正常k-全染色,称G是kk-全可染的.记G的全色数为χ"（G）,定义为使得G是k-全可染的最小正整数k的值.关于全色数的上界,Vizing和Bchzad分别独立地提出着名的全染色猜想:对任意的简单图G,χ"（G）≤ △（G）+2.全染色猜想引起广大学者的研究兴趣.本文将在符号图r=（G,σ）中研究点-边全染色,给出符号图中点-边全染色的定义,在某些符号图类中考虑全色数的上界.本文主要围绕符号图展开研究,先后考虑符号图的边染色,符号图的全染色.学位论文分为以下章节:第一章节,首先介绍论文中常用的基本定义符号以及相关问题的研究现状,最后陈述获得的主要结果.第二章节和第三章节,分别研究当符号图有重边时边色数的上界,某些符号图全色数的上界.具体来讲,我们运用数学归纳法,色延拓技巧,颜色变换等方法证明了如下结果:（1）若符号图r=（G,σ）是多重图,当r不含有μ（r）-三角形,χ’（r）≤△（r）+μ（r）.需指出:该结果考虑的是非0染色.（2）若r=（G,σ）是最大度为3的符号图,则χ"（r）≤5.（3）若符号图是树Tn,则χ"（Tn）=Δ（Tn）+1.（4）若符号图是完全图Kn,则
康玉梅[2]（2021）在《随机图的点和可约染色算法研究》文中研究表明图论作为数学和信息科学的一门交叉学科,它以图为研究对象,将现实问题抽象成图,广泛的应用在各个领域,如矩阵运算、任务调度、网络通信、物品储藏、频率分配等。图染色作为图论研究领域的重要方向之一,同样是将生活中的实际问题抽象成图论模型,然后按照一定的规则进行分类,利用图染色的方法解决。目前,大量的学者们已对图染色问题作了许多的探讨和研究,寻找到了求解各类染色问题的具体方法,主要有基于搜索解空间的染色算法和基于目标函数的染色算法。基于搜索解空间的染色算法一般解决简单的点染色、边染色、全染色;基于目标函数的染色算法解决约束条件较多的邻点和可区别染色、点可区别染色、强边染色、点可约染色等。这两类图染色算法只针对一些特殊图染色或者特殊图集(Wn、Kn、Kn,n、C3（n）、mCn、D（G）、Sn+Fn、Wn+Fn、Mn（Cp）)进行处理得到染色结果。但随着染色条件增加,传统的染色算法将解决不了新出现的染色情况,故需要寻求新的染色算法来解决。因此,本文针对随机图的点和可约边染色、点和可约全染色、邻点和可约边染色3个问题进行研究,提出了解决这三类问题地具体方案,并设计了相关的点和可约染色算法。本文的主要研究工作如下:（1）介绍图染色的相关概念、（邻）点可约边（全）染色、（邻）点和可约边（全）染色的研究现状,以及点和可约染色研究与传统图染色研究方法的区别。（2）设计并完成了基于逐步寻优的点和可约边染色算法。首先,该算法依据点和可约边染色定义和逐步寻优的思想来确定的。其次执行算法得到10个点以内12205208个所有非同构图、19个点以内522957个树图的非同构图、15个点以内的所有单圈图和双圈图的点和可约边染色矩阵和最大染色数,并统计结果进行分析得到若干图的点和可约边染色结论和猜测。除此之外,为了优化点和可约边染色算法,设计了另外两种点和可约边染色算法,分别为基于规则集的点和可约边染色算法和基于方程式的点和可约边染色算法。并通过对这三种点和可约边染色算法的测试和结果集的对比,得到基于逐步寻优的点和可约边染色算法在性能和复杂度上都优于其他两种点和可约边染色算法。（3）设计并实现了点和可约全染色算法和邻点和可约边染色算法。并利用这两种算法对图数据集进行处理,从而得到10个点以内12205208个随机图、12个点以内特殊图的两类点和可约染色情况。最后,通过结果集分析,给出了若干联图和特殊图的定理证明。
王继顺,左林,葛仁福[3]（2020）在《图M（Pn）及Pn2的邻点可区别Ⅰ-均匀全染色》文中认为讨论了路图Pn的Myceilski图M（Pn）和二幂图P22的邻点可区别I-均匀全染色问题,根据这些图的结构性质,在运用构造法的基础上,通过色的调整给出它们的邻点可区别I-均匀全染色方法,从而有效地确定了其邻点可区别I-均匀全色数.结果说明了AVDETC猜想对于这两类图是成立的.
李永艳[4]（2018）在《完全蛛网图及渔网图的邻点可区别V-全染色》文中研究说明借助完全蛛网图和完全渔网图的结构特点,研究了这两类图的邻点可区别V-全染色问题,运用构造法和色调整技术给出了两类图邻点可区别V-全染色,并得到了邻点可区别V-全色数.同时也验证了图的邻点可区别V-全染色猜想.
许仁誉[5]（2017）在《平面图的列表点（边、全）染色和列表线性荫度》文中研究表明图论最早源于着名的哥尼斯堡七桥问题,已有两百多年的发展史.图的染色理论起源于四色问题,是图论研究中最重要的课题之一.在自然科学、社会科学领域都有重要的应用.在本论文中,我们研究了图的全染色、列表染色、邻和可区别全染色和列表线性荫度的问题.若无特别明确指出,本文所考虑的都是简单的,无向的,有限的和非空的图.令G =（V,E）是一个图,对一个点v∈V（G）,用NG（v）表示v在图G中的邻点集,dG（v）= |NG（v）|是点v的度数.图G的最大度和最小度分别用Δ（G）和δ（G）表示.为方便起见,令Δ = Δ（G）和δ = δ（G）.图G的kk-全染色是指用k种颜色（1,2,…,k）对V（G）∪E（G）中的元素进行染色,使得相邻的两个元素或者相关联的两个元素染不同的颜色.图G的所有k-全染色中的最小正整数k称为G的全色数,记为χ"（G）.关于图的全染色猜想（Total Coloring Conjecture）:对任意图 G,Δ + 1 ≤ χ"（G）≤Δ+ 2.这个猜想对于△ ≤ 5的一般图都成立.随着研究的不断深入,研究者发现有很多图的全色数不只满足全染色猜想,还可以取到相应的下界,也就是说χ"（G）= Δ + 1.就平面图而言,对△ = 6的平面图全染色猜想还未证明成立.而对△ ≥ 9的平面图G,已经证明了 χ"（G）= Δ + 1.对4≤Δ≤8的平面图,也未找到不能（Δ+1）-全可染的例子.于是有了平面图猜想:任意最大度至少为4的平面图是（△ +1）-全可染的.本文在第二章证明了平面图的全染色的三个相关结果:（1）对于△ ≥ 8的平面图G,若任何两个弦6-圈不相邻或者任意6-圈至多只含一条弦,则χ"（G）= △ + 1;（2）对于△ ≥ 8的平面图G,若任何7-圈至多含两条弦,则χ"（G）= Δ + 1;（3）对于△ ≥ 7的平面图G,若任何两个弦5-圈不相交,则χ"（G）= △ + 1.一个映射L被称为图G的一个分配,如果对于每个点v ∈ V（G）,都有一个列表L（v）.如果G存在一种染色使得每个点从列表中得到颜色,并且每两个相邻的点颜色不同,我们称G是L-点可染的.称图G是kk-点可选的,如果|L（v）| ≥ kk且G是点可染的,这里v是G中的任意一个点.我们在第三章证明了平面图G中3-圈或4-圈不同时与5-圈相邻,G是4-可选的.如果对于图G的任意一条边e ∈E（G）,我们给其一个颜色集合L（e）,那么就称L为G的一个边列表.对于图G的任意一个满足条件|L（e）| ≥k的边列表L,其中e ∈E（G）为G的任意一条边,如果G都是L-边可染的,那么就称图G是k-边可选的.使图G是kk-边可选的最小正整数k称为图G的列表边色数,记作χ"（G）.类似地,我们可以给出图G的列表全色数χl"（G）的定义,即把上述边染色换为对图的顶点和边进行染色.在第三章我们证明了对于平面图G,若最大度Δ（G）>8,且4-圈与5-圈不相邻,则χl’（G）= Δ,χl"（G）+ 1;若最大度Δ（G）≥ 6,且4-圈与5-圈不相邻,则χl’（G）= Δ + 1,χl"（G）= Δ + 2.近年来,魔幻、反魔幻标号、非正则强度等与"和（sum）"有关的染色与标号问题引起了广泛关注,其中比较着名的有1-2-3猜想和1-2猜想.本文的第四章给出图的邻和可区别全染色的定义,并给出相关问题的一些猜想和主要研究进展.用f(v表示点v及所有与其关联的边的颜色的加和,如果对任意的边uv,有f（u）≠ f（v），则称这样的kk-全染色为图G的k-邻和可区别全染色.k的最小值称为图G的邻和可区别全色数,定义为χ∑"（G）.Pilsniak和Wozniak猜想对至少两个顶点的图G,χ∑" ≤ △（G）+ 3.目前这个猜想已经证明对于完全图,圈,二部图,立方图,系列平行图和△ ≥ 14的平面图都成立.我们证明了对于可嵌入到欧拉示性数非负曲面的图来说,χ∑"（G）≤ max{Δ（G）+ 2,16}.最后,本文还讨论了平面图的列表线性荫度.一个图G的线性荫度是指把图G中的边集剖分成线性森林的最小数目,记为la（G）.Akiyama等人猜想kα（G）≤[Δ（G）+1/2]对每个正则图G都成立.显然,对于每个图G都有la（G）≥[Δ（G）/2],对于每个正则图G都有la（G）≥[Δ（G）+1/2],因此,Akiyama等人的猜想等价于如下猜想,即线性荫度猜想:设G是一个简单图,则[Δ（G）/2]kα（G）「Δ（G）+1/2].如果对于图G的任意一条边e ∈ E（G）,我们给其一个颜色集合L（e）（?）N,那么就称L为G的一个边列表,其中N是一个正整数集合.如果G存在一个正常的边染色φ（e）使得对每条边e有φ（e）∈ L（e）且对任意的i ∈ Cφ有(V（G）,φ-1（i）,其中Gφ = {φ（e）|e ∈E（G）}.那么我们说G是线性L-可染的且φ是G的线性的L-染色.我们说G是线性k-可选的如果G是线性L-可染的且对于所有边e的每个列表分配L满足|L（e）|≥ k.一个图G的列表线性荫度lalist（G）定义为G是线性kk-列表可染的最小值k.显然la（G）≤lalist（G）.本文的第五章,我们证明了如果G是一个平面图且G中7-圈至多含两条弦,那么若Δ（G）≥ 6,则G是线性[Δ+1/2]-可选的,若Δ（G）>11,则G是线性[[Δ/2]-可选的.在本文的第六章,我们将对全文进行总结,并提出在图的染色问题中一些今后可继续研究的课题.
顾忠栋[6]（2017）在《若干图的邻点强可区别E-全染色》文中提出设G（V,E）是一个简单图,存在正整数k,如果映射f:E（G）∪V（G）→{1,2,…,k}满足:对（?）uv∈E（G）,f（u） ≠ f（v）,f（v） ≠ f（uv）,f（u） ≠ f（uv）.对（?）uv∈E（G）,C（u）≠C（v）,其中C（u）={f（u）} ∪ {f（v）} ∪ {f（uv）|uv ∈ E（G）]}.则称f是图G的k-邻点强可区别E-全染色,简记为k-E-AVSDTC.称χaste（G） =min{k|G所有k-邻点强可区别E-全染色}为图G的邻点强可区别E-全色数.本文利用色集分配法、反证法、组合分析法、构造函数法,探讨了若干直积图、若干联图和冠图、若干路、圈运算图的邻点强可区别E-全染色问题,并得到了相应图的邻点强可区别E-全色数,最后运用概率方法得到了图的邻点强可区别E-全色数的两个界.论文共分为五个部分:第一部分介绍了本文所涉及的相关概念和已经得到的一些结果.第二部分讨论了笛卡尔直积图、强矢积图、字典积、半强矢积图的邻点强可区别E-全染色,并给出了其相应的色数.第三部分讨论了几类联图和冠图的邻点强可区别E-全染色,并给出了其相应的色数.第四部分讨论了路、圈运算图的邻点强可区别E-全染色,并给出了其相应的色数.第五部分运用概率方法研究了图邻点强可区别E-全色数的两个上界.
胡腾云[7]（2016）在《随机图的D（β）染色算法研究》文中研究表明图论是离散数学的一个重要研究分支,现实生活中很多实际问题都可以抽象成图,并应用图论的知识解决。图染色问题是图论中一个重要的研究方向,在理论和工程上很多组合优化、加工调度、最大支配集等问题都可利用图染色的方法解决,因此,图染色受到了国内外的专家学者的广泛研究,并取得到了很多有价值的研究成果。图染色问题是一个NP完全问题,目前应用于解决此问题的算法主要有仿生算法和智能优化算法,如:遗传算法、模拟退火算法、神经网络,且这些算法仅限于解决图的正常点染色和边染色问题,对于染色条件复杂D（β）-染色问题,目前尚未发现相关的算法,本文旨在设计一种新的算法来解决此类问题。2006年,张忠辅教授等给出了图的D（β）-点可区别边染色和D（β）-点可区别全染色的定义和相关猜想。截止目前,对于D（β）-染色的研究,仅得到了针对特殊图如路、星、扇、轮、完全图等的一些研究结果,但针对一般图的解决方法目前还没有。本文针对随机图（即:简单无向连通图）的D（β）-点可区别边染色、D（β）-点可区别全染色给出了相应的解决算法,其主要研究工作包括以下几个方面。（1）设计并实现了随机图的生成算法和有限点所有同构图的生成算法,并分别进行了测试,得到了一系列结果,为后续染色算法的测试做准备。（2）设计并实现了解决D（β）-点可区别边染色和D（β）-点可区别全染色问题的2个多目标优化算法。根据定义,将染色的多个约束条件分别设计成子目标函数,总目标函数设计为子目标函数值之和,每一个子目标函数按照顺序迭代运算,逐步得到最优解,此时染色成功;同时,对算法的正确性、收敛性和复杂度进行了分析。（3）设计了详细的算法测试方案,进而得到了大量的染色结果。通过对实验结果的分析,得到了2个重要结论,同时也表明两个染色算法有很好的执行效率。
尹波[8]（2016）在《随机图的色和可区别染色算法研究》文中进行了进一步梳理现实生活中许多复杂的问题都可通过分类、抽象、简化的思想转化成图论问题进行研究解决,如最大支配集、加工调度、任务分配、排课表等典型的组合类问题,而图染色作为图论中一个重要的研究分支,是解决实际问题的一个重要途径。近些年来,一些经典的智能算法被用来研究和尝试解决图染色问题,如粒子群算法、遗传算法、神经网络算法等,但目前这些算法普遍仅应用于解决图的正常点染色和正常边染色,而对于图染色问题中多约束条件的染色问题,公开发表的文献中尚不多见,因此寻求新的智能算法来解决图的多约束条件染色问题是国内外图论研究者都感兴趣的一个重要课题。图的邻点色和可区别染色问题,在已公开发表的文献中对它们的研究都局限于如正则图、星图、完全图等的特殊图,尚无解决一般图的邻点色和可区别染色、点和可区别染色问题的方法。本文根据两种图的色和可区别染色的定义,分别设计了基于多目标优化的染色算法,对算法的正确性、收敛性和复杂度进行了分析,并通过大量的实例测试,得到了一些很有意义的结果。本文的具体工作如下:⑴介绍了一些基本染色概念及相关猜想,并同时给出有关内容的研究背景及目前国内外的研究动态。⑵介绍了两个经典的智能算法（粒子群算法、遗传算法）的基本思想、流程,及其在图染色中的应用,并对这些算法在解决图染色问题的性能上进行了分析。⑶给出了随机图的生成算法和生成有限点数所有伪非同构图的算法,详细描述了算法步骤,并分别对这两种算法进行了算法测试,为之后染色算法的研究提供了基础数据支持。⑷设计并实现了图的色和可区别染色问题中的邻点和可区别边染色、邻点和可区别全染色、点和可区别边染色和点和可区别全染色四个智能优化算法。四个算法的整体思路都是将其染色问题分解为多个特定功能模块的子问题,依次按序通过对子问题的逐步迭代调整直到子问题解决成功,之后以不改变前一子问题的成功状态为前提解决后一个子问题,当所有子问题都成功解决后,即代表该染色成功,算法结束。文中给出了算法的详细流程及测试案例,分析了算法的正确性、收敛性和时间复杂度,测试实例为7个点以内所有伪非同构图和1000个点以内边密度较小的1万个随机连通图,通过对实验结果的分析,表明算法具有较好的执行效率和不算高的时间复杂度,同时给出了若干有意义的经过验证的结论。
代素敏[9]（2016）在《随机图的均匀染色算法研究》文中进行了进一步梳理图染色问题是一种典型的组合优化问题,现实生活中的很多问题如加工调度、任务分配、负载平衡等都可以用图染色的方法来解决。近些年来,随着计算机技术的发展和解决实际问题的需要,一些经典的智能算法被用来研究和尝试解决图染色问题,如蚁群算法、遗传算法、神经网络等,但限于染色问题的多样性和复杂性,目前这些算法普遍应用于解决图的正常点染色和正常边染色,而对于图染色问题中多约束条件的染色问题,公开发表的文献中尚不多见,因此寻求新的智能算法来解决图的多约束条件染色问题是一个具有理论和实际意义的课题。图的均匀染色是指图中任意两个色类的颜色个数最大相差1,在解决生产调度、任务分配和负载均衡等问题方面有很好的应用,从已公开发表的文献看,有关图的均匀染色算法的成果少见。本文所做的核心工作就是根据四种均匀染色的定义,分别设计并实现了四种均匀染色算法,以及为了测试算法而设计的随机图生成算法,同时给出对上述算法的分析过程,最后利用设计的测试图集对算法进行了全面测试,通过对大量测试结果的分析给出了几个有意义的结论。本文主要工作如下:（1）从随机图染色的角度切入,根据具体的情况将染色问题进行分类;介绍一些图的基础染色概念,如正常边染色、全染色和在此基础上衍生出的点可区别染色和邻点可区别染色的概念;以遗传算法和模拟退火算法作为经典智能算法的代表,介绍其在图染色问题中的应用,同时总结遗传算法和模拟退火算法在解决图染色问题中的优点和不足,为研究解决图的均匀染色问题提供思路和参考。（2）设计并实现四种均匀染色算法。根据图的均匀边染色、均匀全染色、点可区别均匀边染色和邻点可区别均匀边染色的定义,设计了四种算法,每种算法的基本思想是将目标问题分解成几个子问题,设计相应的子约束函数,然后根据这些子约束函数进行迭代调整,逐步解决每个子问题,最终使得总目标函数的值为0,染色成功,算法结束。文中给出了针对算法的正确性、有效性和时间复杂度的分析过程。（3）设计了两类测试图集对算法进行测试,一类为7个点以内的所有图,一类为15个点以内的特殊图。通过对测试结果的分析,得到了有意义的结论。基于正常均匀边染色算法对无线传感器网络广播调度进行时隙分配,得到了较为理想的结果。
张静雯[10]（2011）在《最大度为6的平面图的全染色》文中研究说明图论这门学科最早起源于着名的哥尼斯堡七桥问题,而对图进行染色的研究则起源于着名的四色问题,即对平面上的任何一张地图,总可以用至少四种颜色对每个国家进行染色,且使得相邻的国家染有不同的颜色.图的染色问题一般可分为：顶点染色,边染色,全染色,边面染色和完备染色等等.本学位论文研究的是平面图的全染色,并得出了三个主要结果.给定一个平面图G=（V,E）,分别用V,E,F,△和δ表示它的顶点集,边集,面集,最大度和最小度.平面图的全染色就是对平面图的顶点集和边集中的元素进行染色,如果能用k种颜色使得任意两个相邻或相关联的元素染有不同的颜色,则称图G有一个正常的k-全染色,也称图G是k-全可染的.图G的全色数就是使得图G是正常k-全染色的最小的正整数k.显然,给平面图进行正常全染色至少要用△+1种颜色.对于图的全染色,早在20世纪60年代,Vizing和Behzad就分别独立的提出了全染色猜想：任意的简单图G都是△+2-全可染的.到目前为止,只有最大度为6是否是8-全可染的问题尚未得到解决.本学位论文在最大度为6的基础上加一些限制条件得出了以下结果：（1）设图G是最大度为6且不含相邻4-圈的平面图,则G是8-全可染的.在对全染色的研究过程中,人们有意思的发现很多图类的全染色数还能取到相应的下界,即χT（G）=△+1.于是人们很自然的猜想：对任意的平面图G,χT（G）=△+1.因为这里是对平面图的全色数进行的猜想,于是就把这个猜想称为平面图的全染色猜想（Total Coloring Conjecture for Plane Graphs）,简称PTCC.到目前为止,△≥9的平面图G,已被证实PTCC成立.前面的师兄师姐们对最大度为8和最大度为7的平面图再加一些限制条件,证明PTCC成立已经得出了很多有意义的结果.本学位论文主要研究的是最大度为6的平面图的PTCC问题,得出了以下两个结果：（2）设图G是最大度为6且不含5-圈和相邻4-圈的平面图,则G是7-全可染的；（3）设图G是最大度至少为6且不含相邻4--圈的平面图,则G是（△+1）-全可染的.
二、两类图的全染色问题（论文开题报告）
（1）论文研究背景及目的
此处内容要求：
首先简单简介论文所研究问题的基本概念和背景，再而简单明了地指出论文所要研究解决的具体问题，并提出你的论文准备的观点或解决方法。
写法范例：
本文主要提出一款精简64位RISC处理器存储管理单元结构并详细分析其设计过程。在该MMU结构中,TLB采用叁个分离的TLB,TLB采用基于内容查找的相联存储器并行查找,支持粗粒度为64KB和细粒度为4KB两种页面大小,采用多级分层页表结构映射地址空间,并详细论述了四级页表转换过程,TLB结构组织等。该MMU结构将作为该处理器存储系统实现的一个重要组成部分。
（2）本文研究方法
调查法：该方法是有目的、有系统的搜集有关研究对象的具体信息。
观察法：用自己的感官和辅助工具直接观察研究对象从而得到有关信息。
实验法：通过主支变革、控制研究对象来发现与确认事物间的因果关系。
文献研究法：通过调查文献来获得资料，从而全面的、正确的了解掌握研究方法。
实证研究法：依据现有的科学理论和实践的需要提出设计。
定性分析法：对研究对象进行“质”的方面的研究，这个方法需要计算的数据较少。
定量分析法：通过具体的数字，使人们对研究对象的认识进一步精确化。
跨学科研究法：运用多学科的理论、方法和成果从整体上对某一课题进行研究。
功能分析法：这是社会科学用来分析社会现象的一种方法，从某一功能出发研究多个方面的影响。
模拟法：通过创设一个与原型相似的模型来间接研究原型某种特性的一种形容方法。
三、两类图的全染色问题（论文提纲范文）
（1）符号图的边染色和全染色问题研究（论文提纲范文）
| 浙江师范大学硕士学位论文答辩委员会决议书 |
| 摘要 |
| Abstract |
| 第一章 绪论 |
| 1.1 基本概念 |
| 1.2 符号图的边染色及相关内容的研究概况 |
| 1.3 本文主要结果 |
| 第二章 符号图的边染色 |
| 2.1 一些记号 |
| 2.2 符号图的边染色 |
| 2.2.1 定理2.1的证明 |
| 第三章 符号图的全染色 |
| 3.1 预备知识 |
| 3.2 定理3.1的证明 |
| 3.2.1 非3-正则情形 |
| 3.2.2 3-正则有割边情形 |
| 3.2.3 3-正则无割边情形 |
| 3.3 定理3.2的证明 |
| 3.4 定理3.3的证明 |
| 第四章 总结与展望 |
| 参考文献 |
| 攻读学位期间取得的研究成果 |
| 致谢 |
（2）随机图的点和可约染色算法研究（论文提纲范文）
| 摘要 |
| Abstract |
| 1 绪论 |
| 1.1 研究背景、目的及意义 |
| 1.2 本文主要研究内容 |
| 1.3 本文的组织结构 |
| 2 图染色相关概念及研究现状 |
| 2.1 图及图染色的相关概念 |
| 2.1.1 图的定义 |
| 2.1.2 常见图染色 |
| 2.2 可约染色的研究现状 |
| 2.2.1 可约染色概念 |
| 2.2.2 点和可约染色概念 |
| 2.3 传统的图染色算法 |
| 2.4 本章小结 |
| 3 随机图的点和可约边染色算法 |
| 3.1 基于逐步寻优的VSREC算法 |
| 3.1.1 算法描述及流程 |
| 3.1.2 算法示例 |
| 3.1.3 算法分析 |
| 3.2 基于规则集的VSREC算法 |
| 3.3 基于方程式的VSREC算法 |
| 3.4 VSREC算法分析 |
| 3.5 实验结果及结论 |
| 3.6 本章小结 |
| 4 随机图的点和可约全染色算法 |
| 4.1 算法描述及流程 |
| 4.2 算法示例 |
| 4.3 算法分析 |
| 4.4 算法结果及结论 |
| 4.5 本章小结 |
| 5 随机图的邻点和可约边染色算法 |
| 5.1 基于目标函数邻点和可约边染色算法 |
| 5.1.1 目标函数建立 |
| 5.1.2 AVSREC算法描述 |
| 5.2 基于逐步寻优邻点和可约边染色算法 |
| 5.2.1 算法描述及流程 |
| 5.2.2 算法示例 |
| 5.3 算法分析及结论 |
| 5.3.1 算法分析 |
| 5.3.2 算法结论 |
| 5.4 本章小结 |
| 结论 |
| 致谢 |
| 参考文献 |
| 附录A (邻)点和可约染色部分结果 |
| 攻读学位期间的研究成果 |
（4）完全蛛网图及渔网图的邻点可区别V-全染色（论文提纲范文）
| 1引言 |
| 2主要结果 |
（5）平面图的列表点（边、全）染色和列表线性荫度（论文提纲范文）
| 中文摘要 |
| 英文摘要 |
| 符号说明 |
| 第一章 绪论 |
| 1.1 基本概念 |
| 1.2 图的一些染色问题及相关进展 |
| 1.3 本文的主要结果 |
| 第二章 全染色 |
| 2.1 相关简介 |
| 2.2 最大度至少为8的平面图 |
| 2.2.1 任何两个弦6-圈不相邻,或任意6-圈至多只含一条弦 |
| 2.2.2 任意7-圈至多包含两条弦 |
| 2.3 最大度至少为7的平面图 |
| 第三章 列表染色 |
| 3.1 列表点染色 |
| 3.2 列表边染色和列表全染色 |
| 3.2.1 最大度至少为8的平面图 |
| 3.2.2 最大度至少为6的平面图 |
| 第四章 邻和可区别全染色 |
| 4.1 相关简介 |
| 4.2 可嵌入到欧拉示性数非负曲面上的图 |
| 第五章 列表线性荫度 |
| 5.1 相关简介 |
| 5.2 平面图的列表线性荫度 |
| 第六章 总结与展望 |
| 6.1 一些图类 |
| 6.2 平面图进一步研究的问题 |
| 参考文献 |
| 作者简介 |
| 攻读博士学位期间完成论文情况 |
| 致谢 |
| 学位论文评阅及答辩情况表 |
（6）若干图的邻点强可区别E-全染色（论文提纲范文）
| 摘要 |
| Abstract |
| 引言 |
| 1 相关概念及已得到的结果 |
| 2 若干积图的邻点强可区别E-全染色 |
| 2.1 若干笛卡儿积图的邻点强可区别E-全染色 |
| 2.2 若干强失积图的邻点强可区别E-全染色 |
| 2.3 若干字典积图的邻点强可区别E-全染色 |
| 2.4 若干半强失积图的邻点强可区别E-全染色 |
| 3 若干联图和冠图的邻点强可区别E-全染色 |
| 3.1 若干联图的邻点强可区别E-全染色 |
| 3.2 若干冠图的邻点强可区别E-全染色 |
| 4 若干路、圈运算图的邻点强可区别E-全染色 |
| 4.1 若干路的运算图的邻点强可区别E-全染色 |
| 4.2 若干圈的运算图的邻点强可区别E-全染色 |
| 5 用概率方法研究邻点强可区别E-全染色的上界 |
| 5.1 相关定义及引理 |
| 5.2 主要结果及其证明 |
| 结束语 |
| 致谢 |
| 参考文献 |
| 攻读学位期间的研究成果 |
（7）随机图的D（β）染色算法研究（论文提纲范文）
| 摘要 |
| Abstract |
| 1 绪论 |
| 1.1 引言 |
| 1.2 研究背景、目的及意义 |
| 1.3 本文的主要工作 |
| 1.4 本文的组织结构 |
| 2 图染色相关概念及经典算法概述 |
| 2.0 引言 |
| 2.1 图染色基本定义和猜想 |
| 2.2 遗传算法在图染色中的应用 |
| 2.2.1 遗传算法的基本思想 |
| 2.2.2 遗传算法的基本步骤 |
| 2.2.3 遗传算法解决图染色问题 |
| 2.3 模拟退火算法 |
| 2.3.1 模拟退火算法的基本思想 |
| 2.3.2 模拟退火算法的基本步骤 |
| 2.3.3 模拟退火算法在图染色中的应用 |
| 2.4 本章小结 |
| 3 图的生成算法 |
| 3.1 引言 |
| 3.2 随机图的生成算法 |
| 3.2.1 随机图的定义和模型 |
| 3.2.2 算法描述及流程图 |
| 3.2.3 算法测试 |
| 3.3 生成有限点数所有图算法 |
| 3.3.1 定义主要数据结构及生成树 |
| 3.3.2 算法描述及流程图 |
| 3.3.3 算法测试 |
| 3.3.4 实验结果 |
| 3.4 本章小结 |
| 4 随机图的D(β) - 点可区别边染色算法 |
| 4.1 引言 |
| 4.2 D(β) - 点可区别边染色的相关定义和猜想 |
| 4.3 目标函数的构建 |
| 4.3.1 边约束函数 |
| 4.3.2 色集合约束函数 |
| 4.3.3 总体目标函数 |
| 4.4 主要数据结构的定义 |
| 4.5 算法描述及流程图 |
| 4.5.1 正常边染色算法 |
| 4.5.2 色集合调整算法 |
| 4.5.3 D(β) - 点可区别边染色算法 |
| 4.5.4 D(β) - 点可区别边染色算法的流程图 |
| 4.6 算法测试 |
| 4.6.1 对一个随机图测试 |
| 4.6.2 对大量特殊图测试 |
| 4.6.3 对七个点内所有图测试 |
| 4.7 实验结果 |
| 4.8 算法分析 |
| 4.8.1 算法的正确性 |
| 4.8.2 算法的收敛性 |
| 4.8.3 算法的时间复杂度 |
| 4.9 本章小结 |
| 5 随机图的D(β) - 点可区别全染色算法 |
| 5.1 引言 |
| 5.2 D(β) - 点可区别全染色的相关定义和猜想 |
| 5.3 目标函数的构建 |
| 5.3.1 边约束函数 |
| 5.3.2 顶点约束函数 |
| 5.3.3 色集合约束函数 |
| 5.3.4 总体目标函数 |
| 5.4 算法描述及流程图 |
| 5.4.1 顶点染色算法 |
| 5.4.2 D(β) - 点可区别全染色算法 |
| 5.4.3 D(β) - 点可区别全染色算法的流程图 |
| 5.5 算法测试 |
| 5.5.1 对一个随机图测试 |
| 5.5.2 对大量特殊图测试 |
| 5.5.3 对七个点内所有图测试 |
| 5.6 实验结果 |
| 5.7 算法分析 |
| 5.7.1 算法的正确性 |
| 5.7.2 算法的收敛性 |
| 5.7.3 算法的时间复杂度 |
| 5.8 本章小结 |
| 总结与展望 |
| 致谢 |
| 参考文献 |
| 攻读学位期间的研究成果 |
（8）随机图的色和可区别染色算法研究（论文提纲范文）
| 摘要 |
| Abstract |
| 1 绪论 |
| 1.1 引言 |
| 1.2 研究背景、目的及意义 |
| 1.3 本文的研究内容及组织 |
| 2 经典优化算法在图染色中的应用 |
| 2.1 引言 |
| 2.2 图染色相关定义及猜想 |
| 2.3 粒子群算法在图染色中的应用 |
| 2.3.1 粒子群算法的基本思想 |
| 2.3.2 粒子群算法在图染色中的应用 |
| 2.3.3 粒子群算法总结 |
| 2.4 遗传算法在图染色中的应用 |
| 2.4.1 遗传算法的基本思想 |
| 2.4.2 遗传算法在图染色中的应用 |
| 2.4.3 遗传算法总结 |
| 2.5 本章小结 |
| 3 图的生成算法 |
| 3.1 引言 |
| 3.2 随机图的生成算法 |
| 3.2.1 随机图的定义和模型 |
| 3.2.2 算法描述及流程图 |
| 3.2.3 算法测试 |
| 3.3 生成有限点数所有伪非同构图算法 |
| 3.3.1 定义主要数据结构及生成树 |
| 3.3.2 算法描述及流程图 |
| 3.3.3 算法测试 |
| 3.3.4 实验结果 |
| 4 随机图的邻点和可区别染色算法 |
| 4.1 引言 |
| 4.2 定义主要的数据结构 |
| 4.3 邻点和可区别边染色算法 |
| 4.3.1 目标函数的构建 |
| 4.3.2 算法描述 |
| 4.3.3 算法流程示例 |
| 4.3.4 算法测试与结果分析 |
| 4.4 邻点和可区别全染色算法 |
| 4.4.1 目标函数的构建 |
| 4.4.2 算法描述 |
| 4.4.3 算法流程示例 |
| 4.4.4 算法测试与结果分析 |
| 4.5 算法总结 |
| 5 随机图的点和可区别染色算法 |
| 5.1 引言 |
| 5.2 点和可区别边染色算法 |
| 5.2.1 断言 |
| 5.2.2 目标函数的构建 |
| 5.2.3 算法描述 |
| 5.2.4 算法流程示例 |
| 5.2.5 算法测试与结果分析 |
| 5.3 点和可区别全染色算法 |
| 5.3.1 断言 |
| 5.3.2 目标函数的构建 |
| 5.3.3 算法描述 |
| 5.3.4 算法流程示例 |
| 5.3.5 算法测试与结果分析 |
| 5.4 算法总结 |
| 结论 |
| 致谢 |
| 参考文献 |
| 攻读学位期间的研究成果及参加的科研项目 |
（9）随机图的均匀染色算法研究（论文提纲范文）
| 摘要 |
| Abstract |
| 1 绪论 |
| 1.1 引言 |
| 1.2 研究背景、目的及意义 |
| 1.3 本文的主要工作 |
| 1.4 本文的组织结构 |
| 2 图染色相关概念及经典算法概述 |
| 2.1 引言 |
| 2.2 图染色基本定义和猜想 |
| 2.3 遗传算法在图染色中的应用 |
| 2.3.1 遗传算法的基本思想 |
| 2.3.2 遗传算法的基本步骤 |
| 2.3.3 遗传算法的图染色中的应用 |
| 2.4 模拟退火算法 |
| 2.4.1 模拟退火算法的基本思想 |
| 2.4.2 模拟退火算法的基本步骤 |
| 2.4.3 模拟退火算法在图染色中的应用 |
| 2.5 本章小结 |
| 3 图的生成算法 |
| 3.1 引言 |
| 3.2 随机图的生成算法 |
| 3.2.1 随机图的定义和模型 |
| 3.2.2 算法描述及流程图 |
| 3.2.3 算法测试 |
| 3.3 生成有限点数所有图算法 |
| 3.3.1 定义主要数据结构及生成树 |
| 3.3.2 算法描述及流程图 |
| 3.3.3 算法测试 |
| 3.3.4 实验结果 |
| 3.4 本章小结 |
| 4 随机图的正常均匀边染色及正常均匀全算法 |
| 4.1 引言 |
| 4.2 正常均匀边染色算法 |
| 4.2.1 正常均匀边染色的相关定义和猜想 |
| 4.2.2 目标函数的构建 |
| 4.2.3 主要数据结构的定义 |
| 4.2.4 正常均匀边染色算法描述及流程图 |
| 4.2.5 算法测试 |
| 4.2.6 算法分析 |
| 4.2.7 实验结果 |
| 4.3 正常均匀全染色算法 |
| 4.3.1 正常均匀全染色的相关定义和猜想 |
| 4.3.2 目标函数的构建 |
| 4.3.3 正常均匀全染色算法描述及流程图 |
| 4.3.4 算法测试 |
| 4.3.5 算法分析 |
| 4.3.6 实验结果 |
| 4.4 本章小结 |
| 5 随机图的可区别均匀边染色算法 |
| 5.1 引言 |
| 5.2 邻点可区别均匀边染色算法 |
| 5.2.1 邻点可区别均匀边染色的相关定义和猜想 |
| 5.2.2 目标函数的构建 |
| 5.2.3 邻点可区别均匀边染色算法描述及流程图 |
| 5.2.4 算法测试 |
| 5.2.5 算法分析 |
| 5.2.6 实验结果 |
| 5.3 点可区别均匀边染色算法 |
| 5.3.1 点可区别均匀边染色的相关定义和猜想 |
| 5.3.2 目标函数的构建 |
| 5.3.3 点可区别均匀边染色算法描述及流程图 |
| 5.3.4 算法测试 |
| 5.3.5 算法分析 |
| 5.3.6 实验结果 |
| 5.4 本章小结 |
| 6 基于均匀边染色的无线传感网络广播调度算法 |
| 6.1 引言 |
| 6.2 TDMA时隙分配 |
| 6.3 均匀边染色算法解决广播调度问题 |
| 6.3.1 步骤描述 |
| 6.3.2 算法结果及分析 |
| 6.4 本章小结 |
| 结论 |
| 致谢 |
| 参考文献 |
| 攻读学位期间的研究成果 |
（10）最大度为6的平面图的全染色（论文提纲范文）
| 摘要 |
| ABSTRACT |
| 目录 |
| 1 绪论 |
| 1.1 基本概念 |
| 1.2 平面图的全染色的研究现状 |
| 1.3 可研究课题 |
| 1.4 本文的主要结果 |
| 2 最大度为6的平面图的全染色 |
| 2.1 不含5-圈且不含相邻4-圈的平面图的全可染(PTCC) |
| 2.2 不合相邻4~--圈的平面图的全染色(PTCC) |
| 2.3 不含相邻4-圈的平面图的全染色(TCC) |
| 参考文献 |
| 攻读学位期间取得的研究成果 |
| 致谢 |
四、两类图的全染色问题（论文参考文献）
- [1]符号图的边染色和全染色问题研究[D]. 王超. 浙江师范大学, 2021(02)
- [2]随机图的点和可约染色算法研究[D]. 康玉梅. 兰州交通大学, 2021(02)
- [3]图M（Pn）及Pn2的邻点可区别Ⅰ-均匀全染色[J]. 王继顺,左林,葛仁福. 数学的实践与认识, 2020(15)
- [4]完全蛛网图及渔网图的邻点可区别V-全染色[J]. 李永艳. 内蒙古民族大学学报(自然科学版), 2018(02)
- [5]平面图的列表点（边、全）染色和列表线性荫度[D]. 许仁誉. 山东大学, 2017(08)
- [6]若干图的邻点强可区别E-全染色[D]. 顾忠栋. 兰州交通大学, 2017(03)
- [7]随机图的D（β）染色算法研究[D]. 胡腾云. 兰州交通大学, 2016(04)
- [8]随机图的色和可区别染色算法研究[D]. 尹波. 兰州交通大学, 2016(04)
- [9]随机图的均匀染色算法研究[D]. 代素敏. 兰州交通大学, 2016(04)
- [10]最大度为6的平面图的全染色[D]. 张静雯. 浙江师范大学, 2011(05)