# Covering Cycle Matroid

Authors: Qingyin Li; William Zhu
Journal: ISRN Applied Mathematics
 (2013)

---

## Abstract

Covering is a type of widespread data representation while covering-based rough sets provide an efficient and systematic theory to deal with this type of data. Matroids are based on linear algebra and graph theory and have a variety of applications in many fields. In this paper, we construct two types of covering cycle matroids by a covering and then study the graphical representations of these two types of matriods. First, through defining a cycle graph by a set, the
type-1 covering cycle matroid is constructed by a covering. By a dual graph of the cycle graph, the covering can also induce the type-2 covering cycle matroid. Second, some characteristics of these two types of matroids are formulated by a covering, such as independent sets, bases, circuits, and support sets. Third, a coarse covering of a covering is defined to study the graphical representation of the type-1 covering cycle matroid. We prove that the type-1 covering cycle matroid is graphic while the type-2 covering cycle matroid is not always a graphic matroid. Finally, relationships between these two types of matroids and the function matroid are studied. In a word, borrowing from matroids, this work presents an interesting view, graph, to investigate covering-based rough sets.


---

## Body

## 1. Introduction

Covering is a type of common and important data organization mode, and it most appears in incomplete information/decision systems based on symbolic data [1, 2], numeric and fuzzy data [3, 4]. Covering-based rough set theory [5, 6] is an efficient tool to process these types of data. Recently, this theory has attracted much research interest with fruitful achievements on both theory and applications. For example, it has been applied to build axiomatic systems [7, 8] and establish knowledge reduction approaches [9, 10]. Moreover, it also has been used to construct covering structures [11, 12] and define minimal covering reducts [13, 14]. However, this theory has its own limitation in dealing with some hard problems including knowledge reduction. In order to improve its ability to process those hard problems, some other mathematical theories, such as fuzzy set theory [15, 16], topology [5, 17], Boolean algebra [18, 19], and matroid [20, 21] have been combined with covering-based rough set theory.Matroid theory [22] proposed by Whitney is a generalization of linear algebra, graph theory, and transcendence theory. The original purpose of this theory is to formalize the similarities between the ideas of independence and rank in graph theory and those of linear independence and dimension in the study of vector spaces [23]. Matroids have been applied to a number of fields, such as combinatorial optimization [24], algorithm design [25], and information coding [26]. Matroids can provide well-established platforms for greedy algorithms, which may help to process those problems that are difficultly solved by rough sets. Thus, several matroidal structures of rough sets have been studied from different viewpoints, such as binary relations [27], coverings [28, 29], and graphs [30]. Therefore, it makes sense to study matroidal structures of coverings through graphs.In this paper, inspired by union of matroids and cycle matroid, we construct two types of covering cycle matroids by a covering and then study the graphical representations of these two types of matroids. By defining a cycle graph through a set, any block of the covering can induce a cycle graph and a dual graph of the cycle graph, and then some cycle matroids and their dual matroids are obtained by these cycle graphs and dual graphs, respectively. Therefore, type-1 covering cycle matroid is obtained by the union of these cycle matroids, and type-2 covering cycle matroid is obtained by the union of the dual matroids of these cycle matroids. The independent sets, bases, and support sets of these two types of matroids are represented by the covering. In particular, the independent sets of the type-1 covering cycle matroid are equivalently represented by the lower approximations, and the support sets of the type-2 covering cycle matroid are equivalently represented by the upper approximations. We prove that the type-1 covering cycle matroid induced by a covering is equal to the one induced by the intersection reduct of the covering. We also investigate the graphical representations of these two types of matroids. By redefining a covering into a coarse covering, the matroid induced by a graph which is generated by the coarse covering is equal to the type-1 covering cycle matroid induced by the original covering. As for the type-2 covering cycle matroid, it is not always a graphic matroid. We also study relationships between these two types of matroids and the function matroid. Results show that these two types of covering cycle matroids are not always dual, and these three kinds of matroids are equal when the cardinality of any block of a covering is equal to 2.The rest of this paper is organized as follows. Section2 reviews some fundamental definitions about covering-based rough sets, matroids, and graphs. In Section 3, we construct two types of covering cycle matroids by a covering and then study the graphical representations of these two types of matroids. Section 4 studies relationships between three kinds of matroids, which are induced by a covering, respectively. Finally, this paper is concluded in Section 5.


## 2. Basic Definitions

This section recalls some fundamental definitions related to covering-based rough sets, matroids, and graphs.


### 2.1. Covering-Based Rough Sets

Covering is a common type of data structure, and it can characterize the practical problems with extensive coverage.Definition 1 (covering [31]).
LetU be a universe of discourse and C a family of nonempty subsets of U. If ∪C=U, then C is called a covering of U.As we know, a partition ofU is certainly a covering of U; so the concept of a covering is an extension to the concept of a partition.Neighborhoods are important concepts in rough sets, and they can describe the maximal dependence to an object.Definition 2 (indiscernible neighborhood [6]).
LetC be a covering of U and x∈U. IC(x)=∪{K∈C∣x∈K} is called the indiscernible neighborhood of x with respect to C. When there is no confusion, we omit the subscript C.In knowledge discovery, each element in a covering is called knowledge. As we know, some knowledge may be redundant. That is to say, removing those redundant knowledge cannot change the approximation accuracy. To deal with those redundant knowledge, a notion of reducible element is proposed and it has many different forms. For example, the reducible element proposed by Zhu and Wang [8] is different from the one defined by Y. Yao and B. Yao [12].Definition 3 (see [12]).
LetC be a covering of U. If K is an intersection of some elements in C-{K}, then K is said to be an intersection reducible element in C, otherwise K is said to be an intersection irreducible element. If every element of C is an intersection irreducible element, then C is said to be intersection irreducible; otherwise C is said to be intersection reducible.Theorem 4 (see [12]).
LetC be a covering of  U. Suppose K∈C is an intersection reducible element of C, then, for all K1∈C-{K}, K1 is an intersection reducible element of C-{K} if and only if K1 is an intersection reducible element of C.We can simplify a coveringC by iteratively removing reducible elements to obtain reduced forms of C.Definition 5 (see [12]).
LetC be a covering of U. If {Ki} is the set of all intersection reducible elements of C, the set C-{Ki} is called the intersection reduct of C and denoted by ∩-reduct(C).For a coveringC of  U, if K∈C is an intersection reducible element in C, then C-{K} is still a covering of U. Therefore, ∩-reduct(C) is a covering of U.In covering-based rough sets, an object is described by a pair of approximations. In the following definition, we introduce a pair of widely used approximations.Definition 6 (approximations [6]).
LetC be a covering of U. For all X⊆U,
(1)X+=∪{K∈C∣K⊆X},X+=∪{K∈C∣K∩X≠∅}
are called the lower and upper approximations of X, respectively.


### 2.2. Matroids

Matroids are algebraic structures that capture and generalize linear independence in vector spaces. A characteristic of matroids is that they are defined in many different but equivalent ways. In the following, we introduce one defined by independent sets.Definition 7 (matroid [22]).
A matroidM is a pair (U,I) where U is a finite set, and I (independent sets) is a family of subsets of U satisfying the following three conditions:(I1)
∅∈I;(I2)
ifI∈I, and I0⊆I, then I0∈I;(I3)
ifI1, I2∈I, and |I1|<|I2|, then there exists e∈I2-I1 such that I1∪{e}∈I,where|X| denotes the cardinality of X.For a better understanding of the different definitions of a matroid, some operations will be firstly introduced as follows.Definition 8 (see [22]).
LetA be a family of subsets of U. One can denote Low(A)={X⊆U∣∃A∈A, s.t.X⊆A},Max(A)={X⊆U∣∀Y∈A, X⊆Y⇒X=Y},Min(A)={X⊆U∣∀Y∈A, Y⊆X⇒X=Y},Opp(A)={X⊆U∣X∉A}.In order to introduce the dual matroid of a matroid, we first recall the definition of a base in a matroid. Any base of a matroid generalizes the maximal linearly independent vector group of a vector space and the spanning tree of a graph.Definition 9 (base [22]).
LetM be a matroid. A maximal independent set of M is called a base of M, and the set of all bases of M is denoted by B(M), that is, B(M)=Max(I).Clearly, when the set of all independent setsI of a matroid M is given, one can determine B(M) and vice versa. By the bases in matroids, we introduce the concept of the dual matroid of a matroid, which is an extension of the orthogonal complement space of a vector space.Definition 10 (dual matroid [22]).
LetM be a matroid and B*(M)={Bc∣B∈B(M)}, where Bc denotes the complement of B in U. Then B*(M) is the family of all bases of a matroid which is called the dual matroid of M and denoted by M*.The complement of the independent sets in power sets is dependent ones. And a minimal set of the dependent sets is called a circuit of the matroid. A matroid uniquely determines its circuits and vice versa.Definition 11 (circuit [22]).
LetM=(U, I) be a matroid. A minimal dependent set in M is called a circuit of M, and we denote the family of all circuits of M by 𝒞(M), that is, 𝒞(M)=Min(Opp(I)).Matroids have many equivalent definitions. Support sets can uniquely determine one matroid. Support sets are defined as follows.Definition 12 (support set [22]).
LetM=(U, I) be a matroid. For all X⊆U, if there exists a base B∈B(M) such that B⊆X, then X is called a support set of M, and we denote the family of all support sets of M by S(M).From the viewpoint of circuits, matroids are viewed as a generalization of graphs. In the following, we will recall the definition of cycle matroid.Proposition 13 (cycle matroid [22]).
LetG=(V,E) be a graph. Denote I={I⊆E∣I(as a subgraph) does not contain cycles}. Then (E,I) is a matroid, and it is called the cycle matroid of G and denoted as M(G).Union of matroids was introduced by Nash-Williams in 1966. In the following, we will recall the definition of union of matroids on the same universe.Definition 14 (union of matroids [22]).
LetM1=(U,I1), M2=(U,I2),…, and Mm=(U,Im) be a group of matroids on the universe U. Then M=(U,I) is a matroid, where I={I1∪I2∪⋯∪Im∣Ii∈Ii, 1≤i≤m}, which is called the union of M1,M2,…, and Mm and denoted by M=∨i=1mMi.The graphical representation of matroids is an important content in matroids. For a matroidM, M is a graphic matroid [22] if there exists a graph G such that M≅M(G). An equivalent characterization of a graphic matroid is given in the following.Theorem 15 (see [22]).
A matroid is graphic if and only if it has no minor which is one of theU2,4, F7, F7*, M*(K5), and M*(K3,3).A minor of a matroidM is another matroid N that is obtained from M by a sequence of restriction and contraction operations. We will introduce two special matroids in the following two definitions.Definition 16 (restriction matroid [22]).
LetM=(U, I) be a matroid. For any X⊆U, we define IX={I⊆X∣I∈I}. Then there exists a matroid M∣X on X with IX as its independent sets, and M∣X is called the restriction matroid of M on X.Definition 17 (uniform matroid [22]).
Let|U|=n. For an integer k≤n, we define I={X⊆U∣|X|≤k}. Then (U, I) forms a matroid, and it is called a uniform matroid and denoted by Uk,n.


### 2.3. Graphs

Graph theory provides an intuitive way to interpret and comprehend a number of practical and theoretical problems. Theoretically, a graph is an ordered pair consisting of vertices and edges that connect these vertices.Agraph [32] is a pair G=(V, E) consisting of a set V of vertices and a set E of edges such that E⊆V×V. A path [32] is a simple graph whose vertices can be ordered so that two vertices are adjacent if and only if they are consecutive in the list. A cycle [32] is a graph with an equal number of vertices and edges whose vertices can be placed around a circle so that two vertices are adjacent if and only they appear consecutively along the circle. A loop [32] is an edge whose endpoints are equal.


