关于图的 L(d,1)-labeling 问题

一、关于图的L(d,1)-标号问题（论文文献综述）

刘跃芹,洪雷,王惟帝,吕大梅^[1]（2021）在《竖梯的局部替换图的L（1,1,1）-标号》文中认为图G的一个L（1,1,1）-标号是从顶点集V（G）到非负整数集的一个映射f,使得当d（u,v）=1,2,3时,都有|f （u）-f（v）|≥1.不妨设0为最小标号,则称图G的所有L（1,1,1）-标号中的最大跨度f（v）的最小数为图G的L（1,1,1）-标号数.给出了竖梯的局部替换图的L（1,1,1）-标号数的确切值.

孙帅^[2]（2021）在《随机图的L（2,1）-标号算法及其在频率分配中的研究》文中提出作为图染色问题的一种推广,图的标号问题具有极高的理论价值,自诞生以来就成为了图论研究领域中最热门的方向之一。近年来,通过对各类标号模型的研究,得到的一些成果在科学技术和工程领域中都有着广泛的应用,这使得图标号问题备受关注。标号模型通常来自于实际问题中所隐含的拓扑关系,对这些模型的研究不但有助于解决实际问题而且也促进了图论自身的发展。标号问题通常指为图的顶点或边分配自然数,使其满足某些特定的条件,根据条件的不同,学者们提出了各类标号模型的定义并进行了深入地研究,逐渐形成了种类丰富的图标号理论。传统研究方法主要是基于图自身的拓扑结构,通过组合构造法来完成标号的,但能够被这种方法处理的图大多较为特殊,并不适用于一般的随机图。随着计算机科学的快速发展,设计针对随机图的算法来解决各类图标号问题是一种新的研究方法和思路。本学位论文主要研究与信道频率分配相关的L（2,1）-标号及其变种问题,利用算法得到有限点内非同构连通图的标号结果,通过对实验数据的分析,得到了几类图的标号结论。主要工作如下:（1）介绍图及图标号的概念,总结概括L（2,1）-标号及相关变种问题的研究现状,分析目前存在的问题。（2）设计并实现了随机图的L（2,1）混合优化标号算法,对10个点内所有的简单连通图进行L（2,1）-标号求解,得到了正确的标号结果。在整理分析实验结果后,得出了有限点内的相关定理并提出了相应的猜测,基于这些猜测,扩大实验范围,对更大点数的图（主要包括16个点以内的所有单圈图和一些正则图）进行了验证。围绕Griggs关于L（2,1）-标号上界的猜想,本文结合实验结果提出了有关非正则图的更小上界猜测:若图G为非正则的连通图,则其L（2,1）-标号数不超过2Δ+1。使用算法只能得到有限点内随机图的结论,而且随着点数的增加,图结构更为复杂,图集的数量也呈爆炸式增长,所以获取全部的图集数据并不现实,故定义了几类联图,结合算法结果和组合构造法给出这几类联图的数学证明,充分发挥了算法和组合构造法的优势。（3）针对映射到边的L（2,1）-边标号问题,设计了基于线图和多目标优化的两种求解算法,而对要求将映射集合内元素全部用到的全色L（2,1）-标号问题,则使用启发式搜索算法进行求解。实验分别得到了9个点以内图的标号数据,整理并得到了关于树图、单圈图和双圈图的相关结论与猜测,其中,树图边标号的结论改进了已知的结果。（4）结合L（2,1）-标号理论及算法,设计频率分配仿真实验,说明其可行性和应用价值。

李俊峰,洪雷,王惟帝,邢诗豪,张易安,吕大梅^[3]（2021）在《路圈Cartesian积的局部替换图的L（1,1,1）-标号》文中研究说明图G的一个L（1,1,1）-标号就是从顶点集V（G）到非负整数集的一个映射f,使得当d（u,v）=1,2,3时,都有|f（u）-f（v）|≥1.不妨设0为最小标号,则称图G的所有L（1,1,1）-标号中最大跨度f（v）的最小数为图G的L（1,1,1）-标号数,记为λ1（G）.给出了一类路圈Cartesian积的局部替换图的L（1,1,1）-标号数的确切值.

