# Covering-Based Rough Sets on Eulerian Matroids

Authors: Bin Yang; Ziqiong Lin; William Zhu
Journal: Journal of Applied Mathematics
 (2013)

---

## Abstract

Rough set theory is an efficient and essential tool for dealing with vagueness and granularity in information systems. Covering-based rough set theory is proposed as a significant generalization of classical rough sets. Matroid theory is a vital structure with high applicability and borrows extensively from linear algebra and graph theory. In this paper, one type of covering-based approximations is studied from the viewpoint of Eulerian matroids. First, we explore the circuits of an Eulerian matroid from the perspective of coverings. Second, this type of covering-based approximations is represented by the circuits of Eulerian matroids. Moreover, the conditions under which the covering-based upper approximation operator is the closure operator of a matroid are presented. Finally, a matroidal structure of covering-based rough sets is constructed. These results show many potential connections between covering-based rough sets and matroids.


---

## Body

## 1. Introduction

Various theories and methods have been proposed to deal with incomplete and insufficient information in classification, concept formation, and data analysis in data mining. For example, fuzzy set theory [1–3], rough set theory [4, 5], computing with words [6, 7], and linguistic dynamic systems [8] have been developed and applied to real-world problems. Classical rough sets were originally proposed by Pawlak as a useful tool for dealing with the fuzzy and uncertain problems in information systems and have already been an efficient tool for data pre-process and widely used in fields such as process control, economics, medical diagnosis, conflict analysis, and other fields [9–12]. Covering-based rough set has been proposed as a generalization of classical rough set and the study on it is necessary and important. Particularly, with the fast development of computer science and technology in recent years, how to use the effective mathematical tools to solve practical problems has become more and more essential. Of course, as an efficient tool, the study on covering-based rough sets is fetching in more and more researchers. Zhu [12] investigated some basic properties of covering-based rough sets and their comparisons with the corresponding ones of classical rough sets. Zhang et al. [10] investigated three types of covering-based rough sets with an axiomatic approach. In addition, some detailed works of covering-based rough sets can be found in the literatures [13–17]. Therefore, there is profound theoretical and practical significance to study the covering-based rough sets.The concept of matroids was originally introduced by Whitney [18] in 1935 as a generalization of graph theory and linear algebra. Matroid theory is a structure that generalizes linear independence in vector spaces and has a variety of applications in many fields such as algorithm design [19] and combinatorial optimization [20]. In theory, matroid theory provides a good platform to connect it with other theories. Some interesting results about the connection between matroid theory and rough set theory can be found in the literatures [21–25].In this paper, through Eulerian matroids, one type of covering-based approximation operators is represented through the perspective of Eulerian matroids. First, since the family of circuits of an Eulerian matroid is a covering, then the properties, such as irreducible, semireduced, and minimal description, are investigated from the viewpoint of coverings. Second, the second type of covering-based upper and lower approximation operators is represented by the circuits of the Eulerian matroid. In fact, some types of covering-based lower approximation operators are equal, and they can be represented by the circuits of the restriction matroids of Eulerian matroids. Moreover, we obtain the condition under which the covering-based upper approximation operator is the closure operator of a matroid. Finally, a matroidal structure of covering-based rough sets is constructed by a type of covering with some special properties.The remainder of this paper is organized as follows. In Section2, some basic concepts and properties related to covering-based rough sets and matroids are introduced. In Section 3, some properties of the covering induced by an Eulerian matroid are investigated. Moreover, the focus here is the covering-based approximation operators denoted by the circuits of Eulerian matroids. In Section 4, a matroidal structure of covering-based rough sets is constructed by a type of covering with some special properties. Section 5 concludes this paper.


## 2. Preliminaries

In this section, we review some fundamental definitions and results of covering-based rough sets and matroids.


### 2.1. Covering-Based Rough Sets