## 2.1. Covering-Based Rough Sets

Covering is a common type of data structure, and it can characterize the practical problems with extensive coverage.Definition 1 (covering [31]).
LetU be a universe of discourse and C a family of nonempty subsets of U. If ∪C=U, then C is called a covering of U.As we know, a partition ofU is certainly a covering of U; so the concept of a covering is an extension to the concept of a partition.Neighborhoods are important concepts in rough sets, and they can describe the maximal dependence to an object.Definition 2 (indiscernible neighborhood [6]).
LetC be a covering of U and x∈U. IC(x)=∪{K∈C∣x∈K} is called the indiscernible neighborhood of x with respect to C. When there is no confusion, we omit the subscript C.In knowledge discovery, each element in a covering is called knowledge. As we know, some knowledge may be redundant. That is to say, removing those redundant knowledge cannot change the approximation accuracy. To deal with those redundant knowledge, a notion of reducible element is proposed and it has many different forms. For example, the reducible element proposed by Zhu and Wang [8] is different from the one defined by Y. Yao and B. Yao [12].Definition 3 (see [12]).
LetC be a covering of U. If K is an intersection of some elements in C-{K}, then K is said to be an intersection reducible element in C, otherwise K is said to be an intersection irreducible element. If every element of C is an intersection irreducible element, then C is said to be intersection irreducible; otherwise C is said to be intersection reducible.Theorem 4 (see [12]).
LetC be a covering of  U. Suppose K∈C is an intersection reducible element of C, then, for all K1∈C-{K}, K1 is an intersection reducible element of C-{K} if and only if K1 is an intersection reducible element of C.We can simplify a coveringC by iteratively removing reducible elements to obtain reduced forms of C.Definition 5 (see [12]).
LetC be a covering of U. If {Ki} is the set of all intersection reducible elements of C, the set C-{Ki} is called the intersection reduct of C and denoted by ∩-reduct(C).For a coveringC of  U, if K∈C is an intersection reducible element in C, then C-{K} is still a covering of U. Therefore, ∩-reduct(C) is a covering of U.In covering-based rough sets, an object is described by a pair of approximations. In the following definition, we introduce a pair of widely used approximations.Definition 6 (approximations [6]).
LetC be a covering of U. For all X⊆U,
(1)X+=∪{K∈C∣K⊆X},X+=∪{K∈C∣K∩X≠∅}
are called the lower and upper approximations of X, respectively.


## 2.2. Matroids

Matroids are algebraic structures that capture and generalize linear independence in vector spaces. A characteristic of matroids is that they are defined in many different but equivalent ways. In the following, we introduce one defined by independent sets.Definition 7 (matroid [22]).
A matroidM is a pair (U,I) where U is a finite set, and I (independent sets) is a family of subsets of U satisfying the following three conditions:(I1)
∅∈I;(I2)
ifI∈I, and I0⊆I, then I0∈I;(I3)
ifI1, I2∈I, and |I1|<|I2|, then there exists e∈I2-I1 such that I1∪{e}∈I,where|X| denotes the cardinality of X.For a better understanding of the different definitions of a matroid, some operations will be firstly introduced as follows.Definition 8 (see [22]).
LetA be a family of subsets of U. One can denote Low(A)={X⊆U∣∃A∈A, s.t.X⊆A},Max(A)={X⊆U∣∀Y∈A, X⊆Y⇒X=Y},Min(A)={X⊆U∣∀Y∈A, Y⊆X⇒X=Y},Opp(A)={X⊆U∣X∉A}.In order to introduce the dual matroid of a matroid, we first recall the definition of a base in a matroid. Any base of a matroid generalizes the maximal linearly independent vector group of a vector space and the spanning tree of a graph.Definition 9 (base [22]).
LetM be a matroid. A maximal independent set of M is called a base of M, and the set of all bases of M is denoted by B(M), that is, B(M)=Max(I).Clearly, when the set of all independent setsI of a matroid M is given, one can determine B(M) and vice versa. By the bases in matroids, we introduce the concept of the dual matroid of a matroid, which is an extension of the orthogonal complement space of a vector space.Definition 10 (dual matroid [22]).
LetM be a matroid and B*(M)={Bc∣B∈B(M)}, where Bc denotes the complement of B in U. Then B*(M) is the family of all bases of a matroid which is called the dual matroid of M and denoted by M*.The complement of the independent sets in power sets is dependent ones. And a minimal set of the dependent sets is called a circuit of the matroid. A matroid uniquely determines its circuits and vice versa.Definition 11 (circuit [22]).
LetM=(U, I) be a matroid. A minimal dependent set in M is called a circuit of M, and we denote the family of all circuits of M by 𝒞(M), that is, 𝒞(M)=Min(Opp(I)).Matroids have many equivalent definitions. Support sets can uniquely determine one matroid. Support sets are defined as follows.Definition 12 (support set [22]).
LetM=(U, I) be a matroid. For all X⊆U, if there exists a base B∈B(M) such that B⊆X, then X is called a support set of M, and we denote the family of all support sets of M by S(M).From the viewpoint of circuits, matroids are viewed as a generalization of graphs. In the following, we will recall the definition of cycle matroid.Proposition 13 (cycle matroid [22]).
LetG=(V,E) be a graph. Denote I={I⊆E∣I(as a subgraph) does not contain cycles}. Then (E,I) is a matroid, and it is called the cycle matroid of G and denoted as M(G).Union of matroids was introduced by Nash-Williams in 1966. In the following, we will recall the definition of union of matroids on the same universe.Definition 14 (union of matroids [22]).
LetM1=(U,I1), M2=(U,I2),…, and Mm=(U,Im) be a group of matroids on the universe U. Then M=(U,I) is a matroid, where I={I1∪I2∪⋯∪Im∣Ii∈Ii, 1≤i≤m}, which is called the union of M1,M2,…, and Mm and denoted by M=∨i=1mMi.The graphical representation of matroids is an important content in matroids. For a matroidM, M is a graphic matroid [22] if there exists a graph G such that M≅M(G). An equivalent characterization of a graphic matroid is given in the following.Theorem 15 (see [22]).
A matroid is graphic if and only if it has no minor which is one of theU2,4, F7, F7*, M*(K5), and M*(K3,3).A minor of a matroidM is another matroid N that is obtained from M by a sequence of restriction and contraction operations. We will introduce two special matroids in the following two definitions.Definition 16 (restriction matroid [22]).
LetM=(U, I) be a matroid. For any X⊆U, we define IX={I⊆X∣I∈I}. Then there exists a matroid M∣X on X with IX as its independent sets, and M∣X is called the restriction matroid of M on X.Definition 17 (uniform matroid [22]).
Let|U|=n. For an integer k≤n, we define I={X⊆U∣|X|≤k}. Then (U, I) forms a matroid, and it is called a uniform matroid and denoted by Uk,n.


## 2.3. Graphs

Graph theory provides an intuitive way to interpret and comprehend a number of practical and theoretical problems. Theoretically, a graph is an ordered pair consisting of vertices and edges that connect these vertices.Agraph [32] is a pair G=(V, E) consisting of a set V of vertices and a set E of edges such that E⊆V×V. A path [32] is a simple graph whose vertices can be ordered so that two vertices are adjacent if and only if they are consecutive in the list. A cycle [32] is a graph with an equal number of vertices and edges whose vertices can be placed around a circle so that two vertices are adjacent if and only they appear consecutively along the circle. A loop [32] is an edge whose endpoints are equal.


## 3. Two kinds of Matroids Induced by a Covering

In this section, we define a cycle graph by a set and then construct two kinds of matroidal structures by a covering.


### 3.1. Type-1 Covering Cycle Matroid

