论文部分内容阅读
近年来,图的支配理论已经成为图论最重要研究领域之一.一些学者发现无线网络的关键技术之一虚拟骨干网技术,和图的连通支配集有密切的关系.从那以后,支配集在研究无线网络技术中占有重要的地位. 图的[ j,k]-集的概念由Chellai等人在2013年提出.研究 j不小于1的[ j,k]-集的目的,来源于研究中需要一类特殊的支配集,例如,作为计算机网络中的服务器集合,或作为需要监控场合的监控设备集合,不仅要求它们能够有效地工作,而且要求它们能花费尽可能小的代价有效地工作,换句话说,不要有太多的冗余设备. 在本文中,我们主要研究图的[1,2]-集和连通[1,2]-集的性质和算法.图G的一个支配集S被称为[1,2]-集,如果对图G的任意顶点v,满足v∈ V(G)S,1≤|N(v)∩S|≤2.我们称图的G的元素最少的[1,2]-集的元素个数为[1,2]-支配数,简称[1,2]-数.如果图的[1,2]-集的导出子图是连通的,那么称这个[1,2]-集是图G的连通[1,2]-集. 首先,我们考虑满足γ(G)=γ[1,2](G)的图并给出这样的一些图类蜘蛛图和广义Petersen图P(n,1). 其次,我们研究了[1,2]-集和连通[1,2]-集之间的关系.我们研究了满足连通支配集和连通[1,2]-集相等γc(G)=γc[1,2](G)或连通[1,2]-集等于顶点数n,即γc[1,2](G)=n的一些图的结构性质,并证明了二分图的最小连通[1,2]-集问题是一个NPC问题. 最后,我们考虑了图[1,2]-数的算法问题.基于0-1规划,我们设计了一个计算图的精确[1,2]-数的算法.作为一个例子,我们用这个算法计算了一些随机生成树的[1,2]-数.但是这个算法的计算复杂度是指数阶的.因此,我们设计了两个基于贪婪策略的近似算法,来计算树的[1,2]-数的近似值,并且比较了这些算法的性能.