顶点序下图的支配集算法

Dominating Set Algorithm for Graphs Based on Vertex Order

文中将粗糙集理论中的属性序引入到图论中,研究顶点序下图的支配集问题。首先,在图的顶点集上定义一个全序关系,称为顶点序。然后,利用顶点序定义一个二元等价关系,得到图中所有顶点闭邻接集的一个划分。最后,基于该划分设计了一种顶点序下图的极小支配集算法。同时,证明了该算法在给定顶点序下求解极小支配集的完备性和唯一性,并通过实例分析验证了所提算法的正确性和有效性。

This paper introduces the attribute order in rough set theory into graph theory,and studies the dominating set problem of undirected graphs based on vertex order.First,a total order relation is defined on the vertex set of graph,which is called vertex order.Then,a binary equivalence relation is defined by using the vertex order,and a partition of closed sets of all vertices in graph is obtained.Finally,based on the partition,a minimal dominating set algorithm for graphs under vertex order is designed.At the same time,it proves the completeness and uniqueness of this algorithm for solving the minimum dominating set under a given vertex order.An example is used to show the correctness and effectiveness of the algorithm.