In this section, we construct the type-1 covering cycle matroid by a covering and then study the graphical representation of the matroid. The relationship between the matroid and a matroid induced by a graph generated by the covering is also studied.In order to establish the connection between coverings and matroids, we first propose a notion as follows.Definition 18 (cycle graph induced by a set).
LetX={x1,x2,…,xm}⊆U and m≥1. We define a graph GX=(V,E) induced by X as follows:(1)
|V|=m;(2)
E=X where the path x1x2…xm is a cycle.As we know, a set is an unordered collection with no duplicate elements. That is to say a set can induce different cycle graphs. An example to illustrate this feature is given in the following.Example 19.
LetX={e1, e2, e3, e4}, GX1 and GX2 the cycle graphs induced by X. As shown in Figure 1, GX1 and GX2 are represented by (a) and (b), respectively.Two different cycle graphs induced by a set.
(a)
G
X
1
(b)
G
X
2Given a set, according to Definition18, the set can induce a cycle graph. Given a graph, according to Proposition 13, the graph can induce a cycle matroid. Although a set can induce some different cycle graphs, all the cycle matroids induced by these graphs have only one circuit which is equal to the set. Hence the cycle matroids induced by these graphs are the same, and any maximal proper subset of the given set is a base of the cycle matroid generated by a cycle graph which is induced by the given set.Proposition 20.
LetX={x1,x2,…,xm} be a subset of  U, GX a cycle graph induced by X, and M(GX)=(X,I(X)) the cycle matroid induced by GX. Therefore B(M(GX))={X-{xi}∣1≤i≤m}.Proof.
According to Definition18, the path x1x2…xm is a cycle. Hence for any i∈{1,2,…,m}, X-{xi} does not contain cycles. According to Proposition 13, B(M(GX))=Max(I(X))=Max{I⊆X∣I (as a subgraph) does not contain cycles}={X-{xi}∣1≤i≤m}.The following example illustrates the uniqueness of the cycle matroid generated by different cycle graphs induced by the same set.Example 21 (continued from Example19).
LetGX1, GX2 be two different cycle graphs induced by X and M(GX1)=(X1,I(X1)) and M(GX2)=(X2,I(X2)) the cycle matroids induced by GX1 and GX2, respectively. By direct computation, I(X1)=2X1-{X1} and I(X2)=2X2-{X2}. Moreover, X1=X2. Hence M(GX1)=M(GX2).Given a covering of a universe, according to Definition18, every block of the covering can induce a cycle graph. Hence any block of a covering can induce a matroid. What we concern about is that if the covering can generate a matroid. According to Definition 14, we can obtain a matroid by the union of the matroids, which are induced by a block of the given covering, respectively.Proposition 22.
LetC={K1,K2,…,Km} be a covering of U, GKi a cycle graph induced by Ki(1≤i≤m), and M(GKi)=(Ki,I(Ki)) the cycle matroid induced by GKi. Therefore M(C)=(U,I(C)) is a matroid and it is denoted by M(C)=∨i=1mM(GKi), where I(C)={I1∪I2∪⋯∪Im∣Ii∈I(Ki),1≤i≤m}.Proof.
For anyKi∈C, we define a matroid on U as MKi=(U,I(Ki)), where MKi∣Ki=M(GKi) and U-Ki is a circuit of MKi. According to Definition 14, it is straightforward that M(C)=∨i=1mM(GKi)=∨i=1mMKi. So M(C) is a martoid.Definition 23 (type-1 covering cycle matroid).
LetC={K1,K2,…,Km} be a covering of U. M(C)=∨i=1mM(GKi) is called type-1 covering cycle matroid induced by C.Example 24.
LetU={e1,e2,e3,e4} and C={K1,K2,K3}, where K1={e3}, K2={e1,e2,e4}, and K3={e2,e3}. As shown in Figure 2, three cycle graphs GK1, GK2, and GK3 induced by K1, K2, and K3 are represented by Figures 2(a), 2(b), and 2(c), respectively. The cycle matroids induced by GK1, GK2, and GK3 are M(GK1)=(K1,I(K1)), M(GK2)=(K2,I(K2)) and M(GK3)=(K3,I(K3)). By direct computation, I(K1)={∅}, I(K2)={∅,{e1},{e2},{e4},{e1,e2},{e1,e4},{e2,e4}}, and I(K3)={∅,{e2},{e3}}. Therefore the type-1 covering cycle matroid induced by C is M(C)=(U,I(C)), where I(C)=2U-{U}.Cycle graphs induced byK1, K2, and K3, respectively.
(a)
G
K
1
(b)
G
K
2
(c)
G
K
3For a set, a maximal independent set of the cycle matroid generated by a cycle graph induced by the set is a maximal proper subset of the set. In the following proposition, we use all the blocks of a covering to represent a base of the type-1 covering cycle matroid induced by the covering.Proposition 25.
LetC={K1,K2,…,Km} be a covering of U and M(C) the type-1 covering cycle matroid induced by C. Then B(M(C))=Max{∪i=1m(Ki-{xKi})∣xKi∈Ki}.Proof.
According to Definition9, B(M(C))=Max(I(C)). Since GKi is a cycle graph induced by Ki(1≤i≤m) and M(GKi)=(Ki,I(Ki)) the cycle matroid induced by GKi, according Proposition 20, B(M(GKi))={Ki-{xKi}∣xKi∈Ki}. Hence B(M(C))=Max{∪i=1m(Ki-{xKi})∣xKi∈Ki}.In the following proposition, when a covering degenerates a partition, we represent the bases of the type-1 covering cycle matroid induced by the covering.Proposition 26.
LetC={K1,K2,…,Km} be a covering of U and M(C) the type-1 covering cycle matroid induced by C. If C is a partition of U, then B(M(C))={∪i=1m(Ki-{xKi})∣xKi∈Ki}.Proof.
SinceC is a partition of U and xKt∈Kt for any t∈I={1,2,…,m}, (Ki-{xKi})∩(Kj-{xKj})=∅ for any i, j∈I. According to Proposition 25, B(M(C))=Max{∪i=1m(Ki-{xKi})∣xKi∈Ki}={∪i=1m(Ki-{xKi})∣xKi∈Ki}.An equivalent formulation of the independent sets of the type-1 covering cycle matroid induced by a partition is provided from the viewpoint of lower approximations. In fact, a subset of a universe is an independent set if and only if the lower approximation of the subset is equal to empty set.Proposition 27.
LetC={K1,K2,…,Km} be a covering of U and M(C)=(U,I(C)) the type-1 covering cycle matroid induced by C. If C is a partition of U, then I(C)={X⊆U∣X+=∅}.Proof.
For anyX∈I(C), there exists B∈B(M(C)) such that X⊆B. Since C is a partition of U, there exists xKi∈Ki(1≤i≤m) such that B=∪i=1m(Ki-{xKi}), and (Ki-{xKi})∩(Kj-{xKj})=∅ for any i,j∈{1,2,…,m}. So Kj⊈∪i=1m(Ki-{xKi}) for any Kj∈C. Therefore, Kj⊈X for any Kj∈C, that is, I(C)⊆{X⊆U∣X+=∅}. Conversely, for any X⊆U, if X+=∅, then Ki⊈X for all Ki∈C. So X∩Ki⊂Ki. According to Proposition 20, there exists B∈B(M(GKi)) such that X∩Ki⊆B. Hence X∩Ki∈I(Ki). Moreover, X=X∩U=X∩(∪i=1mKi)=∪i=1m(X∩Ki). So X∈I(C), that is, {X⊆U∣X+=∅}⊆I(C). To sum up, this completes the proof.When a covering of a universe is not a partition of the universe, there exists an independent set whose lower approximation is not empty. Example24 can be used to illustrate this feature. Since I(C)=2U-{U}, {2,3}∈I(C). But {2,3}+={2,3}≠∅.A covering can induce the type-1 covering cycle matroid. We would like to know whether there exist two different coverings such that the type-1 covering cycle matroids induced by them are equal. As shown in the following proposition, the type-1 covering cycle matroid induced by any coveringC is equal to the one induced by the covering C-{K}, if K is an intersection reducible element of C.Proposition 28.
LetC={K1,K2,…,Km} be a covering of U. If Kj is an intersection reducible element of C, then M(C)=M(C-{Kj}).Proof.
SinceKj is an intersection reducible element of C, there exist some elements Kj1,Kj2,…,Kjn in C such that Kj=∩i=1nKji. For any xKj∈Kj, xKj∈Kji(1≤i≤n). If |Kj|=1, then I(Kj)={∅}. Hence B(M(C))=Max{∪i=1m(Ki-{xKi})∣xKi∈Ki}=Max{∪i=1j-1(Ki-{xKi})∪(∪i=j+1m(Ki-{xKi}))∣xKi∈Ki}=B(M(C-{Kj})). If |Kj|>1, then ∪i=1n-1(Kji-{xKj})∪(Kjn-{xKj′})=∪i=1nKji for any xKj,xKj′∈Kj and xKj≠xKj′. Since Kj=∩i=1nKji, Kj-{xKj}⊂Kj⊂∪i=1nKji. So Max{∪i=1n(Kji-{xKi})∣xKi∈Kj}={∪i=1nKji}=Max{∪i=1nKji∪Kj}=Max{∪i=1nKji∪(Kj-{xKj})∣xKj∈Kj}. Hence B(M(C))=Max{∪i=1m(Ki-{xKi})∣xKi∈Ki}=Max{∪i=j1jnKi∪(∪t=1∧t≠im(Kt-{xKt}))∣xKt∈Kt}=Max{∪i=j1jnKi∪(∪t=1∧t≠ij-1(Kt-{xKt}))∪(∪t=j+1∧t≠im(Kt-{xKt}))∣xKt∈Kt}=Max{∪i=j1jn(Ki-xKi)∪(∪t=1∧t≠ij-1(Kt-{xKt}))∪(∪t=j+1∧t≠im(Kt-{xKt}))∣xKi∈Ki, xKt∈Kt}=B(M(C-{Kj})). Therefore, M(C)=M(C-{Kj}).The type-1 covering cycle matroid induced by any covering is equal to the one induced by the intersection reduct of the covering.Corollary 29.
LetC be a covering of U. M(C)=M(∩-reduct(C)).Proof.
SupposeK1,K2,…,Kn are all intersection reducible elements of C, then according to Proposition 28, M(C)=M(C-{K1}). According to Theorem 4, K2 is also an intersection reducible element of the covering C-{K1}. Hence M(C-{K1})=M(C-{K1,K2}). Similarly, we can prove that M(C-{K1,K2})=M(C-{K1,K2,K3})=⋯=M(∩-reduct(C)). Therefore, M(C)=M(∩-reduct(C)).In the rest of this subsection, the main task is to study the graphical representation of the type-1 covering cycle matroid. First, we redefine a given covering of a universe into another covering of the universe.Definition 30.
LetC be a covering of U. A family of subsets of U is defined as follows:
(2)P={It(x)∣It(x)=Is(x)foranyx∈U,1≤t<s≤|C|}.P is then also a covering of U and it is called the coarse covering of C. When t≥2, It(x) is the indiscernible neighborhood of x with respect to covering {It-1(x)∣x∈U}.Example 31.
LetU={e1,e2,…,e9} and C={K1,K2,K3,K4,K5}, where K1={e1,e2,e3}, K2={e2,e3}, K3={e4,e5}, K4={e6,e7}, and K5={e6,e8,e9}. By direct computation I2(e1)=I2(e2)=I2(e3)=K1=K1∪K2=I3(e1)=I3(e2)=I3(e3), I2(e4)=I2(e5)=K3=I3(e4)=I3(e5), I2(e6)=I2(e7)=I2(e8)=I2(e9)=K4∪K5=I3(e6)=I3(e7)=I3(e8)=I3(e9). So P={I2(ei)∣1≤i≤9}={K1∪K2,K3,K4∪K5}={{e1,e2,e3},{e4,e5},{e6,e7,e8,e9}}.Proposition 32.
LetC be a covering of U and P the coarse covering of C. P is a partition of U.Proof.
For anyx, y∈U, It(x), It(y)∈P. If It(x)∩It(y)≠∅, then we need to prove that It(x)=It(y). If there exists z∈It(x) such that z∉It(y), then for any z0∈It(x)∩It(y), x,z,z0∈It(x), y,z0∈It(y) and x,y,z0∈It(z0). So x,y,z,z0∈It+1(z0). Therefore, z∈It+2(y), that is, It+2(y)≠It(y), which is contradictory to It(x)∈P. So It(x)⊆It(y). Similarly, we can prove that It(y)⊆It(x). Consequently, It(x)=It(y), that is, P is a partition of U.Relationships between those blocks of a covering and any block in the coarse covering of the covering are shown in the following two propositions.Proposition 33.
LetC be a covering of U and P the coarse covering of C. For any X∈P and K∈C, if X∩K≠∅, then K⊆X.Proof.
For anyx∈K and y∈X∩K, x∈I(y)⊆I2(y)⊆⋯⊆It-1(y)⊆It(y)=X. So K⊆X.Proposition 34.
LetC be a covering of U and P the coarse covering of C. For any X∈P, if Ki∩X≠∅ and Kj∩X=∅ for any i∈I⊆{1,2,…,|C|} and j∈Ic, then X=∪i∈IKi.Proof.
SinceC is a covering of U and X⊆U, X⊆∪i∈IKi. According to Proposition 33, ∪i∈IKi⊆X. So X=∪i∈IKi.As we know, matroids and graphs coincide with each other when the circuit of a matroid is degenerated to the cycle of a graph. The following proposition shows relationships between each block in the coarse covering of a given covering and circuits of the type-1 covering cycle matroid induced by the given covering.Proposition 35.
LetC be a covering of U and P the coarse covering of C. For any X∈P, if X∉B(M(C)∣X), then X∈𝒞(M(C)).Proof.
SinceX∉B(M(C)∣X), X∉I(C). If there exists K∈C such that X=K, then Y∈I(C) for any Y⊂X. For any K∈C, if K≠X, then we need to prove that Y∈I(C) for any Y⊂X. According to Proposition 34, there exists I⊆{1,2,…,|C|} such that X=∪i∈IKi. For any e∈X, there exists I0⊆I such that e∈Ki(i∈I0) and e∉Ki(i∈I-I0). So X-{e}=∪i∈I-I0Ki∪(∪i∈I0(Ki-{e})). Since e∈X, according to Proposition 32, e∈It(e)=X. If for any i∈I-I0 and j∈I0, Ki∩Kj=∅, then It(e)=∪i∈I0Ki⊂X, which is contradictory to It(e)=X. So there exists I1⊆I-I0 with the condition that for any i1∈I1, i2∈I-I0-I1 and j2∈I0, there exists j1∈I0 such that Ki1∩Kj1≠∅ and Ki2∩Kj2=∅. Hence for any xKi∈Ki∩Kj(i∈I1,j∈I0), X-{e}=∪i∈I-I0-I1Ki∪(∪i∈I1(Ki-{xKi}))∪(∪i∈I0(Ki-{e})). Similarly, we can prove that there exists I2⊆I-I0-I1 with the condition that, for any i1∈I2, i2∈I-I0-I1-I2 and j2∈I1, there exists j1∈I1 such that Ki1∩Kj1≠∅ and Ki2∩Kj2=∅. And for any xKi∈Ki∩Kj(i∈I2,j∈I1), X-{e}=∪i∈I-I0-I1-I2Ki∪(∪i∈I2(Ki-{xKi}))∪(∪i∈I1(Ki-{xKi}))∪(∪i∈I0(Ki-{e})). Since I is a finite set, there exist a finite set J with j0≥1 for any j0∈J and an element xKi∈Ki∩Kj(i∈Ij0(j0∈J),j∈Ij0-1) such that X-{e}=∪i∈Ij(j∈J)(Ki-{xKi})∪(∪i∈I0(Ki-{e})). Therefore, Y∈I(C) for any Y⊂X. So X∈Min(Opp(I(C))), that is, X∈𝒞(M(C)).In the following proposition, we study relationships between the coarse covering of a given covering and circuits of the type-1 covering cycle matroid induced by the given covering.Proposition 36.
LetC be a covering of U and P the coarse covering of C. For any X∈P′⊆P, Y∈P-P′, if X∈B(M(C)∣X) and Y∉B(M(C)∣Y), then P-P′=𝒞(M(C)).Proof.
For anyZ∈P-P′, Z∉B(M(C)∣Z), according to Proposition 35, Z∈𝒞(M(C)). Conversely, for any Z∈𝒞(M(C)), Z∈Min(Opp(I(C))). Hence Z∉I(C), that is, Z∉B(M(C)∣Z). There exists an index set I⊆{1,2,…,|C|} such that for any i∈I and j∈Ic, Z∩Ki≠∅ and Z∩Kj=∅. So Z⊆∪i∈IKi. Suppose there exists a nonempty index set I0⊂I with the condition that, for any i∈I0 and j∈I-I0, Kj⊆Z and there exists xKi∈Ki such that xKi∉Z. Since Z∈𝒞(M(C)), I0≠I. There exists a finite set J with j≥1 for any j∈J such that Ki∩Ki1≠∅(i∈Ij(j∈J),i1∈Ij-1) and for any xKi∈Ki∩Ki1, Z⊆∪i∈I-I0-∪j∈JIjKi∪(∪i∈Ij(j∈J)(Ki-xKi))∪(∪i∈I0(Ki-xKi)). For any i, j∈I-I0-∪j∈JIj and t∈Ic, Ki∩Kt=∅ and Kj∩Kt=∅. If I-I0-∪j∈JIj≠∅, then ∪i∈I-I0-∪j∈JIjKi∈𝒞(M(C)), which is contradictory to Z∈𝒞(M(C)). So Z⊆∪i∈Ij(j∈J)(Ki-xKi)∪(∪i∈I0(Ki-xKi)), that is, Z∈I(C), which is contradictory to Z∈𝒞(M(C)). Therefore I0=∅, that is, Z=∪i∈IKi. Since Z∩Ki=∅ for any i∈Ic, there exists t∈{1,2,…,|C|} such that It(x)=Is(x)=Z for any x∈Z and t<s≤|C|, that is, Z∈P. Therefore, Z∈P-P′.In the following definition, we introduce a method to get a connected graph by some disjoint graphs.Definition 37 (vertex identification [22]).
Suppose that the graphG is obtained from the disjoint graphs G1 and G2 by identifying the vertices u1 of G1 and u2 of G2 as the vertex u of G. This operation is called a vertex identification.A connected graph is constructed by some disjoint graphs through vertex identification. These disjoint graphs are, respectively, induced by a block in the coarse covering of a covering.Definition 38.
LetP be the coarse covering of C, GXi a cycle graph induced by Xi, and GXj a path induced by Xj, where Xi,Xj∈P, Xj∈B(M(C)∣Xj) and Xi∉B(M(C)∣Xi). We define a graph by vertex identification of GX1,GX2,…, and GX|P|, and this graph is denoted by GP. We say GP is a graph induced by P.The following example is about the operation of vertex identification and a graph obtained by the coarse covering of a covering.Example 39 (continued from Example31).
P
=
{
{
e
1
,
e
2
,
e
3
}
,
{
e
4
,
e
5
}
,
{
e
6
,
e
7
,
e
8
,
e
9
}
}
=
{
K
1
∪
K
2
,
K
3
,
K
4
∪
K
5
}. Since K4∪K5∉B(M(C)∣(K4∪K5)), K3∉B(M(C)∣K3) and K1∪K2∈B(M(C)∣(K1∪K2)), GK1∪K2 is a path and both GK3 and GK4∪K5 are cycle graphs. Those three graphs are shown in Figure 3. If GP is a graph obtained by vertex identification of these three graphs, then GP is a graph induced by P. GP is shown in Figure 4.Graphs induced byK1∪K2, K3, and K4∪K5, respectively.
(a)
G
K
1
∪
K
2
(b)
G
K
3
(c)
G
K
4
∪
K
5Figure 4
GraphGP obtained by vertex identification of GK1∪K2, GK3, and GK4∪K5.It is obvious that there are some different graphs which can be obtained by the coarse covering of a covering through the operation of vertex identification. Cycles of each graph are the same despite these graphs are different. And these cycles are those blocks in the coarse covering which do not belong to the family of all independent sets of the type-1 covering cycle matroid induced by the original covering. From the viewpoint of the circuit of a matroid, a matroid induced by a connected graph constructed from the coarse covering of a given covering is equal to the type-1 covering cycle matroid induced by the given covering.Theorem 40.
LetC be a covering of U, P the coarse covering of C, and GP a graph induced by P. Then M(C)=M(GP).Proof.
We need to prove only that𝒞(M(C))=𝒞(M(GP)). Since GP is the graph obtained by vertex identification of GXi(1≤i≤|P|), then 𝒞(M(GP))=P-P′, where P′ is a family of subsets of P and it has a property that X∈B(M(C)∣X) for any X∈P′. According to Proposition 36, 𝒞(M(C))=𝒞(M(GP)). Therefore, M(C)=M(GP).


