图支配集问题的粗糙集属性约简方法

An Attribute Reduction Method Based on Rough Sets for Dominating Sets of Graph

探讨粗糙集的属性约简和图的支配集问题之间的联系.通过构造信息系统,将粗糙集的属性约简问题与图的支配集问题相联系,从而把图的支配集问题转化为粗糙集的属性约简问题.首先证明图的极小支配集恰是其构造的信息系统的属性约简,然后提出一种基于信息熵的最小支配集算法,最后通过实例验证该算法的可行性和有效性.

The relationship between attribute reduction problem in rough sets and dominating set problem in graph is discussed. By constructing an information system, the attribute reduction problem in rough sets is associated with the dominating set problem in graph, so as to transformed the dominating set problem into the attribute reduction problem. Firstly, it is proved that the minimal dominating set of a graph is exactly the attribute reduction of the constructed information system. Then, a minimum dominating set algorithm based on information entropy is proposed. Finally, A practical example illustrates the feasibility and efficiency of the proposed algorithm.