论文摘要
连通图G中两个顶点x和y之间的距离定义为这两点之间最短路的长度.对于图G的一个有序顶点集合R={r1,r2,...,rk},顶点x∈G关于图G的表征定义为一个k-维向量cr（x）=（d（x,r1）,d（x,r2）,..,d（x,rk））.若G的不同顶点具有不同的表征,则称集合R是G的分辨集.包含最小顶点数的分辨集称为G的一个基.基的维数d（G）定义为基中包含的顶点个数,通常表示为β（G）。若对每一个x∈R,Rx仍是G的一个分辨集,则分辨集R称为容错的且G的容错度量维数为G的容错分辨集的基数。容错分辨集是一个删除任意顶点保持可分辨性的分辨集.图G的容错度量维数表示容错分辨集的最小基数,记作β’（G）.具有基数β’（G）的容错分辨集称为容错度量基.度量维数的概念是在1953年引入的,但最初未能吸引许多研究者的注意,但二十年后,它被用于观察图G的顶点之间的距离.从那时起,它已被经常地用于不同的领域如化学、图论、机器人学和许多其他已知学科.由于在区分图的不同顶点问题时可能出现的各种情况,在过去的几十年里已经研究了几个度量维数的概念。Hernando等独立提出了另一个概念,容错可分辨性,它可以容许任意顶点的移除并保持基础图的可分辨状态不变.当分辨集中的顶点被认为是一些声纳站的位置时,在这种情况下,我们可以提出图中任何这样的顶点的位置由这些声呐站位置间的距离确定.从这个观点来看,即使忽略了在分辨集中顶点的唯一确定位置处的任何站点,容错分辨集仍然确定分辨集.容错分辨集提高了图中经典分辨集的相关性.此外,容错度量维数相比度量维数在应用上更具有优势.在第1章中,我们给出了背景和一些定义,这些定义有助于以更好的方式理解概念,并且我们给出了后续章节中使用的重要定理和引理.在第2章中,我们研究凸多面体的容错度量维数问题.凸多面体是多面体同时也是n维欧几里德空间Rn中的凸点集.通过保持凸多面体的顶点之间的相同邻接关系,它的图也就被构造出来了.对于凸多面体和其他类图,度量维数问题已经被广泛研究.通过利用图的分辨集和容错分辨集之间的关系,可以证明某些无限族凸多面体是具有恒定容错度量维数的图类.在第3章中,我们考虑了图中的容错分辨集.我们已经刻画了具有容错度量维数n,n-1和2的n-顶点图,它们是较低和较高的极端情形.此外,在第一部分中,提出了一种定位方法,通过在图中使用经典分辨集来定位容错分辨集.在第二部分中我们将所提出的方法应用于三个无限族的正则图,并定位某些容错分辨集.通过搜集所获得的结果和文献中的一些已知结果,在本章中,我们给出了一些图类的容错度量维数的某些下界和上界,同时证明了这些图类保持恒定的容错分辨结构.在第4章中,我们讨论了度量维数和容错度量维数在电信,机器人导航和地理路由中具有潜在的应用等.这些问题的计算复杂性都是NP完全的.在本章中,我们研究了各种连接网络中的容错度量维数.通过在这些网络中使用分辨集,我们在其中找到容错分辨集,进而获得了这些网络的容错度量维数的某些下界和上界.在第5章中,我们用了一种不同以往的方法研究了旋转对称的凸多面体图的二元定位控制数问题.通过保持顶点间的邻接关系,凸多边形的图便可有凸多边形的几何结构来获得.在这一章当中,我们提出了一种用于图的二元控制定位问题的整数线性规划公式.我们已经确定了两个无限凸多面体族的二元定位控制数的精确值。对于两个旋转对称的凸多面体类,也获得了二元定位控制数的精确值.此外,还确定了其他三个无限凸多面体族的二元定位控制数的某些上界.通过使用所提出的整数线性规划公式,我们证明了上界是紧的.在第六章中,我们给出了本论文的结论,并且提出了我们在研究过程中一些未解决的问题.这些未解决的问题可以在未来的研究中进一步探索。
论文目录
文章来源
类型: 博士论文
作者: Hassan Raza
导师: 潘向峰
关键词: 可分辨性,容错可分辨性,可辨集,度量维数,距离,二元定位控制
来源: 安徽大学
年度: 2019
分类: 基础科学
专业: 数学
单位: 安徽大学
分类号: O157.5
总页数: 127
文件大小: 5985K
下载量: 25