### 3.2. Type-2 Covering Cycle Matroid

In this section, type-2 covering cycle matroid is defined, and then the graphical representation of this type of covering cycle matroid is studied.Every connected plane graphG has a natural dual graph G* such that (G*)*=G. The dual is formed by associating a vertex of G* with each face of G and including a dual edge e* in G* for each edge e of G, such that the endpoints of the edge e* are the vertices for the faces on the two sides of e.In graph theory, a plane graph is a graph in which no edges cross each other. For any setX, a cycle graph GX induced by X has no edges cross each other, so the graph GX is a plane graph and has a dual graph. Since GX has two faces, its dual graph has only two vertices. In order to further understand the notion about a dual graph of a plane graph, an example is given in the following.Example 41 (continued from Example24).
As shown in Figure5, the dual graphs of the cycle graphs GK1, GK2, and GK3 are represented by Figures 5(a), 5(b), and 5(c), respectively.Dual graphs ofGK1, GK2 and GK3.
(a)
G
K
1
*
(b)
G
K
2
*
(c)
G
K
3
*Given a set, there are some different cycle graphs induced by the set, but these cycle graphs have the same dual graph. As we know that any edge in any cycle graph induced by the set has two faces, so all the dual graphs of these cycle graphs have only two vertices and any two edges of each dual graph form a cycle. That is to say, any two edges of each dual graph are adjacent. So these dual graphs are the same. When the set is a singleton, the cycle graph induced by the set is a loop. Since the edge of a loop has two faces, the dual graph of the loop has two vertices and an edge. That is to say, a singleton whose element is the edge of the dual graph of the loop is always a base of the matroid induced by this dual graph. Therefore, for a cycle graph, a singleton that consists of any edge of the dual graph of the cycle graph is a base of the matroid induced by the dual graph. Then the following proposition can be obtained.Proposition 42.
LetX be a subset of U, GX* the dual graph of a cycle graph induced by X, and M(GX*)=(U,I*(X)) the cycle matroid induced by GX*. Then B(M(GX*))={{x}∣x∈X}=B*(M(GX)).Proof.
According to Proposition13, Definitions 18 and 10, Proposition 20, and the notion of a dual graph of a plane graph, it is straightforward.The above proposition shows that a singleton consists of any element in the given set that is an independent set of the dual matroid of the cycle matroid, which is induced by a cycle graph. And this cycle graph is induced by the given set. According to Definition14, the following proposition can be obtained easily.Proposition 43.
LetC={K1,K2,…,Km} be a covering of U,  GKi* the dual graph of a cycle graph induced by Ki(1≤i≤m), and M(GKi*)=(Ki,I*(Ki)) the cycle matroid induced by GKi*. Then M′(C)=(U,I′(C)) is a matroid and it is denoted by M′(C)=∨i=1mM(GKi*), where I′(C)={∪i=1m{xKi}∣{xKi}⊆Ki}.Proof.
For anyxKi∈Ki, {xKi}≠∅. So according to Proposition 42, {xKi}∈B(M(GKi*)). Hence ∅, {xKi}∈I*(Ki). For any Ki∈C, we define a matroid on U as MKi⋆=(U,I*(Ki)), where MKi⋆∣Ki=M(GKi*) and U-Ki is a circuit of MKi⋆. Moreover ∅⊆Ki(1≤i≤m); so, according to Definition 14, {∪i=1m{xKi}∣{xKi}⊆Ki} is the set of all independent sets of the matroid ∨i=1mMKi⋆. Therefore M′(C)=∨i=1mM(GKi*)=∨i=1mMKi⋆; that is, M′(C) is a matroid.Definition 44 (type-2 covering cycle matroid).
LetC={K1,K2,…,Km} be a covering of U. Then M′(C)=∨i=1mM(GKi*) is called type-2 covering cycle matroid inducd by C.Example 45 (continued from Example41).
The dual matroids of three cycle matroids induced by three cycle graphs generated byK1, K2, and K3 are M(GK1*)=(K1,I*(K1)), M(GK2*)=(K2,I*(K2)) and M(GK3*)=(K3,I*(K3)). By direct computation, I*(K1)={∅,{e3}}, I*(K2)={∅,{e1},{e2},{e4}}, I*(K3)={∅,{e2},{e3}}. If M′(C)=(U,I′(C))=∨i=1mM(GKi*), then I′(C)={∅,{e1},{e2},{e3},{e4},{e1,e2},{e1,e3},{e2,e3},{e2,e4},{e3,e4},{e1,e2,e3},{e2,e3,e4}}.The following proposition shows relationships between the set of all bases of the type-2 covering cycle matroid induced by a covering and those blocks of the covering.Proposition 46.
LetC={K1,K2,…,Km} be a covering of U. If M′(C) is the type-2 covering cycle matroid induced by C, then B(M′(C))=Max{∪i=1m{xKi}∣xKi∈Ki}.Proof.
According to Proposition43, I′(C)={∪i=1m{xKi}∣{xKi}⊆Ki}. Since B(M′(C))=Max(I′(C)), B(M′(C))=Max{∪i=1m{xKi}∣{xKi}⊆Ki}=Max{∪i=1m{xKi}∣xKi∈Ki}.When a covering is a partition of the universe, relationships between the set of all bases of the type-2 covering cycle matroid and those blocks of the covering are investigated in the following proposition.Proposition 47.
LetC={K1,K2,…,Km} be a covering of U and M′(C) the type-2 covering cycle matroid induced by C. If C is a partition of U, then B(M′(C))={∪i=1m{xKi}∣xKi∈Ki}.Proof.
According to Proposition46, B(M′(C))=Max{∪i=1m{xKi}∣xKi∈Ki}. Since C is a partition of U, {xKi}∩{xKj}=∅ for any xKi∈Ki, xKj∈Kj(i,j∈{1,2,…,m}andi≠j). Hence B(M′(C))={∪i=1m{xKi}∣xKi∈Ki}.In the following proposition, we connect upper approximations with support sets of the type-2 covering cycle matroid. In fact, when a covering is a partition of a universe, a subset of the universe is a support set of the type-2 covering cycle matroid induced by the covering if and only if the upper approximation of the subset is equal to the universe.Proposition 48.
LetC={K1,K2,…,Km} be a covering of U and M′(C) the type-2 covering cycle matroid induced by C. If C is a partition of U, then S(M′(C))={X⊆U∣X+=U}.Proof.
For anyS∈S(M′(C)), according to Definition 12, there exists B∈B(M′(C)) such that B⊆S. Since C is a partition of U, according to Proposition 47, B(M′(C))={∪i=1m{xKi}∣xKi∈Ki}. Hence B∩Ki≠∅ for all Ki∈C. Since B⊆S, B∩Ki⊆S∩Ki, that is, S∩Ki≠∅ for all Ki∈C. Therefore, S+=U, that is, S(M′(C))⊆{X⊆U∣X+=U}. Conversely, for any X∈{X⊆U∣X+=U}, X+=U. Since C is a partition of U, X∩Ki≠∅ for all Ki∈C; that is, there exist xKi∈Ki(1≤i≤m) such that xKi∈X. Hence ∪i=1m{xKi}⊆X. Since C is a partition of U, according to Proposition 47, ∪i=1m{xKi}∈B(M′(C)). According to Definition 12, X∈S(M′(C)), that is, {X⊆U∣X+=U}⊆S(M′(C)). To sum up, this completes the proof.When a coveringC of a universe is not a partition of the universe, there exists a subset of the universe which is not the support set of M′(C) such that the upper approximation of the subset is equal to the universe.Example 49 (continued from Example45).
SinceB(M′(C))={{e1,e2,e3},{e2,e3,e4}}, there does not exist B∈B(M′(C)) such that B⊆{e1,e3,e4}. So {e1,e3,e4}∉S(M′(C)). But {e1,e3,e4}+=U.An equivalent formulation of the family of all circuits of the type-2 covering cycle matroid induced by a covering is provided by those blocks of the covering. In fact, when the covering is a partition of a universe, a subset of the universe is a circuit if and only if it is contained in a block of the covering and its cardinality is equal to 2.Proposition 50.
LetC={K1,K2,…,Km} be a partition of U and M′(C) the type-2 covering cycle matroid induced by C. Therefore 𝒞(M′(C))={X⊆U∣|X|=2 and ∃Ki∈Cs.t.X⊆Ki}.Proof.
SinceI′(C)={∪i=1m{xKi}∣{xKi}⊆Ki}, {x}∈I′(C) for any x∈U. For any X∈𝒞(M′(C)), X∈Min(Opp(I′(C))). If there exists Ki∈C such that X∩Ki≠∅, then |X∩Ki|≥2 since C is a partition of U. If Y⊆X∩Ki and |Y|=2, then Y⊆Ki and Y∉I′(C). So Y=X=X∩Ki. So there exists Ki∈C such that X⊆Ki and |X|=2, that is, X∈{X⊆U∣|X|=2 and ∃Ki∈Cs.t.X⊆Ki}. Conversely, for any Y∈{X⊆U∣|X|=2 and ∃Ki∈Cs.t.X⊆Ki}, there exists Ki∈C such that Y⊆Ki. Since C is a partition of U and |Y|=2, Y∉I′(C) and Z∈I′(C) for any Z⊂Y. So Y∈Min(Opp(I′(C))), that is, Y∈𝒞(M′(C)). To sum up, this completes the proof.A connected graph is constructed by the dual graphs of some cycle graphs through vertex identification. These cycle graphs are, respectively, induced by an element in a partition of a universe.Definition 51.
LetC be a partition of  U and GKi* the dual graph of a cycle graph induced by Ki(1≤i≤|C|). We define a graph by vertex identification of GK1*,GK2*,…, and GK|C|*, and this graph is denoted by GC. We say GC is a graph induced by C.An example about the operation of vertex identification of the dual graphs of the cycle graphs, which are, respectively, induced by an element of a partition, is shown in the following.Example 52.
LetU={e1,e2,e3,e4,e5} and C={K1,K2}, where K1={e3,e5}, K2={e1,e2,e4}. As shown in Figure 6, the dual graphs of two cycle graphs GK1 and GK2 are represented by Figures 6(a) and 6(b), respectively. Figure 7 is the representation of GC which is obtained by vertex identification of GK1* and GK2*.Graphs ofGK1* and GK2*.
(a)
G
K
1
*
(b)
G
K
2
*Figure 7
GraphGC obtained by vertex identification of GK1* and GK2*.Theorem40 shows the type-1 covering cycle matroid induced by any covering is graphic and a graph corresponding to the matroid is constructed by the covering via an indirect route. In the following theorem, we will discuss the relationship between a connected graph induced by a partition and the type-2 covering cycle matroid induced by the partition. It is obvious that there are some different graphs obtained by the partition through the operation of vertex identification. The cycles of each graph are the same while these graphs are different.Theorem 53.
LetC be a partition of  U, GC a graph obtained by vertex identification of GKi*(1≤i≤|C|), and M′(C) the type-2 covering cycle matroid induced by C. Then M′(C)=M(GC).Proof.
We need to prove only that𝒞(M′(C))=𝒞(M(GC)). For Ki(1≤i≤m), if Xi⊆Ki and |Xi|=2, then for any x∈Xi, x is a edge of GKi* and Xi is a cycle of GKi*. Therefore Xi is a cycle of GC. If Xi⊆Ki and |Xi|=1, then Xi∈B(M(GKi*)). According to Proposition 50, 𝒞(M′(C))=𝒞(M(GC)). Therefore, M′(C)=M(GC).For any coveringC of the universe, we want to know that whether the type-2 covering cycle matroid M′(C) is graphic. A counterexample is given in the following.Example 54.
LetU={e1,e2,e3,e4,e5}, C={K1,K2,K3} and M′(C) the type-2 covering cycle matroid induced by C, where K1={e1,e2,e3}, K2={e2,e3,e4}, K3={e5}. By direct computation, I′(M′(C))=Low{{e1,e2,e5}, {e1,e3,e5}, {e1,e4,e5}, {e2,e3,e5}, {e2,e4,e5}, {e3,e4,e5}}. If X={e1,e2,e3,e4}, then I(M′(C)∣X)=Low{{e1,e2},{e1,e3},{e1,e4},{e2,e3},{e2,e4},{e3,e4}}. So M′(C)∣X=U2,4. Hence M′(C) is not a graphic matroid.


