论文摘要
控制集是图论中的重要概念,它定义为图中的一个点集,使得图中其它任何一点都与该点集中的某点相邻.这一概念的提出始于Konig、Berge和Ore,他们的著作和Cockayne, Hedetniemi,以及Larskar和Walikar等人的文章为后来的研究者提供了有益的启示.在过去的30多年里,对图的各类控制集参数问题以及控制参数与图的其他参数的关系问题的研究已经成为图论研究的一个重要领域.在此期间,各种新的控制参数被不断提出,如具有“连通性”的控制集,具有“距离控制性”的控制集,具有“无赘性”的控制集等等,本文在连通控制集和距离控制集的基础上引入一种新的控制集–“[r,R]-控制集”,并从算法的角度来讨论它的性质.如何寻找图的最小控制集是一个NP困难问题,它不能通过回溯法或随机化算法有效地解决,在这种情况下,对于其中的一些问题,代之以设计近似算法,我们要保证它是一个多项式时间算法,并且能得到一个近似于最优解的“合理”的解.对于最小化问题,算法的近似解与最优解的比值称为算法的近似比.近似比与1越靠近,算法所得的解就与最优解越接近.遗憾的是,并不是所有问题都能找到近似比为常数的近似算法,比如,已经证明:在P = NP的前提下,最小控制集问题就不可能找到比O（lnn）更好的算法.在本文第二章中,我们首先引入了[r,R]-控制集的准确定义,然后对一般图中的最小[r,R]-控制集问题提出了一个近似比为lnΔr + [（2r+1）/R]-1的算法,这已经与O（lnn）同阶,可以认为,在一般图中,其改进的余地已经很小.然后我们分别考虑图的[r,R]-控制数与图的大小的关系、图的[r,R]-控制数与其补图的[r,R]-控制数的关系、图的[r,R]-控制集与全控制集的关系,得到了图的[r,R]-控制数的三个不同上界.在第三章,我们从实际应用出发,将最小[r,R]-控制集限定在单位圆盘图中,考虑单位圆盘图中的特殊几何结构,得到了近似比为[4r（r + 1）(1 - （2θ-sin（2θ）/π）][（r+1）/R]（常数）的算法,其中θ= arccos 2rR+1.在r,R取特殊参数的情况下,对算法的近似比进行了更细致的刻划.在第四章,我们将最小[r,R]-控制集限定在随机正则图中,利用极大独立集给出了一个随机算法,并通过微分方程的方法分析了算法的返回值,进而得到了正则图中最小[r,R]-控制集的渐近界,并且证明,在r足够大的时候,最小[r,r + 1]-控制集的渐近界不超过d d/(（d - 2）（d - 1）d/（d-2）.在对随机算法进行分析的过程中,我们指出了一篇主要参考文献在数据处理上的错误.最后,我们给出对未来工作的展望作为结尾.
论文目录
相关论文文献
标签：近似算法论文; 图论论文; 控制集论文; 连通控制集论文; 弱连通控制集论文; 单位圆盘图论文; 随机正则图论文;