路和圈的定位控制集问题

论文摘要

令G表示一个图,V和E分别表示它的点集和边集,r是一给定的正整数.定义Nr[x]={y∈V（G）:d（x,y）≤r},其中d（x,y）表示x和y在图G上的距离.对于V的任何一个子集D,令Dr（x）=N,[x]∩D.如果对于任何x∈VD, Dr（x）是非空的,则D是一个r-控制集.当r=1时,D就是图G的控制集.图的控制集理论在组合优化,编码理论,计算机科学,通信网络,监视系统和社会网络等领域有着重要的应用,它已经成为近几十年来图论中发展最快的领域之一.随着研究的深入,各种新的控制参数不断涌现,其中图的定位控制集就是在其基础上被提出来的.图的定位控制集已经成为编码理论中较活跃的研究方向,它在通讯网络和监视系统中有广泛的应用.如果在控制集的基础上加入一定限制,对于任何x∈VD, Dr（x）是非空的并且互不相同,则D是一个定位控制集.令MrLD（G）表示G中最小定位控制集中的点数.对于图G,找出它的最小定位控制集是十分困难的,即便是最简单的路和圈.当r=1和2时,路和圈的定位控制集问题已解决.本文主要讨论r=3时,路和圈的定位控制集问题,给出了完整的结果.同时,对任意r≥2,本文给出了路和圈的MrLD（G）的新上界.另外,对于路和圈组成的气球图的定位控制集本文也进行了讨论.

论文目录

• 摘要
• ABSTRACT
• 第一章 引言
• 1.1 研究背景和基本概念
• 1.2 研究现状
• 第二章 路和圈的3-LDS
• 第三章 关于r-LDS的界
• 第四章 气球图的2-LDS
• 第五章 总结
• 参考文献
• 致谢