一、一类Halin-图的均匀色数(论文文献综述)
吴建良,杨东雷,杨帆[1](2019)在《平面图的各种染色综述》文中提出文章首先介绍平面图的一些结构和性质,给出了关于点(边,全)方面的染色概念,并综述了一些染色在平面图方面的结果.主要的染色有图的正常点染色、点荫度、线性点荫度、均匀染色、均匀点荫度、无圈点染色、正常边染色、无圈边染色、强边染色、(p,q)-边标号、邻点(和)可区别边(全)染色,荫度、线性荫度、线性k-荫度,全染色以及这些染色的列表情况等.
李明[2](2019)在《平面图的放松均匀染色与强边染色》文中指出设G=(V,E),图G的一个正常的k-点(边)染色就是k种颜色对点(边)的分配,使得任意相邻的点(边)分配到不同的颜色.一个正常的点染色如果每个色类的大小至多差1,称染色是均匀的.图G的均匀染色数是使得图G是均匀m-可染的最小的整数m,用χeq(G)表示.一个放松的k-染色是对点的k-染色使得每个点与至多一个邻点染相同的颜色.图G的一个放松均匀k-染色(简记ED-k-染色)是图G的点集的一个放松的k-染色使得任意两个色类的大小至多差1.图G的ED-色数是使得G是ED-m-可染的最小整数m,记为χed(G).图G的ED-染色阈值是使得图G对任意n≥ m都是ED-n-可染的最小整数m,记为χed*(G).本文我们证明最小度至少2且围长至少为8的平面图有χed*(G)≤4.图的强边染色是一种正常边染色.要求任何长至多为3的路上的边都染不同的颜色.使得图有一个强边染色的最小颜色数称为图的强边色数.用χ’s(G)表示.Faudree等人证明任意最大度为△的平面图有χ’s(G)≤ 4△+4.那么△=4时.χ’s(G)≤ 20.最近,Wang等人证得其强边色数不超过19.本文中我们证明不含带弦5-圈和梯子图L3的平面图是18-强边可染的.并且,对最大度为4的平面图,若它是一个非18-强可染的边数极小图.则它一定不存在至多含三条边的非平凡边割.本论文共分为四章.主要研究了平面图的放松均匀染色问题和强边染色问题.第一章,我们主要介绍了图染色问题的背景及意义,给出了本中用到的基本概念与符号,阐述了放松均匀染色和强边染色问题的研究现状,及本文的主要结果.第二章,我们研究了围长至少为8的平面图的放松均匀染色,证明其对任意m≥4都是ED-m-可染的.第三章,我们研究了最大度为4的平面图18-强边染色,给出了一个充分条件.此外,基于图的k-边割,我们讨论了非18-强边可染的极小图的结构.第四章,我们给出了可进一步研究的问题.
陈琴[3](2017)在《若干Mycielski图的均匀染色》文中进行了进一步梳理如果图G的一个正常顶点染色满足任两个色类中的顶点数相差不超过1,则称为G的均匀染色.研究了一些Mycielski图的均匀染色,给出了路、圈、完全图和广义星图的Mycielski图的均匀色数.
代素敏[4](2016)在《随机图的均匀染色算法研究》文中进行了进一步梳理图染色问题是一种典型的组合优化问题,现实生活中的很多问题如加工调度、任务分配、负载平衡等都可以用图染色的方法来解决。近些年来,随着计算机技术的发展和解决实际问题的需要,一些经典的智能算法被用来研究和尝试解决图染色问题,如蚁群算法、遗传算法、神经网络等,但限于染色问题的多样性和复杂性,目前这些算法普遍应用于解决图的正常点染色和正常边染色,而对于图染色问题中多约束条件的染色问题,公开发表的文献中尚不多见,因此寻求新的智能算法来解决图的多约束条件染色问题是一个具有理论和实际意义的课题。图的均匀染色是指图中任意两个色类的颜色个数最大相差1,在解决生产调度、任务分配和负载均衡等问题方面有很好的应用,从已公开发表的文献看,有关图的均匀染色算法的成果少见。本文所做的核心工作就是根据四种均匀染色的定义,分别设计并实现了四种均匀染色算法,以及为了测试算法而设计的随机图生成算法,同时给出对上述算法的分析过程,最后利用设计的测试图集对算法进行了全面测试,通过对大量测试结果的分析给出了几个有意义的结论。本文主要工作如下:(1)从随机图染色的角度切入,根据具体的情况将染色问题进行分类;介绍一些图的基础染色概念,如正常边染色、全染色和在此基础上衍生出的点可区别染色和邻点可区别染色的概念;以遗传算法和模拟退火算法作为经典智能算法的代表,介绍其在图染色问题中的应用,同时总结遗传算法和模拟退火算法在解决图染色问题中的优点和不足,为研究解决图的均匀染色问题提供思路和参考。(2)设计并实现四种均匀染色算法。根据图的均匀边染色、均匀全染色、点可区别均匀边染色和邻点可区别均匀边染色的定义,设计了四种算法,每种算法的基本思想是将目标问题分解成几个子问题,设计相应的子约束函数,然后根据这些子约束函数进行迭代调整,逐步解决每个子问题,最终使得总目标函数的值为0,染色成功,算法结束。文中给出了针对算法的正确性、有效性和时间复杂度的分析过程。(3)设计了两类测试图集对算法进行测试,一类为7个点以内的所有图,一类为15个点以内的特殊图。通过对测试结果的分析,得到了有意义的结论。基于正常均匀边染色算法对无线传感器网络广播调度进行时隙分配,得到了较为理想的结果。
陶昉昀[5](2015)在《关于图的一些荫度问题的研究》文中认为图G的正常k-全染色是指用k种颜色给V(G)∪ E(G)中的元素进行染色,使得任意两个相邻的或相关联的元素均染不同的颜色。使得图G有正常的k-全染色的最小正整数k称为G的全色数,记为χ"(G)。类似的,我们可以定义图G的正常点染色和正常边染色,对应的色数分别称为点色数和边色数,分别记为χ(G)与χ’(G)。荫度的概念可以看作是图的一种染色(不一定是正常的),其中每个色类的导出子图是一个森林。本文研究了几种不同的荫度概念:图的线性荫度、线性k-荫度、k-星荫度、全荫度、列表全荫度和强均匀点荫度。主要内容概括如下:(1)图的线性荫度。一个线性森林是指每个连通分支都是路的森林。图G的线性荫度是指使得G可以分解成m个线性森林的最小正整数m,用la(G)表示。本文确定了完全图与路、完全图与圈,以及两个完全图的笛卡尔积图的线性荫度。(2)图的线性k-荫度。一个线性k-森林是指每个连通分支都是长度不超过k的路的森林。图G的线性k-荫度是指使得G可以分解成m个线性k-森林的最小正整数m,用lak(G)表示。本文首先研究了两个圈的笛卡尔积图的线性2-荫度,得到了确切的数值。此外,本文研究了几类特殊的平面图,分别给出了这些平面图的线性2-荫度的上界。(3)图的k-星荫度。一个星是指至多一个顶点的度大于1的树。一个k-星森林是指所有分支都是顶点数不超过k+1的星的森林。使得图G可以分解成m个k-星森林的最小正整数m,称为图G的k-星荫度,用sak(G)表示。本文讨论了最大度不超过3的图和树的k-星荫度的上下界,并给出了两个相关的算法。(4)图的全荫度和列表全荫度。在图G的一个k-全染色f(不一定是正常的)中,若每个色类的元素在全图中的导出子图是一个森林,则称f是图G的一个无圈k-全染色。使得图G有一个无圈k-全染色的最小正整数k称为图G的全荫度,记为ρ"(G)。对于图G的每个元素x,如果我们都给它指定一个颜色集合L(x),那么我们称L为G的一个列表。设L是G的一个给定的列表,如果存在G的一个无圈全染色f,满足对任意的元素x ∈ V(G) ∪ E(G)都有f(x)∈L(x),则称f是G的一个无圈列表全染色。若对于满是|L(x)|≥k的任意可能的列表L,G都有一个无圈列表全染色,则称G是无圈k-全可选的。使得图G是无圈k-全可选的最小正整数k称为图G的列表全荫度,记为ρl"(G)。这两个概念是Hetherington提出的。此外,他还提出了关于全荫度的猜想:对任何简单图G,均有本文完全确定了完全图Kn和完全二部图Kn,n的全荫度,证明以上猜想对这两类图是成立的。对于Halin图,我们给出了其列表全荫度的上界。本文还研究了平面图的全荫度,证明了对于△(G)≥13的平面图和△(G)≥7且不含4-圈的平面图,全荫度猜想都是成立的。(5)图的强均匀点荫度。设f是图G的顶点的一个t-染色,若每个色类的导出子图的每个分支都是最大度不超过k的树,则称f为图G的一个(t,k)-树染色。设f为图G的一个(t,k)-树染色且任何两种不同颜色所染的顶点数最多相差1,则称f为图G的一个均匀(t,k)-树染色。使得对所有的t’≥t,图G都具有均匀(t’,k)-树染色的最小正整数t,称作强均匀点k-荫度,记作vak≡(G)。吴建良等人首先提出了这个概念,并且猜想:对任何平面图G,均有va∞≡(G)=O(1)。在本文中,我们首先研究了完全二部图Kn,n的强均匀点1-荫度,得到了一些相关的结果。其次,我们研究了两类特殊的平面图,分别得到了强均匀点∞-荫度的上界,从而证明了吴建良的猜想对这两类平面图是成立的。
张园萍[6](2013)在《若干图类的邻点可区别均匀E-全染色》文中研究表明对简单图G,如果图G存在一个染色法f,使得任意两个相邻的顶点染不同的颜色;任意一条边与其关联的点染不同的颜色;任意两个相邻的点的色集合不相同,并且任意两色所染元素的数目之差不超过1,则称该染色法为的邻点可区别均匀E全染色,其所用最少颜色数称为该图的邻点可区别均匀全色数.本文主要应用穷举法和组合分析法研究了一些图的倍图,Mycielski图,联图,笛卡尔积图的邻点可区别均匀全染色,得到了它们的邻点可区别均匀全色数.论文分为以下五部分:第一部分介绍了图染色的基本概念,常用术语及符号.第二部分介绍了邻点可区别均匀全染色的基本概念和一些重要结果.第三部分主要研究了一些图的倍图及图的邻点可区别均匀全染色,得到了其邻点可区别均匀全色数.第四部分主要研究了一些联图的邻点可区别均匀全色数.第五部分主要研究了一些笛卡尔积图的邻点可区别均匀全染色.
伍芳兰,左连翠[7](2013)在《一类特殊笛卡尔积图的均匀染色》文中进行了进一步梳理利用顶点排序的方法,得出了由圈上某一点延伸出一条路构成的图与完全二部图的笛卡尔积图的均匀色数、均匀色阈。
樊昊[8](2013)在《拟阵圈图的性质和图的染色问题》文中认为图论和拟阵理论在二十世纪经历了空前的发展.图的支撑树及拟阵的基都是组合理论的基本研究对象。一个连通图的树图能够反映该图的不同支撑树之间的变换关系。因此,研究一个图的树图有助于我们更好地了解该图的性质。同样的一个拟阵的基图能够反映该拟阵的不同基之间的变换关系。因此,研究一个拟阵的基图有助于我们更好地了解该拟阵的性质。近些年来,树图和拟阵的基图被推广得到了一些新的图。为了研究拟阵中圈图的性质,P.Li和G.Liu提出了拟阵圈图的概念,并且研究了圈图的连通度,圈图中的路、圈的性质。我们继续对拟阵圈图的性质进行了研究,着重研究了拟阵圈图的边、点容错哈密尔顿性。一个拟阵M就是对于一个有限集E,令C为集合E中非空子集族,它满足如下的公理:(C1)(?)C.(C2)若C1,C2∈C且C1(?)C2,则C1=C2。(C3)若C1≠C2,C1,C2∈C并且存在e∈C1∩C2,则恒有C3∈C满足C3(?)(C1(?) C2)-e.那么我们称M=(E,C)为定义在元素集E上的拟阵。当C∈C(M),我们称C为M的一个圈。如果M的一个圈只有一个元素,则称之为M的一个环。如果两个元素的集合{x,y}是M的一个圈,则称{x,y}为一对平行元。如果M既没有环也没有平行元,则称M是一个简单拟阵。如果一个元素含在M的任一基中,则称之为M的一个反圈。如果S是E的一个子集,且对任意的圈C,都有C(?)S或者C(?)E\S.则称S为M的一个分离集.显然E和(?)都是M的分离集。^M的极小分离集称为M的一个分支。如果拟阵M只有一个分支,则称"为连通拟阵.设e∈E,则M/e和M\e分别表示由拟阵M经过收缩和约束e后所得到的拟阵。拟阵M=(E,B)的基图是这样的一个图G,其中V(G)=B,E(G)={B1B2|B1,B2∈B,|B,\B2|=1},这里图G的顶点和M的基用同样的符号表示。设G是一个图,图G的点集和边集分别记为V(G)和E(G),令v(G)=|V(G)|。包含G的每个点的路称为G的一条哈密尔顿路;同样的,包含G的每个点的圈称为G的一个哈密尔顿圈。如果一个图存在一个哈密尔顿圈,则称之为哈密尔顿的。如果对于一个图G的任意两个顶点来说,G都有-条哈密尔顿路连接他们,则称G是哈密尔顿连通的。如果对一个图G的任意一条边来说,G都有一个含这条边的哈密尔顿圈,则称G是边哈密尔顿的,或者称G是正哈密尔顿的,写作G∈H+。如果对一个图G的任意一条边来说,G都有一个不包含这条边的哈密尔顿圈,则称G是负哈密尔顿的,写作G∈H-。如果G既是正哈密尔顿的,又是负哈密尔顿的,我们称G是一致哈密尔顿的。如果对于图G的任意两条边,均存在一一个哈密尔顿圈包含他们,这个图G就被称为Ez-哈密尔顿的。一个图G被称为k-点容错哈密尔顿的,如果在任意删除不多于k个顶点以后,图仍然是哈密尔顿的,即在余图中仍然存在哈密尔顿圈。类似的,个图G被称为k-边容错哈密尔顿的,如果在任意删除不多于k条边以后,图仍然是哈密尔顿的。现在我们给出拟阵圈图的概念。定义拟阵M的圈图G=G(M)的顶点集V(G)=C,边集E(G)={CC′|C,C′∈C,|C∩C′|≠0}。这里C和C′既代表G的顶点,也代表M的圈。对于一个图G=(V,E),它的一个t-顶点染色,或者t-染色,是指图G的一个从顶点集V到颜色集{1,2…,t}的映射c。如果染色c对于G中的每一条边uu都满足c(u)≠c(u),则称染色c是G的一个正常t-顶点染色且G是可t-染色的.在染色c下,具有相同颜色的顶点构成的集合称为一个色类。如果图G的某个t-顶点染色c的每个色类在G中都能导出一个最大度至多为k的森林,则称c是图G的一个k-森林t-染色。如果G的一个正常t-顶点染色c的任意两个色类的基数之差的绝对值至多为1,则称c是图G的均匀t-顶点染色。图的强均匀染色数χeq*(G)是这样一个整数t的最小值,它使得图G对于每个不小于t的整数t’,都具有一个均匀t’-染色。关于图的强均匀染色数,有一个着名的Chen-Lih-Wu猜想(又称为均匀△-染色猜想),它认为,如果图G是一个连通图,并且G既不是完全图,也不是奇圈,还不是完全二分图K2m+1,2m+1,则χeq*(G)≤△(G)。本文主要研究的是拟阵圈图的边容错哈密尔顿性,点容错哈密尔顿性以及一般图的森林均匀染色问题,全文共分为四章。第一章给出了一个相对完整的简介。首先介绍一些图论中的基本术语和定义,然后给出了关于树图,拟阵基图以及森林图的一个简短但相对完整的综述,最后,给出了本文的主要结论。第二章我们研究了拟阵圈图中的哈密尔顿圈性质。首先我们给出了一个对于拟阵圈图的简短的介绍。然后我们证明了拟阵圈图的E2-哈密尔顿性。在这一章的最后,我们讨论了拟阵圈图的边容错哈密尔顿性。第三章主要讨论拟阵圈图的点容错哈密尔顿性。同样的,首先,给出了对于拟阵圈图容错哈密尔顿性的一个简短的介绍。然后我们讨论了拟阵圈图的点容错哈密尔顿性,并给出证明。第四章主要讨论一般图的森林均匀染色问题。在这一章里,我们首先给出了对于均匀染色的一个简短的介绍。之后,我们讨论了一般图的森林均匀染色问题,并且给出了一个多项式时间算法去构建这样的染色。
王江[9](2011)在《几类扩容图的染色》文中提出图的染色理论在图论中有着非常重要的地位,而全染色一直是人们研究的热点问题之一.本文主要研究了极大扩容图的全色数问题.首先证明了极大扩容图是满足全染色猜想成立的图类.其次,给出了极大扩容图是第一类图的充分条件,针对这个充分条件得到了极大扩容图的一种全染色方法.再次,证明了正则图的极大扩容图是满足均匀全染色猜想的图类.
张文昱[10](2011)在《均匀染色的新途径》文中进行了进一步梳理图论(Graph Theory)是数学的一个分支。它以图为研究对象。图论中的图是由若干给定的点及连接两点的线所构成的图形,这种图形通常用来描述某些事物之间的某种特定关系,用点代表事物,用连接两点的线表示相应两个事物间具有这种关系。二十世纪六十年代以来,图论在科学界突军异起,活跃非凡。图论中有很多着名的问题,如哈密顿问题,四色问题,中国邮递员问题等。并且,应用图论来解决化学,计算机科学,生物学等学科问题已显出极大的优越性。图论作为离散数学的一个重要分支,受到了各方面的普遍重视。均匀染色问题作为图论里的一个重要问题,对于它的研究有着深远的意义。令G表示一个简单图。图的均匀染色,就是指正常染色中任意两个色类中的元素个数最多相差一个。这里主要考虑简单的非空有限图,这些图不包含环以及重边。本文研究了图论中有关均匀染色的若干问题,具体地,我们从树的均匀染色入手,通过在树上加边的方式形成各种带圈的图,从而将简单图做了系统的归类,然后研究这几类加圈图的相关性质及其均匀染色数K的范围。上述问题可以概括如下:任意一个简单图G,其均匀染色数为k,为了方便确定K的范围,我们将G进行分类,按各类别的性质去确定其具体k的范围,达到更科学、更精确的目的。全文共分为五章。第一章,我们给出了一个简短而又相对完整的引言。首先,我们介绍了均匀染色的理论知识。然后,我们给出了一些基本的术语和定义。最后,我们列出本文的主要结果。在第二章里,针对连通的简单图,我们先从简单一些的图类入手,这里是以树入手,巧妙借助已经存在的若干定理,来研究这类图的均匀染色数k。在第三章里,我们对剩下的连通含圈简单图进行研究,将其分类细化,设计相关算法,寻求其均匀染色数k的范围。具体分成以下三大类:第一类,图G里不存在奇圈。在这一类情况里,我们将图G看成二分图G(x,y),然后按照二分图的性质来研究其均匀染色色数的范围。第二类,图G中不存在偶圈。对于此类情况,我们不难得出其任意两个圈都不相交的结论。这样便大大简化了我们确定均匀染色色数的难度。而另外关键的一步是将此大类按照这样一个规则划成两小类,即,图G中是否存在满足|X|-|Y|≥2条件的子树Ti(X,Y)。如果不存在该条件的子树,则图G是3-均匀可染色的。反之,如果图G中存在满足条件的子树Ti(X,Y)时,我们便采用二分搜索方法来锁定均匀染色色数的范围。这里k是介于3和K1之间的数。在本部分,我们构造了相关例子来演示该方法。第三类,图G中既存在奇圈,又存在偶圈。这里又可以分两种情况来讨论。分类标准是,图G里的圈是否相交。如果严格不存在相交的情况,便可以运用前面提到的第二类方法来解决此类问题;然而,如果存在相交的情况——这种情况相对来说比较复杂,我们便对其进行树分解,找到图G的树宽w,即w-退化的,借助树宽,可以确定该图G的均匀染色色数k的范围。在第四章里,主要研究那些非连通简单含圈图的均匀染色数k。本文先从森林入手,将此类图划分为两类,即森林F和其他类别的图G,然后研究这两类图的均匀染色数k的范围。最后,在第五章里,我们做了一些总结和相应的一些推广
二、一类Halin-图的均匀色数(论文开题报告)
(1)论文研究背景及目的
此处内容要求:
首先简单简介论文所研究问题的基本概念和背景,再而简单明了地指出论文所要研究解决的具体问题,并提出你的论文准备的观点或解决方法。
写法范例:
本文主要提出一款精简64位RISC处理器存储管理单元结构并详细分析其设计过程。在该MMU结构中,TLB采用叁个分离的TLB,TLB采用基于内容查找的相联存储器并行查找,支持粗粒度为64KB和细粒度为4KB两种页面大小,采用多级分层页表结构映射地址空间,并详细论述了四级页表转换过程,TLB结构组织等。该MMU结构将作为该处理器存储系统实现的一个重要组成部分。
(2)本文研究方法
调查法:该方法是有目的、有系统的搜集有关研究对象的具体信息。
观察法:用自己的感官和辅助工具直接观察研究对象从而得到有关信息。
实验法:通过主支变革、控制研究对象来发现与确认事物间的因果关系。
文献研究法:通过调查文献来获得资料,从而全面的、正确的了解掌握研究方法。
实证研究法:依据现有的科学理论和实践的需要提出设计。
定性分析法:对研究对象进行“质”的方面的研究,这个方法需要计算的数据较少。
定量分析法:通过具体的数字,使人们对研究对象的认识进一步精确化。
跨学科研究法:运用多学科的理论、方法和成果从整体上对某一课题进行研究。
功能分析法:这是社会科学用来分析社会现象的一种方法,从某一功能出发研究多个方面的影响。
模拟法:通过创设一个与原型相似的模型来间接研究原型某种特性的一种形容方法。
三、一类Halin-图的均匀色数(论文提纲范文)
(1)平面图的各种染色综述(论文提纲范文)
1 平面图及其结构性质 |
2 平面图的点染色 |
2.1 染色定义 |
2.2 平面图的点染色与(k,d)-可选性 |
2.3 均匀点染色和均匀点荫度 |
2.4 无圈点染色 |
2.5 点荫度和线性点荫度 |
3 平面图的边染色 |
3.1 边染色方面的定义 |
3.2 正常边色数 |
3.3 列表边色数 |
3.4 无圈边色数 |
3.5 强边色数 |
3.6 均匀边色数 |
3.7 邻点(和)可区别边色数 |
3.8 平面图的荫度、线性荫度、线性k-荫度以及列表情况 |
4 平面图的全染色 |
4.1 平面图的全染色和列表全染色 |
4.2 邻点(和)可区别的全染色 |
4.3 无圈全染色 |
5 与平面图的面有关的染色 |
6 可以继续探讨的一些问题 |
(2)平面图的放松均匀染色与强边染色(论文提纲范文)
中文摘要 |
英文摘要 |
第一章 引言 |
1.1 基本概念与符号 |
1.2 图的放松均匀染色问题的研究现状 |
1.3 图的强边染色问题的研究现状 |
1.4 本文的主要结果 |
第二章 放松均匀染色问题 |
2.1 预备知识和主要结果 |
2.2 极小反例的结构 |
2.3 定理2.1.2的证明 |
第三章 强边染色问题 |
3.1 一类18-强边可染的△=4的平面图 |
3.2 非18-强边可染的极小反例的结构 |
第四章 可进一步研究的问题 |
参考文献 |
攻读学位期间完成、发表或提交的学术论文 |
致谢 |
(3)若干Mycielski图的均匀染色(论文提纲范文)
1引言 |
2主要结果及其证明 |
(4)随机图的均匀染色算法研究(论文提纲范文)
摘要 |
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 本章小结 |
结论 |
致谢 |
参考文献 |
攻读学位期间的研究成果 |
(5)关于图的一些荫度问题的研究(论文提纲范文)
摘要 |
Abstract |
第一章 绪论 |
1.1 图的基本定义及符号 |
1.2 图的几种荫度的定义及研究概况 |
1.2.1 荫度、线性荫度、线性k-荫度及星荫度 |
1.2.2 点荫度、全荫度、列表全荫度 |
1.2.3 均匀点荫度和强均匀点荫度 |
1.3 本文主要研究内容 |
第二章 笛卡尔积图的线性荫度及线性2-荫度 |
2.1 笛卡尔积图的线性荫度 |
2.2 笛卡尔积图的线性2-荫度 |
第三章 平面图的线性2-荫度 |
3.1 不含相邻3-圈或不含相邻4-圈的平面图 |
3.1.1 结构定理 |
3.1.2 线性2-荫度 |
3.2 不含相交4-圈的平面图 |
3.2.1 结构定理 |
3.2.2 线性2-荫度 |
3.3 4-圈与5-圈不相邻的平面图 |
3.4 3-圈与5-圈不相邻的平面图 |
第四章 图的k-星荫度 |
4.1 定义及基本性质 |
4.2 最大度不超过3的图的2-星荫度 |
4.3 树的k-星荫度 |
第五章 图的全荫度及列表全荫度 |
5.1 完全图和完全二部图的全荫度 |
5.2 Halin图的列表全荫度 |
5.3 平面图的全荫度 |
第六章 图的强均匀点荫度 |
6.1 完全二部图K_(n,n)的强均匀点1-荫度 |
6.2 平面图的强均匀点∞-荫度 |
第七章 总结与展望 |
参考文献 |
附录一 个人学习经历 |
附录二 博士期间发表和完成的论文 |
附录三 博士期间参加的科研项目、学术会议 |
附录四 致谢 |
(6)若干图类的邻点可区别均匀E-全染色(论文提纲范文)
摘要 |
Abstract |
引言 |
1 基本概念及相关猜想 |
2 邻点可区别均匀E-全染色的概念和一些结果 |
3 若干图的倍图和 Myielski 图的邻点可区别均匀E-全染色 |
3.1 相关定义 |
3.2 主要结论及证明 |
4 若干图的联图的邻点可区别均匀E-全染色 |
4.1 相关定义 |
4.2 主要结论及证明 |
5 三类笛卡尔积图的邻点可区别均匀E-全染色 |
5.1 相关定义 |
5.2 相关证明及结论 |
结论 |
致谢 |
参考文献 |
攻读学位期间的研究成果 |
(7)一类特殊笛卡尔积图的均匀染色(论文提纲范文)
0 引言 |
1 主要结论 |
(8)拟阵圈图的性质和图的染色问题(论文提纲范文)
目录 |
中文摘要 |
英文摘要 |
第一章 绪论 |
1.1 基本概念 |
1.2 拟阵的基图 |
1.3 树图和其他衍生图 |
1.4 拟阵的基关联图 |
1.5 图的均匀染色 |
1.6 本文的主要结果 |
第二章 拟阵圈图的边可攻击哈密尔顿性 |
2.1 相关定义及背景介绍 |
2.2 引理 |
2.3 主要定理 |
第三章 拟阵圈图的点可攻击性 |
3.1 相关定义及背景介绍 |
3.2 引理 |
3.3 主要定理 |
第四章 图的松弛均匀染色 |
4.1 图的松弛均匀染色 |
4.2 当d=1时,关于定理4.1.10(a)的一个多项式时间算法 |
参考文献 |
致谢 |
攻读博士学位期间完成论文情况 |
作者简介 |
学位论文评阅及答辩情况表 |
(9)几类扩容图的染色(论文提纲范文)
中文摘要 |
ABSTRACT |
引言 |
第一章 基本知识与基本理论 |
第二章 极大扩容图全色数的证明 |
第三章 极大扩容图均匀染色的证明 |
总结 |
参考文献 |
符号和记法 |
攻读硕士学位期间发表学术论文情况 |
致谢 |
(10)均匀染色的新途径(论文提纲范文)
摘要 |
Abstract |
符号说明 |
第一章 简介 |
1.1 图论、均匀染色的相关背景 |
1.2 基本的概念和定义 |
1.3 主要结论 |
第二章 不带圈的连通简单图G的均匀染色 |
第三章 带圈的连通简单图G的均匀染色 |
3.1 图G里不存在奇圈的情形 |
3.2 图G中不存在偶圈的情形 |
3.3 图G中既存在奇圈,又存在偶圈 |
第四章 非连通的简单带圈图G的均匀染色 |
4.1 森林的均匀染色 |
4.2 其他情况 |
第五章 总结与展望 |
参考文献 |
致谢 |
个人简介 |
学位论文评阅及答辩情况表 |
四、一类Halin-图的均匀色数(论文参考文献)
- [1]平面图的各种染色综述[J]. 吴建良,杨东雷,杨帆. 广州大学学报(自然科学版), 2019(05)
- [2]平面图的放松均匀染色与强边染色[D]. 李明. 山东师范大学, 2019(01)
- [3]若干Mycielski图的均匀染色[J]. 陈琴. 数学的实践与认识, 2017(24)
- [4]随机图的均匀染色算法研究[D]. 代素敏. 兰州交通大学, 2016(04)
- [5]关于图的一些荫度问题的研究[D]. 陶昉昀. 东南大学, 2015(06)
- [6]若干图类的邻点可区别均匀E-全染色[D]. 张园萍. 兰州交通大学, 2013(02)
- [7]一类特殊笛卡尔积图的均匀染色[J]. 伍芳兰,左连翠. 山东大学学报(理学版), 2013(04)
- [8]拟阵圈图的性质和图的染色问题[D]. 樊昊. 山东大学, 2013(10)
- [9]几类扩容图的染色[D]. 王江. 内蒙古师范大学, 2011(10)
- [10]均匀染色的新途径[D]. 张文昱. 山东大学, 2011(04)