## 3.1. Type-1 Covering Cycle Matroid

In this section, we construct the type-1 covering cycle matroid by a covering and then study the graphical representation of the matroid. The relationship between the matroid and a matroid induced by a graph generated by the covering is also studied.In order to establish the connection between coverings and matroids, we first propose a notion as follows.Definition 18 (cycle graph induced by a set).
LetX={x1,x2,…,xm}⊆U and m≥1. We define a graph GX=(V,E) induced by X as follows:(1)
|V|=m;(2)
E=X where the path x1x2…xm is a cycle.As we know, a set is an unordered collection with no duplicate elements. That is to say a set can induce different cycle graphs. An example to illustrate this feature is given in the following.Example 19.
LetX={e1, e2, e3, e4}, GX1 and GX2 the cycle graphs induced by X. As shown in Figure 1, GX1 and GX2 are represented by (a) and (b), respectively.Two different cycle graphs induced by a set.
(a)
G
X
1
(b)
G
X
2Given a set, according to Definition18, the set can induce a cycle graph. Given a graph, according to Proposition 13, the graph can induce a cycle matroid. Although a set can induce some different cycle graphs, all the cycle matroids induced by these graphs have only one circuit which is equal to the set. Hence the cycle matroids induced by these graphs are the same, and any maximal proper subset of the given set is a base of the cycle matroid generated by a cycle graph which is induced by the given set.Proposition 20.
LetX={x1,x2,…,xm} be a subset of  U, GX a cycle graph induced by X, and M(GX)=(X,I(X)) the cycle matroid induced by GX. Therefore B(M(GX))={X-{xi}∣1≤i≤m}.Proof.
According to Definition18, the path x1x2…xm is a cycle. Hence for any i∈{1,2,…,m}, X-{xi} does not contain cycles. According to Proposition 13, B(M(GX))=Max(I(X))=Max{I⊆X∣I (as a subgraph) does not contain cycles}={X-{xi}∣1≤i≤m}.The following example illustrates the uniqueness of the cycle matroid generated by different cycle graphs induced by the same set.Example 21 (continued from Example19).
LetGX1, GX2 be two different cycle graphs induced by X and M(GX1)=(X1,I(X1)) and M(GX2)=(X2,I(X2)) the cycle matroids induced by GX1 and GX2, respectively. By direct computation, I(X1)=2X1-{X1} and I(X2)=2X2-{X2}. Moreover, X1=X2. Hence M(GX1)=M(GX2).Given a covering of a universe, according to Definition18, every block of the covering can induce a cycle graph. Hence any block of a covering can induce a matroid. What we concern about is that if the covering can generate a matroid. According to Definition 14, we can obtain a matroid by the union of the matroids, which are induced by a block of the given covering, respectively.Proposition 22.
LetC={K1,K2,…,Km} be a covering of U, GKi a cycle graph induced by Ki(1≤i≤m), and M(GKi)=(Ki,I(Ki)) the cycle matroid induced by GKi. Therefore M(C)=(U,I(C)) is a matroid and it is denoted by M(C)=∨i=1mM(GKi), where I(C)={I1∪I2∪⋯∪Im∣Ii∈I(Ki),1≤i≤m}.Proof.
For anyKi∈C, we define a matroid on U as MKi=(U,I(Ki)), where MKi∣Ki=M(GKi) and U-Ki is a circuit of MKi. According to Definition 14, it is straightforward that M(C)=∨i=1mM(GKi)=∨i=1mMKi. So M(C) is a martoid.Definition 23 (type-1 covering cycle matroid).
LetC={K1,K2,…,Km} be a covering of U. M(C)=∨i=1mM(GKi) is called type-1 covering cycle matroid induced by C.Example 24.
LetU={e1,e2,e3,e4} and C={K1,K2,K3}, where K1={e3}, K2={e1,e2,e4}, and K3={e2,e3}. As shown in Figure 2, three cycle graphs GK1, GK2, and GK3 induced by K1, K2, and K3 are represented by Figures 2(a), 2(b), and 2(c), respectively. The cycle matroids induced by GK1, GK2, and GK3 are M(GK1)=(K1,I(K1)), M(GK2)=(K2,I(K2)) and M(GK3)=(K3,I(K3)). By direct computation, I(K1)={∅}, I(K2)={∅,{e1},{e2},{e4},{e1,e2},{e1,e4},{e2,e4}}, and I(K3)={∅,{e2},{e3}}. Therefore the type-1 covering cycle matroid induced by C is M(C)=(U,I(C)), where I(C)=2U-{U}.Cycle graphs induced byK1, K2, and K3, respectively.
(a)
G
K
1
(b)
G
K
2
(c)
G
K
3For a set, a maximal independent set of the cycle matroid generated by a cycle graph induced by the set is a maximal proper subset of the set. In the following proposition, we use all the blocks of a covering to represent a base of the type-1 covering cycle matroid induced by the covering.Proposition 25.
LetC={K1,K2,…,Km} be a covering of U and M(C) the type-1 covering cycle matroid induced by C. Then B(M(C))=Max{∪i=1m(Ki-{xKi})∣xKi∈Ki}.Proof.
According to Definition9, B(M(C))=Max(I(C)). Since GKi is a cycle graph induced by Ki(1≤i≤m) and M(GKi)=(Ki,I(Ki)) the cycle matroid induced by GKi, according Proposition 20, B(M(GKi))={Ki-{xKi}∣xKi∈Ki}. Hence B(M(C))=Max{∪i=1m(Ki-{xKi})∣xKi∈Ki}.In the following proposition, when a covering degenerates a partition, we represent the bases of the type-1 covering cycle matroid induced by the covering.Proposition 26.
LetC={K1,K2,…,Km} be a covering of U and M(C) the type-1 covering cycle matroid induced by C. If C is a partition of U, then B(M(C))={∪i=1m(Ki-{xKi})∣xKi∈Ki}.Proof.
SinceC is a partition of U and xKt∈Kt for any t∈I={1,2,…,m}, (Ki-{xKi})∩(Kj-{xKj})=∅ for any i, j∈I. According to Proposition 25, B(M(C))=Max{∪i=1m(Ki-{xKi})∣xKi∈Ki}={∪i=1m(Ki-{xKi})∣xKi∈Ki}.An equivalent formulation of the independent sets of the type-1 covering cycle matroid induced by a partition is provided from the viewpoint of lower approximations. In fact, a subset of a universe is an independent set if and only if the lower approximation of the subset is equal to empty set.Proposition 27.
LetC={K1,K2,…,Km} be a covering of U and M(C)=(U,I(C)) the type-1 covering cycle matroid induced by C. If C is a partition of U, then I(C)={X⊆U∣X+=∅}.Proof.
For anyX∈I(C), there exists B∈B(M(C)) such that X⊆B. Since C is a partition of U, there exists xKi∈Ki(1≤i≤m) such that B=∪i=1m(Ki-{xKi}), and (Ki-{xKi})∩(Kj-{xKj})=∅ for any i,j∈{1,2,…,m}. So Kj⊈∪i=1m(Ki-{xKi}) for any Kj∈C. Therefore, Kj⊈X for any Kj∈C, that is, I(C)⊆{X⊆U∣X+=∅}. Conversely, for any X⊆U, if X+=∅, then Ki⊈X for all Ki∈C. So X∩Ki⊂Ki. According to Proposition 20, there exists B∈B(M(GKi)) such that X∩Ki⊆B. Hence X∩Ki∈I(Ki). Moreover, X=X∩U=X∩(∪i=1mKi)=∪i=1m(X∩Ki). So X∈I(C), that is, {X⊆U∣X+=∅}⊆I(C). To sum up, this completes the proof.When a covering of a universe is not a partition of the universe, there exists an independent set whose lower approximation is not empty. Example24 can be used to illustrate this feature. Since I(C)=2U-{U}, {2,3}∈I(C). But {2,3}+={2,3}≠∅.A covering can induce the type-1 covering cycle matroid. We would like to know whether there exist two different coverings such that the type-1 covering cycle matroids induced by them are equal. As shown in the following proposition, the type-1 covering cycle matroid induced by any coveringC is equal to the one induced by the covering C-{K}, if K is an intersection reducible element of C.Proposition 28.
LetC={K1,K2,…,Km} be a covering of U. If Kj is an intersection reducible element of C, then M(C)=M(C-{Kj}).Proof.
SinceKj is an intersection reducible element of C, there exist some elements Kj1,Kj2,…,Kjn in C such that Kj=∩i=1nKji. For any xKj∈Kj, xKj∈Kji(1≤i≤n). If |Kj|=1, then I(Kj)={∅}. Hence B(M(C))=Max{∪i=1m(Ki-{xKi})∣xKi∈Ki}=Max{∪i=1j-1(Ki-{xKi})∪(∪i=j+1m(Ki-{xKi}))∣xKi∈Ki}=B(M(C-{Kj})). If |Kj|>1, then ∪i=1n-1(Kji-{xKj})∪(Kjn-{xKj′})=∪i=1nKji for any xKj,xKj′∈Kj and xKj≠xKj′. Since Kj=∩i=1nKji, Kj-{xKj}⊂Kj⊂∪i=1nKji. So Max{∪i=1n(Kji-{xKi})∣xKi∈Kj}={∪i=1nKji}=Max{∪i=1nKji∪Kj}=Max{∪i=1nKji∪(Kj-{xKj})∣xKj∈Kj}. Hence B(M(C))=Max{∪i=1m(Ki-{xKi})∣xKi∈Ki}=Max{∪i=j1jnKi∪(∪t=1∧t≠im(Kt-{xKt}))∣xKt∈Kt}=Max{∪i=j1jnKi∪(∪t=1∧t≠ij-1(Kt-{xKt}))∪(∪t=j+1∧t≠im(Kt-{xKt}))∣xKt∈Kt}=Max{∪i=j1jn(Ki-xKi)∪(∪t=1∧t≠ij-1(Kt-{xKt}))∪(∪t=j+1∧t≠im(Kt-{xKt}))∣xKi∈Ki, xKt∈Kt}=B(M(C-{Kj})). Therefore, M(C)=M(C-{Kj}).The type-1 covering cycle matroid induced by any covering is equal to the one induced by the intersection reduct of the covering.Corollary 29.
LetC be a covering of U. M(C)=M(∩-reduct(C)).Proof.
SupposeK1,K2,…,Kn are all intersection reducible elements of C, then according to Proposition 28, M(C)=M(C-{K1}). According to Theorem 4, K2 is also an intersection reducible element of the covering C-{K1}. Hence M(C-{K1})=M(C-{K1,K2}). Similarly, we can prove that M(C-{K1,K2})=M(C-{K1,K2,K3})=⋯=M(∩-reduct(C)). Therefore, M(C)=M(∩-reduct(C)).In the rest of this subsection, the main task is to study the graphical representation of the type-1 covering cycle matroid. First, we redefine a given covering of a universe into another covering of the universe.Definition 30.
LetC be a covering of U. A family of subsets of U is defined as follows:
(2)P={It(x)∣It(x)=Is(x)foranyx∈U,1≤t<s≤|C|}.P is then also a covering of U and it is called the coarse covering of C. When t≥2, It(x) is the indiscernible neighborhood of x with respect to covering {It-1(x)∣x∈U}.Example 31.
LetU={e1,e2,…,e9} and C={K1,K2,K3,K4,K5}, where K1={e1,e2,e3}, K2={e2,e3}, K3={e4,e5}, K4={e6,e7}, and K5={e6,e8,e9}. By direct computation I2(e1)=I2(e2)=I2(e3)=K1=K1∪K2=I3(e1)=I3(e2)=I3(e3), I2(e4)=I2(e5)=K3=I3(e4)=I3(e5), I2(e6)=I2(e7)=I2(e8)=I2(e9)=K4∪K5=I3(e6)=I3(e7)=I3(e8)=I3(e9). So P={I2(ei)∣1≤i≤9}={K1∪K2,K3,K4∪K5}={{e1,e2,e3},{e4,e5},{e6,e7,e8,e9}}.Proposition 32.
LetC be a covering of U and P the coarse covering of C. P is a partition of U.Proof.
For anyx, y∈U, It(x), It(y)∈P. If It(x)∩It(y)≠∅, then we need to prove that It(x)=It(y). If there exists z∈It(x) such that z∉It(y), then for any z0∈It(x)∩It(y), x,z,z0∈It(x), y,z0∈It(y) and x,y,z0∈It(z0). So x,y,z,z0∈It+1(z0). Therefore, z∈It+2(y), that is, It+2(y)≠It(y), which is contradictory to It(x)∈P. So It(x)⊆It(y). Similarly, we can prove that It(y)⊆It(x). Consequently, It(x)=It(y), that is, P is a partition of U.Relationships between those blocks of a covering and any block in the coarse covering of the covering are shown in the following two propositions.Proposition 33.
LetC be a covering of U and P the coarse covering of C. For any X∈P and K∈C, if X∩K≠∅, then K⊆X.Proof.
For anyx∈K and y∈X∩K, x∈I(y)⊆I2(y)⊆⋯⊆It-1(y)⊆It(y)=X. So K⊆X.Proposition 34.
LetC be a covering of U and P the coarse covering of C. For any X∈P, if Ki∩X≠∅ and Kj∩X=∅ for any i∈I⊆{1,2,…,|C|} and j∈Ic, then X=∪i∈IKi.Proof.
SinceC is a covering of U and X⊆U, X⊆∪i∈IKi. According to Proposition 33, ∪i∈IKi⊆X. So X=∪i∈IKi.As we know, matroids and graphs coincide with each other when the circuit of a matroid is degenerated to the cycle of a graph. The following proposition shows relationships between each block in the coarse covering of a given covering and circuits of the type-1 covering cycle matroid induced by the given covering.Proposition 35.
LetC be a covering of U and P the coarse covering of C. For any X∈P, if X∉B(M(C)∣X), then X∈𝒞(M(C)).Proof.
SinceX∉B(M(C)∣X), X∉I(C). If there exists K∈C such that X=K, then Y∈I(C) for any Y⊂X. For any K∈C, if K≠X, then we need to prove that Y∈I(C) for any Y⊂X. According to Proposition 34, there exists I⊆{1,2,…,|C|} such that X=∪i∈IKi. For any e∈X, there exists I0⊆I such that e∈Ki(i∈I0) and e∉Ki(i∈I-I0). So X-{e}=∪i∈I-I0Ki∪(∪i∈I0(Ki-{e})). Since e∈X, according to Proposition 32, e∈It(e)=X. If for any i∈I-I0 and j∈I0, Ki∩Kj=∅, then It(e)=∪i∈I0Ki⊂X, which is contradictory to It(e)=X. So there exists I1⊆I-I0 with the condition that for any i1∈I1, i2∈I-I0-I1 and j2∈I0, there exists j1∈I0 such that Ki1∩Kj1≠∅ and Ki2∩Kj2=∅. Hence for any xKi∈Ki∩Kj(i∈I1,j∈I0), X-{e}=∪i∈I-I0-I1Ki∪(∪i∈I1(Ki-{xKi}))∪(∪i∈I0(Ki-{e})). Similarly, we can prove that there exists I2⊆I-I0-I1 with the condition that, for any i1∈I2, i2∈I-I0-I1-I2 and j2∈I1, there exists j1∈I1 such that Ki1∩Kj1≠∅ and Ki2∩Kj2=∅. And for any xKi∈Ki∩Kj(i∈I2,j∈I1), X-{e}=∪i∈I-I0-I1-I2Ki∪(∪i∈I2(Ki-{xKi}))∪(∪i∈I1(Ki-{xKi}))∪(∪i∈I0(Ki-{e})). Since I is a finite set, there exist a finite set J with j0≥1 for any j0∈J and an element xKi∈Ki∩Kj(i∈Ij0(j0∈J),j∈Ij0-1) such that X-{e}=∪i∈Ij(j∈J)(Ki-{xKi})∪(∪i∈I0(Ki-{e})). Therefore, Y∈I(C) for any Y⊂X. So X∈Min(Opp(I(C))), that is, X∈𝒞(M(C)).In the following proposition, we study relationships between the coarse covering of a given covering and circuits of the type-1 covering cycle matroid induced by the given covering.Proposition 36.
LetC be a covering of U and P the coarse covering of C. For any X∈P′⊆P, Y∈P-P′, if X∈B(M(C)∣X) and Y∉B(M(C)∣Y), then P-P′=𝒞(M(C)).Proof.
For anyZ∈P-P′, Z∉B(M(C)∣Z), according to Proposition 35, Z∈𝒞(M(C)). Conversely, for any Z∈𝒞(M(C)), Z∈Min(Opp(I(C))). Hence Z∉I(C), that is, Z∉B(M(C)∣Z). There exists an index set I⊆{1,2,…,|C|} such that for any i∈I and j∈Ic, Z∩Ki≠∅ and Z∩Kj=∅. So Z⊆∪i∈IKi. Suppose there exists a nonempty index set I0⊂I with the condition that, for any i∈I0 and j∈I-I0, Kj⊆Z and there exists xKi∈Ki such that xKi∉Z. Since Z∈𝒞(M(C)), I0≠I. There exists a finite set J with j≥1 for any j∈J such that Ki∩Ki1≠∅(i∈Ij(j∈J),i1∈Ij-1) and for any xKi∈Ki∩Ki1, Z⊆∪i∈I-I0-∪j∈JIjKi∪(∪i∈Ij(j∈J)(Ki-xKi))∪(∪i∈I0(Ki-xKi)). For any i, j∈I-I0-∪j∈JIj and t∈Ic, Ki∩Kt=∅ and Kj∩Kt=∅. If I-I0-∪j∈JIj≠∅, then ∪i∈I-I0-∪j∈JIjKi∈𝒞(M(C)), which is contradictory to Z∈𝒞(M(C)). So Z⊆∪i∈Ij(j∈J)(Ki-xKi)∪(∪i∈I0(Ki-xKi)), that is, Z∈I(C), which is contradictory to Z∈𝒞(M(C)). Therefore I0=∅, that is, Z=∪i∈IKi. Since Z∩Ki=∅ for any i∈Ic, there exists t∈{1,2,…,|C|} such that It(x)=Is(x)=Z for any x∈Z and t<s≤|C|, that is, Z∈P. Therefore, Z∈P-P′.In the following definition, we introduce a method to get a connected graph by some disjoint graphs.Definition 37 (vertex identification [22]).
Suppose that the graphG is obtained from the disjoint graphs G1 and G2 by identifying the vertices u1 of G1 and u2 of G2 as the vertex u of G. This operation is called a vertex identification.A connected graph is constructed by some disjoint graphs through vertex identification. These disjoint graphs are, respectively, induced by a block in the coarse covering of a covering.Definition 38.
LetP be the coarse covering of C, GXi a cycle graph induced by Xi, and GXj a path induced by Xj, where Xi,Xj∈P, Xj∈B(M(C)∣Xj) and Xi∉B(M(C)∣Xi). We define a graph by vertex identification of GX1,GX2,…, and GX|P|, and this graph is denoted by GP. We say GP is a graph induced by P.The following example is about the operation of vertex identification and a graph obtained by the coarse covering of a covering.Example 39 (continued from Example31).
P
=
{
{
e
1
,
e
2
,
e
3
}
,
{
e
4
,
e
5
}
,
{
e
6
,
e
7
,
e
8
,
e
9
}
}
=
{
K
1
∪
K
2
,
K
3
,
K
4
∪
K
5
}. Since K4∪K5∉B(M(C)∣(K4∪K5)), K3∉B(M(C)∣K3) and K1∪K2∈B(M(C)∣(K1∪K2)), GK1∪K2 is a path and both GK3 and GK4∪K5 are cycle graphs. Those three graphs are shown in Figure 3. If GP is a graph obtained by vertex identification of these three graphs, then GP is a graph induced by P. GP is shown in Figure 4.Graphs induced byK1∪K2, K3, and K4∪K5, respectively.
(a)
G
K
1
∪
K
2
(b)
G
K
3
(c)
G
K
4
∪
K
5Figure 4
GraphGP obtained by vertex identification of GK1∪K2, GK3, and GK4∪K5.It is obvious that there are some different graphs which can be obtained by the coarse covering of a covering through the operation of vertex identification. Cycles of each graph are the same despite these graphs are different. And these cycles are those blocks in the coarse covering which do not belong to the family of all independent sets of the type-1 covering cycle matroid induced by the original covering. From the viewpoint of the circuit of a matroid, a matroid induced by a connected graph constructed from the coarse covering of a given covering is equal to the type-1 covering cycle matroid induced by the given covering.Theorem 40.
LetC be a covering of U, P the coarse covering of C, and GP a graph induced by P. Then M(C)=M(GP).Proof.
We need to prove only that𝒞(M(C))=𝒞(M(GP)). Since GP is the graph obtained by vertex identification of GXi(1≤i≤|P|), then 𝒞(M(GP))=P-P′, where P′ is a family of subsets of P and it has a property that X∈B(M(C)∣X) for any X∈P′. According to Proposition 36, 𝒞(M(C))=𝒞(M(GP)). Therefore, M(C)=M(GP).


