检索结果-南通市图书馆

最大度至多为6的平面图的L(2,1)-标号

引用

应用数学 2012年第2期25卷 237-245页

作者：朱海洋吕新忠陈伟侯立峰徐州空军学院后勤指挥系江苏徐州221000 浙江师范大学数理与信息工程学院浙江金华321004

令Δ(G),g(G)和λ(G)分别为图G的最大度,围长,和L(2,1)-标号数.证明了若G是Δ(G)≤6和g(G)≥5的平面图,则λ(G)≤Δ(G)+13.进而关于Δ(G)≤6和g(G)≥5的平面图G,这个界要比先前的结果好.

关键词：平面图 L(2 1)-标号标号数围长

来源：

维普期刊数据库

同方期刊数据库评论

在线全文

学校读者我要写书评

暂无评论

随机图的L(2,1)-标号混合人工蜂群算法

引用

武汉大学学报（理学版） 2021年第2期67卷 158-164页

作者：孙帅李敬文袁清厚兰州交通大学电子与信息工程学院甘肃兰州730070

为解决图的L(2,1)-标号问题,设计了一种全新的标号算法,该算法利用人工蜂群全局搜索能力强的优点来得到最优的L(2,1)-标号方案。为了加快算法的收敛速度,修改了部分搜索策略并采用改进后的CK算法对初始蜜源进行限制。实验结果表明,该算... 详细信息

为解决图的L(2,1)-标号问题,设计了一种全新的标号算法,该算法利用人工蜂群全局搜索能力强的优点来得到最优的L(2,1)-标号方案。为了加快算法的收敛速度,修改了部分搜索策略并采用改进后的CK算法对初始蜜源进行限制。实验结果表明,该算法可以有效地求解有限点内随机图的L(2,1)-标号且10个点内的简单连通图都满足Griggs的猜想。通过分析实验结果总结出有关K_(n)\e、K_(n)\2e、联图K_(n)↑S_(m)以及太阳图等的相关定理,并结合已有结果给出了新的猜想。

关键词： L(2 1)-标号标号数人工蜂群算法组合优化

来源：

维普期刊数据库

同方期刊数据库评论

在线全文

学校读者我要写书评

暂无评论

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

随机图的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）-标号理论及算法,设计频率分配仿真实验,说明其可行性和应用价值。

关键词： L(2,1)-标号标号数标号算法频率分配

来源：

同方学位论文库评论