论文部分内容阅读
在过去的三十多年里,随着计算机科学的迅速发展,图论也得到了飞速发展,而图论中发展最快的领域也许就是控制数理论的研究.控制数理论能够快速发展的主要原因是它在现实世界中,例如编码理论、计算机科学、通信网络、监视系统和社会网络等理论与实践中有着广泛而深刻的应用背景.
设图G=(V(G),E(G))为简单无向图,V(G)和E(G)分别为图G的顶点集和边集.设D()V(G),若V(G)D中的每一个点至少与D的某一个顶点相邻接,也即N[D]=V(G),则称D为G的控制集.1998年,Haynes和Slater基于某类应用背景提出了配对控制集的概念.2000年,Hedetniemi,Hedetniemi和Rall提出了图的无圈控制集问题.集S()V称为G的配对控制集(无圈控制集),如果S是G的控制集且导出子图存在完美匹配(不含有圈).
控制相关参数的算法复杂性问题作为控制数理论研究中的一个重要领域,受到了越来越多的研究人员的关注.不过,对于任意图,几乎所有的控制相关参数问题均是NP-完全的.即使一个问题被证明是NP-完全的,人们仍然有可能得到此问题的特定实例的多项式算法.(例如,对于任意图具有NP-完全性的控制数问题已经被证明在树、区间图、AT-free图上是多项式可解的.)本文主要研究了两类新型控制参数(配对控制数和无圈控制数)在特殊图类的算法复杂性问题,主要工作分为两个部分:
第一部分,由于任意图的配对控制集问题具有NP-完全性,作者考虑了AT-free图类.在研究了AT-free图类的结构性质的基础上,给出了配对控制集在AT-free图的BFS-树上分布的结构性质.利用这些性质,给出了求解AT-free图类最小配对控制集的多项式时间算法.
第二部分,针对文[41]中提出的一些公开问题,同时在注意到无圈控制集问题对于二部图都是NP-完全的这一事实基础上,研究了二部图的一个子类二部置换图的无圈控制集问题.当限定在二部置换图上时,证明了无圈控制数等于其控制数(γa(G)=γ(G)).利用此结论给出了二部置换图的无圈控制集问题的线性时间求解算法.