In this subsection, we recall some basic definitions and results of covering-based rough sets used in this paper. For detailed descriptions about covering-based rough sets, please refer to [9, 11, 12, 26].Definition 1 (covering [11]).
LetU be a universe of discourse, C a family of subsets of U. If none of subsets in C is empty, and ⋃‍C=U, then C is called a covering of  U.It is clear that a partition ofU is certainly a covering of  U, so the concept of a covering is an extension of the concept of a partition. In the following discussion, the universe of discourse U is considered to be finite.Definition 2 (covering-based approximation space [11]).
LetU be a universe of discourse and C a covering of U. The ordered pair 〈U,C〉 is called a covering-based approximation space.Definition 3 (minimal description [11]).
Letting〈U,C〉 be a covering-based approximation space, x∈U, then set family
(1)MdC(x)={K∈C∣x∈K∧(∀S∈C∧x∈S∧S⊆K⟹K=S)}
is called the minimal description of x.Definition 4 (unary covering [12]).
LetC be a covering of  U. C is called unary if  ∀x∈U,|MdC(x)|=1.Definition 5 (representative element [12]).
LetC be a covering of  U. If x∈K∈C satisfies the following condition:
(2)∀K′∈C(x∈K′⟹K⊆K′),
then x is called a representative element of K.Definition 6 (representative covering [12]).
LetC be a covering of  U. If ∀K∈C, K has a representative element, one says C is representative.Definition 7 (exact covering [12]).
LetC be a covering of  U. If ∀C′⊆C,
(3){K∈C∣K⊆⋃‍C′}={K∈C∣∃K′∈C′(K⊆K′)},
one says the covering C is exact.The following lemma shows that the concepts of representative and exact coverings are equivalent.Lemma 8 (see [12]).
LetC be a covering of  U. C is representative if and only if  C is exact.


### 2.2. Matroids

Matroid theory was established as a generalization of graph theory and linear algebra. This theory was used to study abstract relations on a subset, and it used both of these areas of mathematics for its motivation, its basic examples, and its notation. With the rapid development of matroid theory in recent years, it has already become an effective mathematical tool to study other mathematic branches. In this subsection, we recall some definitions, examples, and results of matroids.Definition 9 (matroid [27]).
A matroid is an ordered pairM=(U,ℐ), where U is a finite set and ℐ a family of subsets of U with the following three properties:(I1)
∅∈ℐ;(I2)
ifI∈ℐ, and I′⊆I, then I′∈ℐ;(I3)
ifI1, I2∈ℐ, and |I1|<|I2|, then there exists e∈I2-I1 such that I1⋃‍{e}∈ℐ, where |I| denotes the cardinality of I.Any element of ℐ is called an independent set.Example 10.
LetG=(V,U) be the graph as shown in Figure 1. Denote ℐ={I⊆U|IdoesnotcontainacycleofG}, that is, ℐ={∅,{a1},{a2},{a3},{a4},{a1,a2}, {a1,a3},{a1,a4},{a2,a3},{a2,a4},{a3,a4},{a1,a2,a4},{a1,a3,a4},{a2,a3,a4}}. Then M=(U,ℐ) is a matroid, where U={a1,a2,a3,a4}.Figure 1
A graph.In fact, if a subset is not an independent set, then it is a dependent set of the matroid. In other words, the dependent set of a matroid generalizes the cycle in graphs. Based on the dependent set, we introduce other concepts of a matroid. For this purpose, several denotations are presented in the following definition.Definition 11 (see [27]).
Let𝒜 be a family of subsets of  U. One can denoteMax(𝒜)={X∈𝒜|∀Y∈𝒜, X⊆Y⇒X=Y},Min(𝒜)={X∈𝒜|∀Y∈𝒜, Y⊆X⇒X=Y},Opp(𝒜)={X⊆U|X∉𝒜},Com(𝒜)={X⊆U|~X∈𝒜}, where ~X=U-X.Definition 12 (base [27]).
LetM=(U,ℐ) be a matroid. A maximal independent set in M is called a base of M, and one denotes the family of all bases of M by ℬ(M), that is, ℬ(M)=Max(ℐ).Example 13 (continued from Example10).
According to Definition12, we have ℬ(M)={{a1,a2,a4},{a1,a3,a4},{a2,a3,a4}}.A matroid and its bases are uniquely determined by each other. In other words, a matroid can also be defined from the viewpoint of the base.Theorem 14 (base axiom [27]).
Letℬ be a family of subsets of  U. Then there exists M=(U,ℐ) such that ℬ=ℬ(M) if and only if ℬ satisfies the following two conditions:(B1)
ℬ≠∅;(B2)
ifB1,B2∈ℬ and x∈B1-B2, then there exists y∈B2-B1 such that (B1-{x})⋃‍{y}∈ℬ.Definition 15 (circuit [27]).
LetM=(U,ℐ) be a matroid. A minimal dependent set in M is called a circuit of M, and one denotes the family of all circuits of M by 𝒞(M), that is,
(4)𝒞(M)=Min(Opp(ℐ)).Example 16 (continued from Example10).
According to Definition15, we have 𝒞(M)={{a1,a2,a3}}.Theorem 17 (circuit axiom [27]).
LetM=(U, ℐ) be a matroid and 𝒞=𝒞(M). Then 𝒞 satisfies the following three properties:(C1)
∅∉𝒞;(C2)
ifC1,C2∈𝒞 and C1⊆C2, then C1=C2;(C3)
ifC1,C2∈𝒞, C1≠C2 and e∈C1⋂‍C2, then there exists C3∈𝒞 such that C3⊆(C1⋃‍C2)-{e}.A matroid uniquely determines its circuits and vice versa. The following theorem shows that a matroid can be defined from the viewpoint of circuits.Theorem 18 (see [27]).
LetU be a nonempty and finite set and 𝒞 a family of subsets of  U. If 𝒞 satisfies (C1), (C2), and (C3) of Theorem 17, then there exists M=(U, ℐ) such that 𝒞=𝒞(M).Definition 19 (rank function [27]).
LetM=(U, ℐ) be a matroid. One can define the rank function of M as follows: for all X∈2U,
(5)rM(X)=max{|I|∣I⊆X,I∈ℐ}.rM(X) is calledthe rank of X in M.Based on the rank function of a matroid, one can define the closure operator, which reflects the dependency between a set and elements.Definition 20 (closure [27]).
LetM=(U,ℐ) be a matroid. The closure operator clM of M is defined as clM(X)={e∈U|rM(X⋃‍{e})=rM(X)} for all X∈2U. clM(X) is called the closure of X in M.