刘乐^[4]（2020）在《几类图的L（1，d）-标号》文中认为图G中任意顶点u和v,d（u,v）表示这两个顶点u,v在图G中的距离.设m是一个非负整数,f:V（G）→[0,m]是一个映射,如果f满足条件:当d（u,v）=1时,|f（u）-f（v）|≥1;当d（u,v）=2时,|f（u）-f（v）|≥2,则称f是图G的一个m-L（1,2）-标号.图G的L（1,2）-标号的最小跨度用λ1,2（G）表示,称为图G的L（1,2）-标号数.对于一个正实数σ,S（σ）表示一个周长为σ的圈,它可看成是把数轴上的闭区间[0,σ]首尾的0和σ重合从而得到的圈,S（σ）称为σ-圈.对于任意一个x,x∈R,[x]σ∈[0,σ]表示σ除以x以后的余数.定义|p-q|σ=min{|p-q|,σ-|p-q|},|p-q|σ称为两个点p和q在S（σ）上的圆距离.f:V（G）→[0,σ)是一个映射,如果f满足条件:当d（x,y）=1时,|f（x）-f（y）|σ≥1:当d（x,y）=2 时,|f（x）-f（y）|σ≥2,则称f是图 G 的一个σ-L（1,2）-圆标号.图G所有的L（1,2）-圆标号里最小的σ称为G的L（1,2）-圆标号数,用σ1,2(（G）表示.无向图G的k次幂指的是和图G具有相同顶点集的图,且图G中距离不大于k的两个顶点之间有一条边,特别地,称G2为图G的平方图.设整数k和n满足1≤k≤n-1,且2k≠n,则广义Petersen图P（n,k）的定义为:顶点集V（P（n,k））={u0,u1,…,un-1;v0,v1,…,vn-1},边集E（P（n,k））包含以下三种形式的边,即[ui,ui+1],[ui,vi],[vi,vi+k],其中i是一个整数且下标i+1,i+k需要模n.本文主要研究了圈Cn的平方图的L（1,2）-标号和L（1,2）-圆标号问题,这里的n≥3,还讨论了广义Petersen图P（n,n-1/2）的L（1,2）-标号问题,其中n是奇数.

李亚男,吴钰莉,蔡雨,吕大梅^[5]（2020）在《点接拟梯子的L（d,1,1）-标号》文中提出图G的L（d,1,1）-标号指的是顶点集V（G）到非负整数集的一个映射f,且当d（u,v）=1时,|f（u）-f（v）|≥d;当d（u,v）=2时,|f（u）-f（v）|≥1;当d（u,v）=3时,|f（u）-f（v）|≥1。不妨假设最小的标号为0.G的L（d,1,1）-标号数λ（G）指的是G的全部L（d,1,1）-标号下的跨度max{f（v）;v∈V（G）}最小值。基本上确定了点接拟梯子的L（d,1,1）-标号数。

李海萍,杨英^[6]（2018）在《手镯图的L（2,1）—标号》文中指出为了更好地研究频道分配问题,引入了从顶点集到非负整数集的一个函数,即图的一个L（2,1）—标号。假设最小标号为零,图的L（2,1）—标号数就是此图的所有L（2,1）—标号下的跨度的最小数。对于路和圈的Cartesian积图的推广图——手镯图的标号数问题,给出了手镯图的定义,即是将拟梯子的两端重合而得到的图形,同时给出了其L（2,1）—标号数的定义,运用顶点分组标号法,根据圈的个数和每个圈的顶点数的不同进行分类讨论,研究结果完全确定了手镯图的L（2,1）—标号数的确切值,丰富了图的种类并完善了标号数理论。

杜娟,吕大梅,张科^[7]（2016）在《Cartesian积的局部边-路替换图的L（2,1）-标号》文中指出设d为正整数,图G的一个L（d,1）-标号就是从非负整数集到V（G）的一个函数,且使得2个相邻顶点的标号相差至少是d,2个距离为2的顶点的标号相差至少为1.图G的L（d,1）-标号的跨度就是所有L（d,1）-标号的最大值和最小值之差.图G的L（d,1）-标号数是G的所有L（d,1）-标号下跨度的最小值.在已有研究图G的边-路替换图的L（d,1）-标号基础上,研究了Cartesian积的局部边-路替换图的L（2,1）-标号.

戴本球^[8]（2015）在《图的放松的距离二标号着色》文中认为标号着色是从频道分配问题中抽象出来的一种图着色概念。与经典的图着色相比,它不仅要求图中相邻元素的着色有着明显的差别,同时还要求图中不相邻元素的着色有所不同。图G的距离二标号着色也即L（j,k）-标号,有整数距离二标号（j,k为非负整数）和实数距离二标号（j,k为非负实数）两种模式。它们分别是定义在V（G）→{0,1,2,3,…}和V（G）→[0,+∞)上的函数f,满足条件：（1）|f（u）-f（v）|≥j,若uv∈E（G）；（2） |f（u）-f（v）|≥k,若d（u,v）=2。图G的L（j,k）-标号着色数λj,k（G）=minf max{f（v）: v∈V（G）}。随着图着色问题研究的不断深入,各种各样的图着色的变形和推广出现并被广泛研究,诸如有缺陷着色、非正常着色、荫度等等,它们都可看作是对图的正常着色的放松。着色放松问题实际上还有很多问题值得深入挖掘和思考。标号着色的放松问题在理论上就值得研究,同时它也有实际应用价值。为解决频道分配问题,需要选取合适的数学模型,合理地分配稀缺并且有限的频道资源。放松的距离二标号着色是更为合适的频道分配问题的数学模型。假设G是一个图,f：V（G）→{0,1,2，...]是一个映射,s,t是两个非负整数。若对于G的任何两个相邻顶点u,v,f（u）≠f（v）；对于G的任何顶点u,至多有s个u的邻点标号属于集合{f（u）-1,（u）+1},至多有t个u的2-邻点的标号等于f（u）,则称f是图G的（s,t）-放松的L（2,1）-标号。记f的跨度为span（f）,表示图中顶点的最大标号和最小标号的差。图的（s,t）-放松的L（2,1）-标号的最小跨度定义为图的（s,t）-放松的L（2,1）-标号着色数,记为λ2,1s,t（G）。图的（s,t）-放松的L（2,1）-标号是对图的整数L（2,1）-标号作出相应的放松而产生的新的图标号概念。假设G是一个图,f：V（G）→[0,+∞)是一个映射,s,t是两个非负整数,j,k是实数并且j>k≥1。若对于任一顶点u,至多s个u的邻点标号属于（f（u）-j,f（u）-k]∪ [f（u）+k,f（u）+j）,其他邻点的标号属于[0,f（u）-j]∪[f（u）+j,+∞)；至多t个u的2-邻点的标号属于（f（u）-k,f（u）+k）,u的其他2-邻点的标号属于[0,f（u）-k]∪[f（u）+k,+∞),则称f是图G的（s,t）-放松的L（j,k）-标号。图的（s,t）-放松的L（j,k）-标号着色的最小跨度定义为图的（s,t）-放松的L（j,k）-标号着色数,记为λj,ks,t（G）。图的（s,t）-放松的L（j,k）-标号这一概念是通过对图的实数L（j,k）-标号作出相应的放松而产生的。若d＝j/k,则λj,ks,t（G）=kλd,1s,t（G）。图的（s,t）-放松的L（j,k）-标号和图的（s,t）-放松的L（d，1）-标号可以相互转化。网格图（六边形网格图、四边形网格图以及三角形网格图）是频道分配问题中干扰图的理想模型。本文主要考虑各种网格图的（s,t）-放松的L（2,1）-标号着色以及（s,t）-放松的L（d,1）-标号着色问题,研究并得出了它们的一些基本性质,讨论了它们的所有可能的（s,t）-放松的情形。确定了三种网格图的所有s,t情形下的（s,t）-放松的L（2,1）-标号着色数,确定了六边形网格图的所有s,t和任意d>1情形下的（s,t）-放松的L（d,1）-标号着色数,确定了四边形网格图的几乎所有s,t和任意d>1情形下的（s,t）-放松的L（d,1）-标号着色数（除了s＝0,t＝1,1<d<2这一情形以外）,确定了三角形网格图的大多数情形下的（s,t）-放松的L（d,1）-标号着色数以及其余情形下的（s,t）-放松的L（d,1）-标号着色数的界。这些结果给相应的频道分配问题提供了一系列的频道分配方案。

段滋明^[9]（2011）在《图论中的距离标号理论及其在力学计算中的应用研究》文中认为图论是研究离散系统结构的一门学科分支,图的标号问题是图论中重要的研究领域之一,其在科学技术和工程领域中有广泛的应用。图的距离标号问题是近30年来研究比较活跃的一个标号分支,最初源于对频率分配问题的研究,同时又是经典的图染色理论的推广,具有重要的理论研究价值与应用前景。图的距离标号定义如下:对简单图G = （V ,E）,给定整数k1 , k 2, , k p,设f : V （G ）→{0,1,2, , k},若满足:对任意两个顶点x, y,当d （ x , y ） = i≤p时,有| f （ x ） ? f （ y ） |≥ki,则称f为图G的一个L （ k1 , k 2, , k p）-标号,或称为图G的距离p标号,有时也直接称为图G的距离标号,其中d （ x , y ）表示顶点x与y之间的距离。使得图G存在L （ k1 , k 2, , k p）-标号的最小k称为图G的L （ k1 , k 2, , k p）-标号数,记作1 , 2, , （ ）λk k k pG或λ（G ; k1 , k 2, , kp）。当x, y是图G的边时,将上述诸概念相应位置添加“边”字即可得图的距离边标号的概念。图的距离标号理论可以直接应用于力学计算中。有限单元法是力学计算的重要工具,有限元节点编号是有限单元法的重要步骤,对计算效率有显着影响。从图论角度来看,有限元节点编号问题就是图的距离标号问题,可以用图的理论来进行节点编号优化。自图的距离标号概念提出以来,已获得了较丰富的研究结果。但这些结果主要都是有关L （2,1）-标号以及L （ h, k ）-标号的研究,有关p≥3的研究结果还很少。不过,在最近的几年中, p≥3的距离标号问题的研究已逐渐被越来越多的学者所关注,正成为图论中的一个热点研究问题。本论文研究图的距离标号理论及其应用,包括一般图、树、无限正则网格图及外平面图等图类的L （ h, k ）-标号、L （ h, 2,1）-标号及L （ h, 1, ,1）-标号问题,以及标号理论在力学计算中的应用。论文共分六部分,各部分的主要工作叙述如下:第一部分给出了论文所涉及的一些基本概念与术语;介绍了图的距离标号问题的研究背景、研究现状及其在工程中的应用;最后介绍了论文的主要工作。第二部分主要研究图的L （ h, k ）-标号与L （ h, k ）-边标号问题。主要结果包括:1)Griggs-Yeh关于L （2,1）-标号数的Δ2-猜想是该领域中着名的猜想,目前仍没有完全解决。研究了一般图的全图、斜积图、反斜积图及笛卡尔和图的L （2,1）-标号,给出了这些图类标号数的上界,所得结果分别改进了已有结果,部分证明了这些图类满足Griggs-Yeh猜想;2)研究了外平面图的L （ h, k ）-标号问题,给出了标号数的一个上界,部分改进了已有结果。3)研究了图的L （ h, k ）-边标号问题:分析了一般图的L （ h, k ）-边标号的性质;提供了对图进行L （ h, 1）-边标号的一个算法,利用该算法得到了L （ h, 1）-边标号数的一般上界,该上界改进了已有结果;最后,给出了外平面图的L （ h, k ）-边标号数的上界。第三部分主要研究图的L （ h, 2,1）-标号问题,研究的图类包括一般图、树、无限正则格子图及弦图、t-树、外平面图与全图等。主要结果包括:1)分析了一般图的L （ h, 2,1）-标号的性质;得到了对图进行L （ h, 2,1）-标号的一个算法;给出了L （ h, 2,1）-标号数的上、下界;并分析了图的完美匹配、哈密尔顿性与上界的关系。2)给出了树的L （ h, 2,1）-标号数的上、下界,并且该上、下界都是可达的;同时给出了无限正则树的L （ h, 2,1）-标号算法。3)研究了4种无限正则网格图的L （ h, 2,1）-标号问题:一些情况给出了精确的标号数,其它情况给出了标号数的上、下界;在所有情况下,都给出了一个L （ h, 2,1）-标号算法。4)研究了弦图、t -树、外平面图与全图的L （ h, 2,1）-标号问题,给出了这些图类的标号数的上界,并给出了路的全图的确定的L （3,2,1）-标号数。第四部分主要研究图的L （ h, 1, ,1）-标号问题,研究图类包括一般图、树及无限正则网格图等。主要结果包括:1)分析了L （ h, 1, ,1）-标号的一般性质,并对一对一的L （ h, 1, ,1）-标号数与完美匹配、哈密尔顿性的关系做了探讨;给出了对任意图进行L （ h, 1,1）-标号的一个算法,给出了一般图G的L （ h, 1,1）-标号数的上、下界。2)给出了树的L （ h, 1,1）-标号数的上、下界,所得上界部分改进了已有结果,并且该上、下界是可达的;给出了无限正则树及正则毛毛虫树Cat n确定的L （ h, 1,1）-标号数;另外,还给出了树的L （1, ,1）-标号数的一般表达式,并给出了无限正则树的L （1, ,1）-标号数的确定值。3)给出了无限六边形与八边形网格图的确定的L （ h, 1,1）-标号数;给出了无限三角形网格图的L （ h, 1,1）-标号数的上、下界;给出了无限八边形网格图大部分情况下的L （ h, 1, ,1）-标号数的确定值,只有一种情况是给出了上、下界。第五部分研究图的距离标号理论在力学计算中的应用。主要结果包括:1)有限单元法是力学计算的重要工具,用图论的语言对有限元节点编号问题进行了描述。2)在分析了几种基于图论的有限元节点编号优化方法后,提出了一种新的有限元节点编号优化方法,该方法简单可行,能较有效的对带宽进行优化。第六部分总结了论文的主要工作并对进一步研究的工作作了展望。该论文有图18幅,参考文献130篇。

