Journal of Applied Mathematics
Volume 2013 (2013), Article ID 519173, 7 pages
http://dx.doi.org/10.1155/2013/519173
Research Article

Equivalent Characterizations of Some Graph Problems by Covering-Based Rough Sets

Shiping Wang,1 Qingxin Zhu,1 William Zhu,2 and Fan Min2

1School of Computer Science and Engineering, University of Electronic Science and Technology of China, Chengdu 611731, China
2Lab of Granular Computing, Minnan Normal University, Zhangzhou, Fujian 363000, China

Received 4 January 2013; Accepted 30 April 2013

Academic Editor: Hector Pomares

Copyright © 2013 Shiping Wang et al. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

Abstract

Covering is a widely used form of data structures. Covering-based rough set theory provides a systematic approach to this data. In this paper, graphs are connected with covering-based rough sets. Specifically, we convert some important concepts in graph theory including vertex covers, independent sets, edge covers, and matchings to ones in covering-based rough sets. At the same time, corresponding problems in graphs are also transformed into ones in covering-based rough sets. For example, finding a minimal edge cover of a graph is translated into finding a minimal general reduct of a covering. The main contributions of this paper are threefold. First, any graph is converted to a covering. Two graphs induce the same covering if and only if they are isomorphic. Second, some new concepts are defined in covering-based rough sets to correspond with ones in graph theory. The upper approximation number is essential to describe these concepts. Finally, from a new viewpoint of covering-based rough sets, the general reduct is defined, and its equivalent characterization for the edge cover is presented. These results show the potential for the connection between covering-based rough sets and graphs.