## 2.1. Covering-Based Rough Sets

In this subsection, we recall some basic definitions and results of covering-based rough sets used in this paper. For detailed descriptions about covering-based rough sets, please refer to [9, 11, 12, 26].Definition 1 (covering [11]).
LetU be a universe of discourse, C a family of subsets of U. If none of subsets in C is empty, and ⋃‍C=U, then C is called a covering of  U.It is clear that a partition ofU is certainly a covering of  U, so the concept of a covering is an extension of the concept of a partition. In the following discussion, the universe of discourse U is considered to be finite.Definition 2 (covering-based approximation space [11]).
LetU be a universe of discourse and C a covering of U. The ordered pair 〈U,C〉 is called a covering-based approximation space.Definition 3 (minimal description [11]).
Letting〈U,C〉 be a covering-based approximation space, x∈U, then set family
(1)MdC(x)={K∈C∣x∈K∧(∀S∈C∧x∈S∧S⊆K⟹K=S)}
is called the minimal description of x.Definition 4 (unary covering [12]).
LetC be a covering of  U. C is called unary if  ∀x∈U,|MdC(x)|=1.Definition 5 (representative element [12]).
LetC be a covering of  U. If x∈K∈C satisfies the following condition:
(2)∀K′∈C(x∈K′⟹K⊆K′),
then x is called a representative element of K.Definition 6 (representative covering [12]).
LetC be a covering of  U. If ∀K∈C, K has a representative element, one says C is representative.Definition 7 (exact covering [12]).
LetC be a covering of  U. If ∀C′⊆C,
(3){K∈C∣K⊆⋃‍C′}={K∈C∣∃K′∈C′(K⊆K′)},
one says the covering C is exact.The following lemma shows that the concepts of representative and exact coverings are equivalent.Lemma 8 (see [12]).
LetC be a covering of  U. C is representative if and only if  C is exact.


## 2.2. Matroids