## 3.2. Type-2 Covering Cycle Matroid

In this section, type-2 covering cycle matroid is defined, and then the graphical representation of this type of covering cycle matroid is studied.Every connected plane graphG has a natural dual graph G* such that (G*)*=G. The dual is formed by associating a vertex of G* with each face of G and including a dual edge e* in G* for each edge e of G, such that the endpoints of the edge e* are the vertices for the faces on the two sides of e.In graph theory, a plane graph is a graph in which no edges cross each other. For any setX, a cycle graph GX induced by X has no edges cross each other, so the graph GX is a plane graph and has a dual graph. Since GX has two faces, its dual graph has only two vertices. In order to further understand the notion about a dual graph of a plane graph, an example is given in the following.Example 41 (continued from Example24).
As shown in Figure5, the dual graphs of the cycle graphs GK1, GK2, and GK3 are represented by Figures 5(a), 5(b), and 5(c), respectively.Dual graphs ofGK1, GK2 and GK3.
(a)
G
K
1
*
(b)
G
K
2
*
(c)
G
K
3
*Given a set, there are some different cycle graphs induced by the set, but these cycle graphs have the same dual graph. As we know that any edge in any cycle graph induced by the set has two faces, so all the dual graphs of these cycle graphs have only two vertices and any two edges of each dual graph form a cycle. That is to say, any two edges of each dual graph are adjacent. So these dual graphs are the same. When the set is a singleton, the cycle graph induced by the set is a loop. Since the edge of a loop has two faces, the dual graph of the loop has two vertices and an edge. That is to say, a singleton whose element is the edge of the dual graph of the loop is always a base of the matroid induced by this dual graph. Therefore, for a cycle graph, a singleton that consists of any edge of the dual graph of the cycle graph is a base of the matroid induced by the dual graph. Then the following proposition can be obtained.Proposition 42.
LetX be a subset of U, GX* the dual graph of a cycle graph induced by X, and M(GX*)=(U,I*(X)) the cycle matroid induced by GX*. Then B(M(GX*))={{x}∣x∈X}=B*(M(GX)).Proof.
According to Proposition13, Definitions 18 and 10, Proposition 20, and the notion of a dual graph of a plane graph, it is straightforward.The above proposition shows that a singleton consists of any element in the given set that is an independent set of the dual matroid of the cycle matroid, which is induced by a cycle graph. And this cycle graph is induced by the given set. According to Definition14, the following proposition can be obtained easily.Proposition 43.
LetC={K1,K2,…,Km} be a covering of U,  GKi* the dual graph of a cycle graph induced by Ki(1≤i≤m), and M(GKi*)=(Ki,I*(Ki)) the cycle matroid induced by GKi*. Then M′(C)=(U,I′(C)) is a matroid and it is denoted by M′(C)=∨i=1mM(GKi*), where I′(C)={∪i=1m{xKi}∣{xKi}⊆Ki}.Proof.
For anyxKi∈Ki, {xKi}≠∅. So according to Proposition 42, {xKi}∈B(M(GKi*)). Hence ∅, {xKi}∈I*(Ki). For any Ki∈C, we define a matroid on U as MKi⋆=(U,I*(Ki)), where MKi⋆∣Ki=M(GKi*) and U-Ki is a circuit of MKi⋆. Moreover ∅⊆Ki(1≤i≤m); so, according to Definition 14, {∪i=1m{xKi}∣{xKi}⊆Ki} is the set of all independent sets of the matroid ∨i=1mMKi⋆. Therefore M′(C)=∨i=1mM(GKi*)=∨i=1mMKi⋆; that is, M′(C) is a matroid.Definition 44 (type-2 covering cycle matroid).
LetC={K1,K2,…,Km} be a covering of U. Then M′(C)=∨i=1mM(GKi*) is called type-2 covering cycle matroid inducd by C.Example 45 (continued from Example41).
The dual matroids of three cycle matroids induced by three cycle graphs generated byK1, K2, and K3 are M(GK1*)=(K1,I*(K1)), M(GK2*)=(K2,I*(K2)) and M(GK3*)=(K3,I*(K3)). By direct computation, I*(K1)={∅,{e3}}, I*(K2)={∅,{e1},{e2},{e4}}, I*(K3)={∅,{e2},{e3}}. If M′(C)=(U,I′(C))=∨i=1mM(GKi*), then I′(C)={∅,{e1},{e2},{e3},{e4},{e1,e2},{e1,e3},{e2,e3},{e2,e4},{e3,e4},{e1,e2,e3},{e2,e3,e4}}.The following proposition shows relationships between the set of all bases of the type-2 covering cycle matroid induced by a covering and those blocks of the covering.Proposition 46.
LetC={K1,K2,…,Km} be a covering of U. If M′(C) is the type-2 covering cycle matroid induced by C, then B(M′(C))=Max{∪i=1m{xKi}∣xKi∈Ki}.Proof.
According to Proposition43, I′(C)={∪i=1m{xKi}∣{xKi}⊆Ki}. Since B(M′(C))=Max(I′(C)), B(M′(C))=Max{∪i=1m{xKi}∣{xKi}⊆Ki}=Max{∪i=1m{xKi}∣xKi∈Ki}.When a covering is a partition of the universe, relationships between the set of all bases of the type-2 covering cycle matroid and those blocks of the covering are investigated in the following proposition.Proposition 47.
LetC={K1,K2,…,Km} be a covering of U and M′(C) the type-2 covering cycle matroid induced by C. If C is a partition of U, then B(M′(C))={∪i=1m{xKi}∣xKi∈Ki}.Proof.
According to Proposition46, B(M′(C))=Max{∪i=1m{xKi}∣xKi∈Ki}. Since C is a partition of U, {xKi}∩{xKj}=∅ for any xKi∈Ki, xKj∈Kj(i,j∈{1,2,…,m}andi≠j). Hence B(M′(C))={∪i=1m{xKi}∣xKi∈Ki}.In the following proposition, we connect upper approximations with support sets of the type-2 covering cycle matroid. In fact, when a covering is a partition of a universe, a subset of the universe is a support set of the type-2 covering cycle matroid induced by the covering if and only if the upper approximation of the subset is equal to the universe.Proposition 48.
LetC={K1,K2,…,Km} be a covering of U and M′(C) the type-2 covering cycle matroid induced by C. If C is a partition of U, then S(M′(C))={X⊆U∣X+=U}.Proof.
For anyS∈S(M′(C)), according to Definition 12, there exists B∈B(M′(C)) such that B⊆S. Since C is a partition of U, according to Proposition 47, B(M′(C))={∪i=1m{xKi}∣xKi∈Ki}. Hence B∩Ki≠∅ for all Ki∈C. Since B⊆S, B∩Ki⊆S∩Ki, that is, S∩Ki≠∅ for all Ki∈C. Therefore, S+=U, that is, S(M′(C))⊆{X⊆U∣X+=U}. Conversely, for any X∈{X⊆U∣X+=U}, X+=U. Since C is a partition of U, X∩Ki≠∅ for all Ki∈C; that is, there exist xKi∈Ki(1≤i≤m) such that xKi∈X. Hence ∪i=1m{xKi}⊆X. Since C is a partition of U, according to Proposition 47, ∪i=1m{xKi}∈B(M′(C)). According to Definition 12, X∈S(M′(C)), that is, {X⊆U∣X+=U}⊆S(M′(C)). To sum up, this completes the proof.When a coveringC of a universe is not a partition of the universe, there exists a subset of the universe which is not the support set of M′(C) such that the upper approximation of the subset is equal to the universe.Example 49 (continued from Example45).
SinceB(M′(C))={{e1,e2,e3},{e2,e3,e4}}, there does not exist B∈B(M′(C)) such that B⊆{e1,e3,e4}. So {e1,e3,e4}∉S(M′(C)). But {e1,e3,e4}+=U.An equivalent formulation of the family of all circuits of the type-2 covering cycle matroid induced by a covering is provided by those blocks of the covering. In fact, when the covering is a partition of a universe, a subset of the universe is a circuit if and only if it is contained in a block of the covering and its cardinality is equal to 2.Proposition 50.
LetC={K1,K2,…,Km} be a partition of U and M′(C) the type-2 covering cycle matroid induced by C. Therefore 𝒞(M′(C))={X⊆U∣|X|=2 and ∃Ki∈Cs.t.X⊆Ki}.Proof.
SinceI′(C)={∪i=1m{xKi}∣{xKi}⊆Ki}, {x}∈I′(C) for any x∈U. For any X∈𝒞(M′(C)), X∈Min(Opp(I′(C))). If there exists Ki∈C such that X∩Ki≠∅, then |X∩Ki|≥2 since C is a partition of U. If Y⊆X∩Ki and |Y|=2, then Y⊆Ki and Y∉I′(C). So Y=X=X∩Ki. So there exists Ki∈C such that X⊆Ki and |X|=2, that is, X∈{X⊆U∣|X|=2 and ∃Ki∈Cs.t.X⊆Ki}. Conversely, for any Y∈{X⊆U∣|X|=2 and ∃Ki∈Cs.t.X⊆Ki}, there exists Ki∈C such that Y⊆Ki. Since C is a partition of U and |Y|=2, Y∉I′(C) and Z∈I′(C) for any Z⊂Y. So Y∈Min(Opp(I′(C))), that is, Y∈𝒞(M′(C)). To sum up, this completes the proof.A connected graph is constructed by the dual graphs of some cycle graphs through vertex identification. These cycle graphs are, respectively, induced by an element in a partition of a universe.Definition 51.
LetC be a partition of  U and GKi* the dual graph of a cycle graph induced by Ki(1≤i≤|C|). We define a graph by vertex identification of GK1*,GK2*,…, and GK|C|*, and this graph is denoted by GC. We say GC is a graph induced by C.An example about the operation of vertex identification of the dual graphs of the cycle graphs, which are, respectively, induced by an element of a partition, is shown in the following.Example 52.
LetU={e1,e2,e3,e4,e5} and C={K1,K2}, where K1={e3,e5}, K2={e1,e2,e4}. As shown in Figure 6, the dual graphs of two cycle graphs GK1 and GK2 are represented by Figures 6(a) and 6(b), respectively. Figure 7 is the representation of GC which is obtained by vertex identification of GK1* and GK2*.Graphs ofGK1* and GK2*.
(a)
G
K
1
*
(b)
G
K
2
*Figure 7
GraphGC obtained by vertex identification of GK1* and GK2*.Theorem40 shows the type-1 covering cycle matroid induced by any covering is graphic and a graph corresponding to the matroid is constructed by the covering via an indirect route. In the following theorem, we will discuss the relationship between a connected graph induced by a partition and the type-2 covering cycle matroid induced by the partition. It is obvious that there are some different graphs obtained by the partition through the operation of vertex identification. The cycles of each graph are the same while these graphs are different.Theorem 53.
LetC be a partition of  U, GC a graph obtained by vertex identification of GKi*(1≤i≤|C|), and M′(C) the type-2 covering cycle matroid induced by C. Then M′(C)=M(GC).Proof.
We need to prove only that𝒞(M′(C))=𝒞(M(GC)). For Ki(1≤i≤m), if Xi⊆Ki and |Xi|=2, then for any x∈Xi, x is a edge of GKi* and Xi is a cycle of GKi*. Therefore Xi is a cycle of GC. If Xi⊆Ki and |Xi|=1, then Xi∈B(M(GKi*)). According to Proposition 50, 𝒞(M′(C))=𝒞(M(GC)). Therefore, M′(C)=M(GC).For any coveringC of the universe, we want to know that whether the type-2 covering cycle matroid M′(C) is graphic. A counterexample is given in the following.Example 54.
LetU={e1,e2,e3,e4,e5}, C={K1,K2,K3} and M′(C) the type-2 covering cycle matroid induced by C, where K1={e1,e2,e3}, K2={e2,e3,e4}, K3={e5}. By direct computation, I′(M′(C))=Low{{e1,e2,e5}, {e1,e3,e5}, {e1,e4,e5}, {e2,e3,e5}, {e2,e4,e5}, {e3,e4,e5}}. If X={e1,e2,e3,e4}, then I(M′(C)∣X)=Low{{e1,e2},{e1,e3},{e1,e4},{e2,e3},{e2,e4},{e3,e4}}. So M′(C)∣X=U2,4. Hence M′(C) is not a graphic matroid.