王慧娟^[10]（2010）在《与图的L（d，1）-标号相关的几种图标号问题》文中研究说明图的染色问题是图论中研究的主要问题之一,也是图论研究中一个活跃的领域,因此各类染色问题被相继提出并加以发展应用,其中图的染色问题的一个重要推广是图的标号问题.作为频道分配问题的一个变形，Griggs和Yeh在1992年文章[1]中提出了图的L（2,1）-标号问题.假如给定一些基站,我们想给每一个基站在避免干扰的条件下给它分配一个频道.为了避免干扰,我们要求非常近的基站之间必须是至少差两个频道的,稍近的一些基站也让它们分配不同的频道.为了方便起见,把基站看作是点,如果两个基站非常近则在两个基站间连一条边,如果两个点距离为2则对应的基站可以看作是稍近.这样我们就可以定义L（2,1）-标号了本文只考虑简单连通图G.定义1图G的一个L（2,1）-标号是一个满足下面两个条件的映射c：V（G）→(0,1,2…k},（1）对任意的u,v∈V（G）,若d（u,v）=1,则|c（u）-c（v）|≥2；（2）对任意的u,v∈V（G）,若d（u,v）=2,则|c（u）-c（v）|≥1.当所有的标号都小于等于k时,则称图G有一个k-L（2,1）-标号.使得图G有一个k-L（2,1）-标号的最小的正整数k称为图G的L（2,1）-标号数,记为λ（G）.同样的,我们可以定义L（d,1）-标号.定义2图G的一个L（d,1）-标号是一个满足下面两个条件的映射c：V（G）→{0,1,2…k},（1）对任意的u,v∈V（G）,若d（u,v）=1,则|c（u）-c（v）|≥d；（2）对任意的u,v∈V（G）,若d（u,v）=2,则|c（u）-c（v）|≥1.当所有的标号都小于等于k时,称图G有一个k-L（d,1）-标号.使得图G有一个k-L（d,1）-标号的最小的正整数k称为图G的L（d,1）-标号数,记为λd（G）.记λ2（G）=A（G）.现在已经有很多的文章在研究L（2,1）-标号问题,但是很多文章是在特殊图类上研究λ（G）.Griggs和Yeh[1]证明了对最大度是△的一般图G,λ（G）≤△2+2△. Chang和Kuo[2]把上界改进到△2+△,近期Kral和Skrekovski[3]把上界改进到了△2+△-1,并证明了若图G的直径是2,则λ（G）≤△2,指出了Moore图是可以达到这个上界的.因此Griggs和Yeh[1]猜想对任意的△≥2的图G最好的上界是△2,且证明了确定图G的λ（G）是NP-困难的.本文中△（G）表示图G的最大度,δ（G）表示图G的最小度,d（u,v）表示u,v两点在图G中的距离,即u,v之间最短路的长度.在本文的第二章中,我们研究了图G的（d,1）-全标号.Whittleseyet等人在文章[4]中研究了图G的第一剖分图的L（d,1）-标号.图G的第一剖分图s1（G）是图G通过在每一条边上加一个点得到的.图G的第一剖分图s1（G）的L（d,1）-标号其实就是图G的（d,1）-全标号.定义3[5]图G的（d,1）-全标号是满足下面三个条件的映射c：V（G）∪E（G）→{0,1,2…k},（1）.对任意的u,v∈V（G）,若uv∈E（G）,则c（u）≠c（v）；（2）.对任意的u,v,w∈V（G）,若uv,uw∈E（G）,则c（uv）≠c（uw）；（3）.对任意的u,v∈V（G）,若uv∈E（G）,则|c（u）-c（uv）|≥d.我们把这种映射称为图G的（d,1）-全标号.一个（d,1）-全标号的跨度是指最大标号数与最小标号数的差,图G的所有（d,1）-全标号中最小的跨度,称为图G的（d,1）-全标号数,记为λdT（G）.对于最大度为△的一个图G,图G在[0,q]上的一个（d,1）-全标号如果满足,对于任意的点v∈V（G）,其标号均在[0,△+d-1]内,则称此标号为一个d-优（d-good）标号,设p是图G的点集V（G）的一个剖分, V（G）=A∪B,A∪B=φ,其中边集E（G）＼（E（A）∪E（B））称为G的割,记为[A,B].图G的一个割边数目最多的割称为图G的最大割.目前,在文章[5]中对任意图G,猜想λdT（G）≤△+2d-1.这就是着名的全标号猜想.并且在[8]中证明了对任意的图G,λdT（G）≤2△+d-1,λ2T（G）≤6若△（G）≤3,λ2T（G）≤8若△（G）≤4.下面我们给出第二章的两个主要结论.定理2.5对任意的简单图G,最大度为Δ,如果Δ是偶的且Δ≥10,则λ2T（G）≤2Δ-1.定理2.6设图G是一个连通图且最大度为Δ,如果Δ（G）≤3且最大度点的邻点中至多有Δ-1个最大度点,则λdT（G）≤d+4.Hajo Broersma[6]曾经把古典的顶点标号进行变形,提出了图的干道限制染色（Backbone-染色）.即把原来图G上的限制只在图G的某一个主干道上加强.受此启示,本文在第三章中所要研究的L（d,1）-T标号是比L（d,1）-标号要求更松的一种限制.还是要求相邻的以及距离为2的基站频道必须不同,另外要求在图G的任意一棵支撑树T上相邻的基站频道至少差d.也就是只在图G的某个重要的干 道上我们要求的严格一些.这里我们以支撑树作为主要枢纽.对于任意连通图G,都有支撑树.所以我们引入以下定义：定义4给定一个简单连通图G及其一棵支撑树T,图G的一个L（d,1）-T标号是一个满足下面三个条件的映射c：V（G）→{0,1,2…k},（1）对任意的u,v∈V（G）,若d（u,v）=1,则|c（u）-c（v）|≥1；（2）对任意的u,v∈V（G）,若dT（u,v）=1,则|c（u）-c（v）|≥d；（3）对任意的u,v∈V（G）,若dG（u,v）=2,则|c（u）-c（v）|≥1.当所有的标号都小于等于k时,则称图G有一个k-L（d,1）-T标号.使得图G有一个k-L（d,1）-T标号的最小的正整数k称为图G的L（d,1）-T标号数,记为λd,T（G）.我们定义Tλd,T（G）：=maxT{λd,T（G）：G是一个图且T是图G的一棵支撑树}.若图G不含K1,3,则称图G是无爪图.设V（K1,n）={v0,v1,v2,…,vn}且Δ（v0）=n,则称v0为K1,n的一个控制点.设图G是一个简单图, V（G）={v1,v2,…,vn},G[I2]的点集和边集如下定义：V（G[I2]）={v1,v2,…,vn,v’1,v’2,…,v’n},E（G[I2]）=E（G）∪{v’iv’j,v’ivj,viv’j|vivj∈E（G）},则G[I2]称为G的点分裂图[7].在本文的第三章我们主要得到了以下结论.定理3.1.1对于任意的简单连通图G,其最大度为△,则Tλd,T（G）≤△2+2d-2.定理3.1.2设G是一个简单连通图,最大度为△,且图G的最大度点的邻点中至多有△-1个最大度点,则Tλd,T（G）≤△2+2d-3.引理3.1.3若图G是至少有一条边的简单图,则limd→∞（λd+1（G））/（λd（G））=1.定理3.1.4如果G是一个简单连通图,则limd→∞（Tλd+1,T（G））/（Tλ（?）（G））=1.定理3.2.2设G是无爪的连通图,则Tλd,T（G）≤3/4△2+2d+1/2△-2.定理3.2.3若G’为连通图G的点分裂图,△（G）=△,则Tλd,T（G’）≤2△2+2d+△-2.在本文第四章中研究的L’（d,1）-T标号是比L（d,1）-T标号要求更松的一种限制.还是要求相邻的基站频道必须不同,另外要求在图G的任意一棵支撑树T上相邻的基站频道至少差d且在T上距离为2的基站频道至少差1.也就是只在G的某个重要的干道上我们要求的严格一些.这里仍以支撑树作为主要枢纽.我们引入以下定义：定义5给定一个简单连通图G及其一棵支撑树T,图G的一个L’（d,1）-T标号是一个满足下面三个条件的映射c：V（G）→{0,1,2…k},（1）对任意的u,v∈V（G）,若d（u,v）=1,则|c（u）-c（v）|≥1；（2）对任意的u,v∈V（G）,若dT（u,v）=1,则|c（u）-c（v）|≥d；（3）对任意的u,v∈V（G）,若dT（u,v）=2,则|c（u）-c（v）|≥1.当所有的标号都小于等于k时,称图G有一个k-三L’（d,1）-T标号.则使得图G有一个k-L’（d,1）-T标号的最小的正整数k称为图G的L’（d,1）-T标号数,记为λ’d,T（G）.我们定义Tλ’d,T（G）:=maxT{λ’d,T（G）:G是一个图且T是图G的一棵支撑树}.在本文的第四章中我们给出了以下主要结论.定理4.1.1对于任意的简单连通图G,其最大度为△,则Tλ’d,T（G）≤2△+2d-3.定理4.1.2设G是一个简单连通图,最大度为△,且图G的最大度点的邻点中至多有△-2个最大度点,则Tλ’d,T（G）≤2△+2d-4.定理4.2.1对任意的简单连通图G,其最大度为△,则图G存在一棵支撑树T0,使得λ′d,T0（G）≤2△+2d-4.定理4.2.2如果G是一个简单连通图,则limd→∞（?）=1.定理4.2.3若G’为连通图G的点分裂图,△（G）=△,则G’存在一棵支撑树T0,使得λ’d,T0（G’）≤3△+2d-2.

