李有浩,赵承业,董合德

(中国计量大学 理学院,浙江 杭州 310018)

图的支配问题在图的相关研究中一直是一个很热门的分支,因为其具有很多的变形和实际的相关应用,从理论到算法[1-2],各种论点层出不穷.而连通支配集[3]就是图支配的一个重要分支问题.定义集合C⊆V(G),G(C)是集合C在图G=(V,E)中的生成子图,N(v)表示顶点v所有邻居节点,N[v]=N(v)∪{v}如果满足1)|N[v]∩C|≥1,∀v∈V(G),2)G(C)是连通的,那么就称集合C是图G的连通支配集.相关的研究也有很多,如文献[4,5].

误报容错支配集是图的支配问题的一个新的有趣的延伸[6-10],从容错的角度来看,其实是介于图的2-tuple支配和3-tuple支配之间的一个图的支配问题.这个问题最早是由Slater在2009年提出的[7],其实际意义可以对应社交网络中如下的一种情况.

我们对于一般的社交网络可以用图G=(V,E)来表示,图G中的每一个点代表一个社交个体,如果两个个体之间可以相互交换信息的话,那么就给这两个个体所对应的图G中的点连上一条边.这里假设图G中的每一个点都可能是一个入侵节点,例如一个着火点或是一个破坏者等等.假设存在这样的入侵者点v′.网络中还存在具有保护装置的点,它可以检测出其邻居节点是否是入侵节点,并且汇报这一入侵点的位置.要求尽可能布置最少的保护节点,而且还能准确找到网络中的入侵节点.这在网络的拓扑图中,相当于找到最小的满足条件的支配集D,在D中所有的点布置保护装置.然而这样的保护装置可能会损坏而不会汇报信息……