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