二、关于图的L(d,1)-标号问题（论文开题报告）

（1）论文研究背景及目的

此处内容要求：

首先简单简介论文所研究问题的基本概念和背景，再而简单明了地指出论文所要研究解决的具体问题，并提出你的论文准备的观点或解决方法。

写法范例：

本文主要提出一款精简64位RISC处理器存储管理单元结构并详细分析其设计过程。在该MMU结构中,TLB采用叁个分离的TLB,TLB采用基于内容查找的相联存储器并行查找,支持粗粒度为64KB和细粒度为4KB两种页面大小,采用多级分层页表结构映射地址空间,并详细论述了四级页表转换过程,TLB结构组织等。该MMU结构将作为该处理器存储系统实现的一个重要组成部分。

（2）本文研究方法

调查法：该方法是有目的、有系统的搜集有关研究对象的具体信息。

观察法：用自己的感官和辅助工具直接观察研究对象从而得到有关信息。

实验法：通过主支变革、控制研究对象来发现与确认事物间的因果关系。

文献研究法：通过调查文献来获得资料，从而全面的、正确的了解掌握研究方法。

实证研究法：依据现有的科学理论和实践的需要提出设计。

定性分析法：对研究对象进行“质”的方面的研究，这个方法需要计算的数据较少。

定量分析法：通过具体的数字，使人们对研究对象的认识进一步精确化。