Matroid theory was established as a generalization of graph theory and linear algebra. This theory was used to study abstract relations on a subset, and it used both of these areas of mathematics for its motivation, its basic examples, and its notation. With the rapid development of matroid theory in recent years, it has already become an effective mathematical tool to study other mathematic branches. In this subsection, we recall some definitions, examples, and results of matroids.Definition 9 (matroid [27]).
A matroid is an ordered pairM=(U,ℐ), where U is a finite set and ℐ a family of subsets of U with the following three properties:(I1)
∅∈ℐ;(I2)
ifI∈ℐ, and I′⊆I, then I′∈ℐ;(I3)
ifI1, I2∈ℐ, and |I1|<|I2|, then there exists e∈I2-I1 such that I1⋃‍{e}∈ℐ, where |I| denotes the cardinality of I.Any element of ℐ is called an independent set.Example 10.
LetG=(V,U) be the graph as shown in Figure 1. Denote ℐ={I⊆U|IdoesnotcontainacycleofG}, that is, ℐ={∅,{a1},{a2},{a3},{a4},{a1,a2}, {a1,a3},{a1,a4},{a2,a3},{a2,a4},{a3,a4},{a1,a2,a4},{a1,a3,a4},{a2,a3,a4}}. Then M=(U,ℐ) is a matroid, where U={a1,a2,a3,a4}.Figure 1
A graph.In fact, if a subset is not an independent set, then it is a dependent set of the matroid. In other words, the dependent set of a matroid generalizes the cycle in graphs. Based on the dependent set, we introduce other concepts of a matroid. For this purpose, several denotations are presented in the following definition.Definition 11 (see [27]).
Let𝒜 be a family of subsets of  U. One can denoteMax(𝒜)={X∈𝒜|∀Y∈𝒜, X⊆Y⇒X=Y},Min(𝒜)={X∈𝒜|∀Y∈𝒜, Y⊆X⇒X=Y},Opp(𝒜)={X⊆U|X∉𝒜},Com(𝒜)={X⊆U|~X∈𝒜}, where ~X=U-X.Definition 12 (base [27]).
LetM=(U,ℐ) be a matroid. A maximal independent set in M is called a base of M, and one denotes the family of all bases of M by ℬ(M), that is, ℬ(M)=Max(ℐ).Example 13 (continued from Example10).
According to Definition12, we have ℬ(M)={{a1,a2,a4},{a1,a3,a4},{a2,a3,a4}}.A matroid and its bases are uniquely determined by each other. In other words, a matroid can also be defined from the viewpoint of the base.Theorem 14 (base axiom [27]).
Letℬ be a family of subsets of  U. Then there exists M=(U,ℐ) such that ℬ=ℬ(M) if and only if ℬ satisfies the following two conditions:(B1)
ℬ≠∅;(B2)
ifB1,B2∈ℬ and x∈B1-B2, then there exists y∈B2-B1 such that (B1-{x})⋃‍{y}∈ℬ.Definition 15 (circuit [27]).
LetM=(U,ℐ) be a matroid. A minimal dependent set in M is called a circuit of M, and one denotes the family of all circuits of M by 𝒞(M), that is,
(4)𝒞(M)=Min(Opp(ℐ)).Example 16 (continued from Example10).
According to Definition15, we have 𝒞(M)={{a1,a2,a3}}.Theorem 17 (circuit axiom [27]).
LetM=(U, ℐ) be a matroid and 𝒞=𝒞(M). Then 𝒞 satisfies the following three properties:(C1)
∅∉𝒞;(C2)
ifC1,C2∈𝒞 and C1⊆C2, then C1=C2;(C3)
ifC1,C2∈𝒞, C1≠C2 and e∈C1⋂‍C2, then there exists C3∈𝒞 such that C3⊆(C1⋃‍C2)-{e}.A matroid uniquely determines its circuits and vice versa. The following theorem shows that a matroid can be defined from the viewpoint of circuits.Theorem 18 (see [27]).
LetU be a nonempty and finite set and 𝒞 a family of subsets of  U. If 𝒞 satisfies (C1), (C2), and (C3) of Theorem 17, then there exists M=(U, ℐ) such that 𝒞=𝒞(M).Definition 19 (rank function [27]).
LetM=(U, ℐ) be a matroid. One can define the rank function of M as follows: for all X∈2U,
(5)rM(X)=max{|I|∣I⊆X,I∈ℐ}.rM(X) is calledthe rank of X in M.Based on the rank function of a matroid, one can define the closure operator, which reflects the dependency between a set and elements.Definition 20 (closure [27]).
LetM=(U,ℐ) be a matroid. The closure operator clM of M is defined as clM(X)={e∈U|rM(X⋃‍{e})=rM(X)} for all X∈2U. clM(X) is called the closure of X in M.


## 3. Covering-Based Rough Sets on Eulerian Matroids

