网格图的2-彩虹控制数

给定一个图G和正整数k,图的彩虹控制函数f是满足下列条件的映射f:V(G)→2{1,2,…,k},使得对某个顶点v满足f(v)=,则∪u∈N(v)f(u)={1,2,…,k},其中V(G)是图G的顶点集,N(v)表示所有与v相邻的顶点的集合.彩虹控制函数f的权定义为w(f)=∑v∈V(G)|f(v)|.图的k-彩虹控制数γrk(G)是所有彩虹控制函数的权中的最小权.研究了2-彩虹控制函数的启发式算法的网格图的构造方法,实验结果表明,基于禁忌搜索策略的模拟退火算法比传统的模拟退火算法具有较好的效果.

Study on 2-rainbow Domination Numbers of Grid Graphs

Given a graph G and a set of K colors, we assign an arbitrary subset of these colors to each ver- tex of G. If we require that each vertex to which an empty set is assigned has all K colors in its neighbor- hood, then this assignment is called the K-rainbow dominating function of the graph G. The corresponding invariant ）% （G）, which is the minimum sum of numbers of assigned colors over all vertices of G, is called the K-rainbow domination number of G. In this paper,a simulated annealing algorithm with a tabu search scheme is proposed to solve the 2-rainbow domination numbers of grid graphs. It is compared with the stan- dard simulated annealing algorithm. The experimental results show that the proposed approach can obtain solutions with higher quality than those from the standard simulated annealing algorithm.