## 4. Relationships between Three Kinds of Matroids

In this section, we study relationships between type-1 covering cycle matroid, type-2 covering cycle matroid, and function matroid.For a covering, we can induce two types of covering cycle matroids. Naturally, we will consider whether these two types of covering cycle matroids are equal. The following theorem shows that the type-1 covering cycle matroid induced by a covering is equal to the type-2 covering cycle matroid induced by the covering when the cardinality of every block of the covering is equal to two.Theorem 55.
LetC={K1,K2…,Km} be a covering of U. If for all Ki∈C, |Ki|=2, then M(C)=M′(C).Proof.
Since for allKi∈C,  |Ki|=2, then according to Definition 18 and Proposition 13, {xKi}∈I(Ki) for any {xKi}⊆Ki. For any xKi∈Ki, {xKi}∈B(M(GKi)).
According to Proposition22, I(C)={∪i=1m{xKi}∣{xKi}⊆Ki}=I′(C). Hence M(C)=M′(C).The upper approximation number provides a tool to quantify covering-based rough sets. The upper approximation number is defined as follows.Definition 56 (see [28, 29, 33]).
LetC be a covering of U. For all X⊆U,
(3)fC(X)=|{K∈C∣K∩X≠∅}|
is called the upper approximation number of X with respect to C. When there is no confusion, we omit the subscript C.In the following, a matroid is defined through the upper approximation number. We say that the matroid is the function matroid induced by the covering.Definition 57 (see [28, 29]).
LetC be a covering of  U. Then we say Mf(C)=(U,If(C)) a martoid where If(C)={I⊆U∣ for all I1⊆I,f(I1)≥|I1|}, which is called the function matroid induced by C.Given a covering, the upper approximation number of any base of the function matroid induced by the covering is equal to the cardinality of the covering.Proposition 58.
LetC be a covering of U, Mf(C) the function matroid induced by C, and Bf(C) the family of all the bases of Mf(C). For all B∈Bf(C), f(B)=|C|.Proof.
Iff(B)≠|C|, that is, there exists K∈C such that K∩B=∅, then for any x∈K, f(B∪{x})=|{K∈C∣K∩(B∪{x})≠∅}|≥f(B)+1≥|B|+1=|B∪{x}|. Since B∈Bf(C), B∈If(C). Hence f(I)≥|I| for any I⊆B. Therefore, for any I0⊆B∪{x}, if I0⊆B, then f(I0)≥|I0|. If I0⊈B, then there exists I∈B such that I∪{x}=I0, and f(I0)=|{K∈C∣K∩I0≠∅}|=|{K∈C∣K∩(I∪{x})≠∅}|≥f(I)+1≥|I|+1=|I0|. So B∪{x}∈If(C). Since |B∪{x}|>|B|, B is not a base of Mf(C), which is contradictory to B∈Bf(C). Therefore, f(B)=|C| for all B∈Bf(C).The following theorem shows that the function matroid induced by a covering is equal to the type-2 covering cycle matroid induced by the covering.Theorem 59.
LetC={K1,K2,…,Km} be a covering of U. Then Mf(C)=M′(C).Proof.
We need to prove onlyIf(C)=I′(C).(⇒):
LetBf(C) be the bases of the function matroid Mf(C). For any X∈If(C), there exists B∈Bf(C) such that X⊆B and B∈If(C). Hence |{Ki∈C∣Ki∩B≠∅}|=|C|≥|B|; that is, there exists {xKi}⊆Ki(1≤i≤m) such that {xKi}⊆B and B=∪i=1m{xKi}, that is, B∈I′(C). According to (I2) in Definition 7, I∈I′(C) for any I⊆B. Hence X∈I′(C); that is, If(C)⊆I′(C).(⇐):
For anyI∈I′(C), I′(C)={∪i=1m{xKi}∣{xKi}⊆Ki}. So f(I)=|{Ki∈C∣Ki∩I≠∅}|≥|I|. For any I1⊆I, I1∈I′(C). Hence f(I1)≥|I1|. Therefore, I∈{I⊆U∣ for all I1⊆I, f(I1)≥|I1|}. So I′(C)⊆If(C). To sum up, this completes the proof.The following corollary shows that the type-1 covering cycle matroid induced by a covering is equal to the function matroid induced by the covering when the cardinality of every block of the covering is equal to two.Corollary 60.
LetC be a covering of  U. If for all K∈C, |K|=2, then Mf(C)=M(C).Proof.
According to Theorems55 and 59, it is straightforward.For a coveringC, maybe people want to ask a question about the relationship between M(C) and M′(C) as follows: Could M(C) and M′(C) be dual matroids? Next, we will answer this question.Example 61 (continued from Examples24 and 45).
According to Examples24 and 45, B(M(C))={{e1,e2,e3},{e1,e2,e4},{e1,e3,e4},{e2,e3,e4}} and B(M′(C))={{e1,e2,e3},{e2,e3,e4}}. So Bc∉B(M′(C)) for any B∈B(M(C)). Therefore M(C) and M′(C) are not dual matroids.Example61 shows type-1 and type-2 covering cycle matroids induced by the same covering are not always dual. The following theorem shows that when a covering of a universe is a partition of the universe, these two types of covering cycle matroids induced by the covering are dual with each other.Theorem 62.
IfC is a partition of U, then M*(C)=M′(C).Proof.
According to Propositions26 and 47 and Definition 10, it is straightforward.


## 5. Conclusions

In this paper, we constructed two types of covering cycle matroids by a covering and studied the graphical representations of these two types of matriods. Some concepts of these two types of matroids were studied by those blocks of the covering, such as independent sets, bases, circuits, and support sets. We proved that the type-1 covering cycle matroid is a graphic matroid while the type-2 covering cycle matroid is not always a graphic matroid. These results provide a platform for studying covering-based rough sets through matroidal approaches. With the advantage of matroids, covering cycle matroid will help to develop some efficient algorithms for processing the data organized by coverings. In future, we will use both matroid theory and graph theory simultaneously to study rough set theory.



---

*Source: 539401-2013-06-05.xml*