In this section, we provide equivalent formulations of some important concepts and properties of covering-based rough sets from the viewpoint of Eulerian matroids. Specifically, the covering-based upper and lower approximation operators are characterized by the circuits of matroids. For this purpose, some definitions and properties of the covering induced by an Eulerian matroid are presented.The following definition introduces Eulerian matroids, which is a special kind of matroids, and has sound theoretical foundations and wide applications.Definition 21 (Eulerian matroid [27]).
LetM=(U, ℐ) be a matroid. If there exist C1,C2,…,Cm∈𝒞(M) such that Ci⋂‍Cj=∅(i≠j,i,j=1,2,…,m) and U=⋃i=1mCi, then one says M is an Eulerian matroid.Example 22.
LetG=(V,U) be the graph as shown in Figure 2. Denote 𝒞={C⊆U|C does a cycle of G}, that is, 𝒞={{a1},{a2},{a5,a8},{a3,a4,a5},{a3,a4,a8},{a5,a6,a7},{a6,a7,a8},{a3,a4,a6,a7}}. Then there exists a matroid M=(U,ℐ) such that 𝒞=𝒞(M), where U={a1,a2,a3,a4,a5,a6,a7,a8}. Clearly, M is an Eulerian matroid.Figure 2
A graph.According to the above definition, it is clear that𝒞(M) is a covering of U. In other words, we construct a covering by an Eulerian matroid.Example 23 (continued from Example22).
It is easy to check that the set family𝒞={{a1},{a2},{a5,a8},{a3,a4,a5}, {a3,a4,a8},{a5,a6,a7},{a6,a7,a8},{a3,a4,a6,a7}} is a covering of U.Proposition 24.
LetM=(U,ℐ) be an Eulerian matroid and x∈U. Then
(6)Md𝒞(M)(x)={C∈𝒞(M)∣x∈C}.Proof.
It is obviousMd𝒞(M)(x)⊆{C∈𝒞(M)|x∈C}. Suppose Md𝒞(M)(x)≠{C∈𝒞(M)|x∈C}. Hence {C∈𝒞(M)|x∈C}-Md𝒞(M)(x)≠∅. Suppose K∈{C∈𝒞(M)|x∈C}-Md𝒞(M)(x). Then there exists L∈𝒞(M) such that x∈L and L⊂K. It is contradiction to (C2) of Theorem 17.Example 25 (continued from Example22).
We have(7)Md𝒞(M)(a1)={{a1}},Md𝒞(M)(a2)={{a2}},Md𝒞(M)(a5)={{a5,a8},{a3,a4,a5},{a5,a6,a7}},Md𝒞(M)(a8)={{a5,a8},{a3,a4,a8},{a6,a7,a8}},Md𝒞(M)(a3)={{a3,a4,a5},{a3,a4,a8},{a3,a4,a6,a7}}=Md𝒞(M)(a4),Md𝒞(M)(a6)={{a5,a6,a7},{a6,a7,a8},{a3,a4,a6,a7}}=Md𝒞(M)(a7).In fact, the concepts of unary covering, representative covering, and exact covering play a vital role in covering-based rough sets. Based on the properties of the Eulerian matroid and the above proposition, the following remark is presented.Remark 26.
IfM=(U,ℐ) is an Eulerian matroid, then 𝒞(M) is not a representative covering. In other words, 𝒞(M) is not an exact covering.Example 27 (continued from Example22).
It is easy to know𝒞={{a1},{a2},{a5,a8},{a3,a4,a5},{a3,a4,a8},{a5,a6,a7},{a6,a7,a8},{a3,a4,a6,a7}} is not a representative and exact covering of U.Proposition 28.
LetM=(U,ℐ) be an Eulerian matroid. Then 𝒞(M) is a unary covering if and only if 𝒞(M) is a partition of  U.Proof.
(⇒): Let 𝒞(M) be a unary covering of U and x∈U. Then |Md𝒞(M)(x)|=1. If 𝒞(M) is not a partition of U, then there exists x∈U such that there exist C1,C2∈𝒞(M), C1≠C2 and x∈C1⋂‍C2, that is, |Md𝒞(M)(x)|≥2. It is contradictory.
(⇐): It is straightforward.Example 29 (continued from Example22).
Clearly, according to Proposition28, since 𝒞(M)={{a1},{a2},{a5,a8},{a3,a4,a5},{a3,a4,a8},{a5,a6,a7},{a6,a7,a8},{a3,a4,a6,a7}} is not a partition of  U, then 𝒞(M) is not a unary covering of  U.In covering-based rough sets, a pair of covering-based approximation operators are used to describe an object. In the following definition, a widely used pair of covering-based approximation operators are introduced.Definition 30 (covering-based approximation set family [12]).
LetC be a covering of  U. For any set X⊆U, set families
(8)C_(X)={K∈C∣K⊆X},C¯(X)={K∈C∣K⋂‍X≠∅}
are called the covering-based lower and upper approximation set families of X, respectively.Definition 31 (covering-based approximation operator [12]).
LetC be a covering of  U. For any set X⊆U,
(9)X_=⋃‍C_(X),X¯=⋃‍C¯(X)
are called the covering-based lower and upper approximations of X, respectively.Definition 32 (restriction matroid [27]).
LetM=(U,ℐ) be a matroid and X⊆U. Suppose ℐX={I⊆X|I∈ℐ}. Then (X,ℐX) is a matroid and called the restriction matroid of X in M. One denotes the restriction matroid of X in M as M|X, that is, M|X=(X,ℐX).In the following proposition, a widely used pair of covering-based approximation operators are represented by the circuits of Eulerian matroids.Proposition 33.
LetM=(U,ℐ) be an Eulerian matroid and X⊆U. Then
(10)𝒞(M)_(X)=𝒞(M∣X),𝒞(M)¯(X)={C∈𝒞(M)∣C⋂‍X≠∅}.Proof.
Let𝒞1={C∈𝒞(M)|C⊆X}. According to Definition 30, we need to prove only 𝒞1=𝒞(M|X). On one hand, for any C∈𝒞1, we have C⊆X and C∉ℐX. Since C∈𝒞(M), then, for any e∈C, C-{e}∈ℐ and C-{e}⊆X hold. Hence, C-{e}∈ℐX, that is, C∈𝒞(M|X) and 𝒞1⊆𝒞(M|X). On the other hand, for any C′∈𝒞(M|X) and any e∈C′, it is easy to prove C′-{e}∈ℐX⊆ℐ. Since C′⊆X and C′∉ℐX, then C′∉ℐ. Therefore, C′∈𝒞(M). Since C′⊆X, then 𝒞(M|X)⊆𝒞1 holds.Example 34.
LetM=(U,ℐ) be a matroid, where U={a,b,c,d,e,f} and 𝒞(M)={{e,f},{a,d,e},{a,d,f},{b,c,e},{b,c,f},{a,b,c,d}}. Clearly, M is an Eulerian matroid and 𝒞(M) a covering of  U. Suppose X1={a,b,d,f}, X2={a,b,c,e,f}, and X3={d}. Then
(11)𝒞(M)_(X1)=𝒞(M∣X1)={{a,d,f}},𝒞(M)¯(X1)=𝒞(M),𝒞(M)_(X2)=𝒞(M∣X2)={{e,f},{b,c,e},{b,c,f}},𝒞(M)¯(X2)=𝒞(M),𝒞(M)_(X3)=𝒞(M∣X3)=∅,𝒞(M)¯(X3)={{a,d,e},{a,d,f},{a,b,c,d}}.
Similarly, according to the above proposition, we can obtain the following proposition.Proposition 35.
LetM=(U,ℐ) be an Eulerian matroid and X⊆U. Then
(12)X_=⋃‍𝒞(M∣X),X¯=⋃‍{C∈𝒞(M)∣C⋂‍X≠∅}.Proof.
It is easy to prove this proposition by Definition31 and Proposition 33.Example 36 (continued from Example34).
As shown in Example34, the covering-based lower and upper approximation sets of X1, X2, and X3, respectively, are X_1={a,d,f}, X¯1=⋃‍𝒞(M)=U, X_2=⋃‍𝒞(M|X2)={b,c,e,f}, X¯2=⋃‍𝒞(M)=U, X_3=⋃‍𝒞(M|X3)=∅, X¯3=⋃‍𝒞(M)=U.The above proposition shows that the covering-based lower and covering-based upper approximation operators of covering-based rough sets can be denoted by the circuits of matroids. Li and Liu [21] have already proved the closure operator of matroids and covering-based upper approximation operator are equivalent if and only if the covering is unary. Based on their works, the following proposition can be presented.Proposition 37.
LetM=(U,ℐ) be an Eulerian matroid. For any X⊆U, X¯=clM(X) if and only if 𝒞(M) is a partition of U.Proof.
According to Proposition28, 𝒞(M) is a unary covering if and only if 𝒞(M) is a partition of U. Hence, this proposition is easy to prove.Example 38.
LetM=(U,ℐ) be an Eulerian matroid, where U={a,b,c,d,e,f} and 𝒞(M)={{a,b},{c,f},{d,e}}. Suppose X1={a,b,e}, X2={c,d}, and X3={f}. Then X¯1={a,b,d,e}, X¯2={c,d,e,f}, and X¯3={c,f}, and clM(X1)={a,b,d,e}, clM(X2)={c,d,e,f} and clM(X3)={c,f}.Proposition 39.
LetM=(U,ℐ) be an Eulerian matroid. For any X⊆U, X∈ℐ if and only if  𝒞(M)¯(~X)=𝒞(M).Proof.
(⇒): Suppose X∈ℐ. Clearly, it is easy to see 𝒞(M)¯(~X)⊆𝒞(M) according to Proposition 33. If there exists C′∈𝒞(M) such that C′∉𝒞(M)¯(~X), then C′⋂‍(~X)=∅. Thus C′⊆X. Clearly, it is a contradiction to X∈ℐ(M). Then C∈𝒞(M)¯(~X) for any C∈𝒞(M), that is, 𝒞(M)⊆𝒞(M)¯(~X). Hence 𝒞(M)¯(~X)=𝒞(M).
(⇐): Suppose X∉ℐ. Then there exists C∈𝒞(M) such that C⊆X, that is, C⋂‍(~X)=∅. Thus C∉𝒞(M)¯(~X). Hence 𝒞(M)¯(~X)≠𝒞(M); it is a contradiction to 𝒞(M)¯(~X)=𝒞(M). Then X∈ℐ.In fact, the above proposition indicates that the independent sets of an Eulerian matroid can be judged from the viewpoint of covering-based rough sets.Example 40 (continued from Example38).
Since𝒞(M)¯(~X1)={{c,f},{d,e}}, 𝒞(M)¯(~X2)={{a,b},{c,f},{d,e}} and 𝒞(M)¯(~X3)={{a,b},{c,f},{d,e}}, then X1∉ℐ, X2∈ℐ, and X3∈ℐ.In fact, it is easy to find that the circuits of an Eulerian matroid contain a partition of the universe at least. Therefore, we study the relationships between the circuits of an Eulerian matroid and its subset family.Proposition 41.
LetM=(U,ℐ) be an Eulerian matroid and X⊆U. Then there exists a partition U/R={C1,C2,…,Cm}⊆𝒞(M) such that R_(X)⊆X_ and R¯(X)⊆X¯, where R_,R¯ are the classical approximation operators.Proof.
It is easy to prove this proposition by Definition31 and Proposition 35.Example 42 (continued from Example38).
It is not difficult to find thatU/R=𝒞(M). Hence, the covering-based upper and lower approximation operators are the classical upper and lower approximation operators, respectively.Proposition 43.
LetM=(U,ℐ) be an Eulerian matroid and X⊆U. Then 𝒞(M)¯(X)=𝒞(M)_(X) if and only if {{x}|x∈X}⊆𝒞(M).Proof.
(
⇒
): Suppose there exists x′∈X such that {x′}∉𝒞(M). Then there exists C′={x′,x1,…,xs}(s≥1) such that C′∈𝒞(M) and C′∈𝒞(M)¯({x′}). Since {x′}⊂C′, then C′∉𝒞(M)_({x′}). It is contradictory. Thus {{x}|x∈X}⊆𝒞(M).
(
⇐
): Since {{x}|x∈X}⊆𝒞(M) holds for any X⊆U, then 𝒞(M)¯(X)={{x}|x∈X}=𝒞(M)_(X).Similarly, according to the above proposition, the following proposition can be presented.Proposition 44.
LetM=(U,ℐ) be an Eulerian matroid and X⊆U. Then X¯=X_ if and only if {{x}|x∈X}⊆𝒞(M).Since a family of circuits determines only one matroid, then the relationship between two coverings, which are induced by two Eulerian matroids, is presented in the following proposition.Proposition 45.
LetM1=(U,ℐ1) and M2=(U,ℐ2) be two Eulerian matroids. If ℐ1≠ℐ2, then there exists X⊆U such that 𝒞(M1)¯(X)≠𝒞(M2)¯(X) and 𝒞(M1)_(X)≠𝒞(M2)_(X).In fact, the above proposition shows that different Eulerian matroids induce different covering-based approximation spaces and different covering-based approximation operators.The above results show that many important concepts and properties of covering-based rough sets can be concisely characterized by corresponding concepts and properties in matroids. Therefore, covering-based rough sets may be efficient to study matroids.