跨学科研究法：运用多学科的理论、方法和成果从整体上对某一课题进行研究。

功能分析法：这是社会科学用来分析社会现象的一种方法，从某一功能出发研究多个方面的影响。

模拟法：通过创设一个与原型相似的模型来间接研究原型某种特性的一种形容方法。

三、关于图的L(d,1)-标号问题（论文提纲范文）

（2）随机图的L（2,1）-标号算法及其在频率分配中的研究（论文提纲范文）

（4）几类图的L（1，d）-标号（论文提纲范文）

（6）手镯图的L（2,1）—标号（论文提纲范文）

（7）Cartesian积的局部边-路替换图的L（2,1）-标号（论文提纲范文）

（8）图的放松的距离二标号着色（论文提纲范文）

（9）图论中的距离标号理论及其在力学计算中的应用研究（论文提纲范文）

（10）与图的L（d，1）-标号相关的几种图标号问题（论文提纲范文）

四、关于图的L(d,1)-标号问题（论文参考文献）

• [1]竖梯的局部替换图的L（1,1,1）-标号[J]. 刘跃芹,洪雷,王惟帝,吕大梅. 高师理科学刊, 2021(10)
• [2]随机图的L（2,1）-标号算法及其在频率分配中的研究[D]. 孙帅. 兰州交通大学, 2021
• [3]路圈Cartesian积的局部替换图的L（1,1,1）-标号[J]. 李俊峰,洪雷,王惟帝,邢诗豪,张易安,吕大梅. 高师理科学刊, 2021(02)
• [4]几类图的L（1，d）-标号[D]. 刘乐. 天津职业技术师范大学, 2020(06)
• [5]点接拟梯子的L（d,1,1）-标号[J]. 李亚男,吴钰莉,蔡雨,吕大梅. 高师理科学刊, 2020(04)
• [6]手镯图的L（2,1）—标号[J]. 李海萍,杨英. 河北科技大学学报, 2018(04)
• [7]Cartesian积的局部边-路替换图的L（2,1）-标号[J]. 杜娟,吕大梅,张科. 浙江大学学报(理学版), 2016(06)
• [8]图的放松的距离二标号着色[D]. 戴本球. 东南大学, 2015(06)
• [9]图论中的距离标号理论及其在力学计算中的应用研究[D]. 段滋明. 中国矿业大学, 2011(08)
• [10]与图的L（d，1）-标号相关的几种图标号问题[D]. 王慧娟. 山东师范大学, 2010(04)

标签：图论算法论文;  简单图论文;  网格系统论文;  组合数学论文;