Conditions for coverings to induce matroids

摘要

Coverings are a useful form of data structure, and covering-based rough sets provide an effective tool to cope with this type of data. However, many important problems such as covering reduction in covering-based rough sets are NP-hard, so that most algorithms to solve them are greedy ones. Matroids, as a generalization of the linear independence in vector spaces, provide well-established platforms for greedy algorithms. Therefore, it is necessary to integrate covering-based rough sets and matroids. In this paper, we present conditions for coverings to induce matroids. Firstly, some conditions under which the minimal set of a covering satisfies the circuit axiom of matroids are presented through three sides, which are coverings, matroids and neighborhoods, then a matroid is induced by the covering. Secondly, two conditions under which two different coverings can induce the same matroid are studied. Finally, two sufficient and necessary conditions for a neighborhood covering to induce an Eulerian matroid are investigated, where the neighborhood covering is a family of all neighborhoods. In a word, these results show an interesting view to investigate the combination between covering-based rough sets and matroids.