## 4. The Eulerian Matroid Induced by a Covering

From the above definitions and properties, we know that the circuits of an Eulerian matroid can construct only one covering-based approximation space. Now, in this section, we wonder if a coveringC of U forms the family of circuits of an Eulerian matroid, what conditions should the covering C satisfies? For this purpose, the concepts of antichain and blocker are introduced.Definition 46 (antichain [27]).
Let𝒜 be a family of subsets of U. If, for any A1,A2∈𝒜, A1⊈A2 and A2⊈A1 hold, then one says 𝒜 is an antichain of U.According to the above definition, it is easy to see that the family of circuits and the family of bases of a matroid are all antichains.Definition 47 (blocker [27]).
Let𝒜 be an antichain of  U. Then the blocker b(𝒜) of 𝒜 can be denoted as follows:
(13)b(𝒜)=Min{X⊆U∣∀A∈𝒜,X⋂‍A≠∅}.Example 48.
Let𝒜={{a,b},{a,c},{b,c,d}} be a family of subsets of U={a,b,c,d}. Clearly, 𝒜 is an antichain of U. Suppose b(𝒜) is the blocker of 𝒜. Then b(𝒜)=Min{{a,b},{a,c},{a,d},{b,c},{a,b,c},{a,b,d},{a,c,d},{b,c,d},{a,b,c,d}}={{a,b}, {a,c},{a,d},{b,c}}.Theorem 49 (see [27]).
LetM(U,ℐ) be a matroid. Then there exists another matroid on U, whose family of all bases is equal to Com(ℬ(M)).According to the above theorem, we introduce the concept of the dual matroid.Definition 50 (dual matroid [27]).
The matroid whose family of all bases is equal toCom(ℬ(M)) is called the dual matroid of M(U,ℐ) and is denoted as M*. In particular, if ℐ=ℐ(M*), M is called an identically self-dual matroid.Lemma 51 (see [27]).
IfM=(U,I) is a matroid, then
(14)𝒞(M*)=b(ℬ(M)),b(𝒞(M*))=ℬ(M).Now, based on the above results, a matroidal structure of covering-based rough sets will be constructed. Firstly, the concept of Eulerian covering is defined in the following definition.Definition 52 (Eulerian covering).
An Eulerian coveringC is a covering of  U with the following properties: (EC1)
C is an antichain;(EC2)
there existK1,K2,…,Km∈C such that {K1,K2,…,Km} is a partition of  U, where m∈ℕ+;(EC3)
ifK,K′∈C, K≠K′ and k∈K⋂‍K′, then there exists K′′∈C such that K′′⊆(K⋃‍K′)-{k}.Example 53.
LetU={a,b,c,d,e,f} and C={{a,b,c},{a,b,d},{a,b,e},{a,b,f},{a,c,d}, {a,c,e},{a,c,f},{a,d,e}, {a,d,f},{a,e,f},{b,c,d},{b,c,e},{b,c,f},{b,d,e},{b,d,f}, {b,e,f},{c,d,e},{c,d,f},{c,e,f},{d,e,f}}. Clearly, C is a covering of U and satisfies (EC1), (EC2), and (EC3) of Definition 52; then C is an Eulerian covering of  U.In fact, an Eulerian covering of a universe in compliance with the above definition satisfies the circuit axiom. In other words, it determines an Eulerian matroid.Proposition 54.
LetC be an Eulerian covering of U. Then C satisfies (C1), (C2), and (C3) of Theorem 17.Proof.
It is easy to prove this proposition by Theorem17 and Definition 52.Example 55 (continued from Example53).
As shown in Example53, C is the family of circuits of an Eulerian matroid M. Clearly, ℐ={X⊆U||X|≤2} and ℬ(M)=Max(ℐ)={B⊆U||B|=2}.Definition 56.
LetC be an Eulerian covering on U. The Eulerian matroid whose circuit set is C is denoted by M(C).In fact, a partition of a universe is an Eulerian covering. Hence, a matroidal structure of classical rough sets is constructed in the following proposition.Proposition 57.
LetR be an equivalence relation on U. Then there exists an Eulerian matroid M(U/R) such that 𝒞(M(U/R))=U/R.Proof.
It is easy to prove that every partition ofU is an Eulerian covering. Hence, the proof of this proposition has already been finished.Proposition 58.
LetR be an equivalence relation on U. Then
(15)ℬ(M*(UR))=Min{X⊆U∣R¯(X)=U}.Proof.
For anyX⊆U, it is obvious (∀A∈U/R,X⋂‍A≠∅)⇔R¯(X)=U. Then according to Lemma 51, we know that ℬ(M*(U/R))=b(𝒞(M(U/R)))=Min{X⊆U|∀A∈U/R,X⋂‍A≠∅}=Min{X⊆U|R¯(X)=U}.Example 59.
LetU={a,b,c,d,e,f} and U/R={{a,e},{b,d,f},{c}}. Then 𝒞(M(U/R))=U/R is the family of circuits of an Eulerian matroid induced by U/R. In addition, suppose M*(U/R) is the dual matroid of M(U/R). Then
(16)ℬ(M*(UR))=b(UR)=Min{X⊆U∣R¯(X)=U}={{a,b,c},{a,c,d},{a,c,f},i{b,c,e},{c,d,e},{c,e,f}}.Proposition 60.
LetC be an Eulerian covering of U and M*(C) the dual matroid of M(C). Then
(17)ℬ(M*(C))=Min{X⊆U∣C¯(X)=C}.Proof.
It is easy to prove this proposition by Lemma51 and Proposition 33.Example 61 (continued from Example53).
An Eulerian coveringC of U induces an Eulerian matroid M(C). Suppose M*(C) is the dual matroid of M(C). Then ℬ(M*(C))=b(C)=Min{X⊆U|C¯(X)=C}={B*⊆U||B*|=4}.


## 5. Conclusions

In this paper, we studied one type of covering-based rough sets on Eulerian matroids. Via inducing a covering from the circuits of an Eulerian matroid, the covering-based approximation operators were represented from the viewpoint of Eulerian matroids. First, we studied the properties of the covering induced by an Eulerian matroid and the properties of the covering-based approximation operators through Eulerian matroids. Second, the relationships between two covering-based approximation spaces induced by two Eulerian matroids were explored. Finally, a matroidal structure of covering-based rough sets was constructed.



---

*Source: 254797-2013-09-09.xml*