论文摘要
图论是研究离散系统结构的一门学科分支,图的标号问题是图论中重要的研究领域之一,其在科学技术和工程领域中有广泛的应用。图的距离标号问题是近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篇。
论文目录
相关论文文献
- [1].有向图的距离标号边跨度[J]. 数学研究 2013(04)
- [2].全维视觉机器人距离标定方法[J]. 机电工程 2008(01)
- [3].龙虾树的多级距离标号[J]. 应用数学学报 2011(05)
- [4].一类特殊毛毛虫的多级距离数[J]. 山东大学学报(理学版) 2009(04)
- [5].一类特殊对称毛毛虫的多级距离数[J]. 天津师范大学学报(自然科学版) 2010(02)
- [6].基于标定场的激光雷达两步标定方法[J]. 空间控制技术与应用 2017(04)
- [7].立方路的多级距离数[J]. 西北师范大学学报(自然科学版) 2015(02)
- [8].关于根点对称的二元树的多级距离标号[J]. 天津师范大学学报(自然科学版) 2011(03)
- [9].基于BAW微波延迟线的雷达距离标定模块研制[J]. 压电与声光 2016(04)