Volume 2012, Article ID 973920,27pages doi:10.1155/2012/973920
Research Article
Matroidal Structure of Rough Sets from the Viewpoint of Graph Theory
Jianguo Tang,
1, 2Kun She,
1and William Zhu
31School of Computer Science and Engineering, University of Electronic Science and Technology of China, Chengdu 611731, China
2School of Computer Science and Engineering, XinJiang University of Finance and Economics, Urumqi 830012, China
3Lab of Granular Computing, Zhangzhou Normal University, Zhangzhou 363000, China
Correspondence should be addressed to William Zhu,williamfengzhu@gmail.com Received 4 February 2012; Revised 30 April 2012; Accepted 18 May 2012
Academic Editor: Mehmet Sezer
Copyrightq2012 Jianguo Tang et al. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
Constructing structures with other mathematical theories is an important research field of rough sets. As one mathematical theory on sets, matroids possess a sophisticated structure. This paper builds a bridge between rough sets and matroids and establishes the matroidal structure of rough sets. In order to understand intuitively the relationships between these two theories, we study this problem from the viewpoint of graph theory. Therefore, any partition of the universe can be represented by a family of complete graphs or cycles. Then two different kinds of matroids are constructed and some matroidal characteristics of them are discussed, respectively. The lower and the upper approximations are formulated with these matroidal characteristics. Some new properties, which have not been found in rough sets, are obtained. Furthermore, by defining the concept of lower approximation number, the rank function of some subset of the universe and the approximations of the subset are connected. Finally, the relationships between the two types of matroids are discussed, and the result shows that they are just dual matroids.
1. Introduction
Rough sets provide an important tool to deal with data characterized by uncertainty and vagueness. Since it was proposed by Pawlak1,2, rough sets have been generalized from different viewpoints such as the similarity relation3,4or the tolerance relations5instead of the equivalence relation, and a covering over the universe instead of a partition6–10, and the neighborhood instead of the equivalence class11–14. Besides, using some other mathematical theories, such as fuzzy sets15–19, boolean algebra20–23, topology24–27, lattice theory28–30, and modal logic31, to study rough sets has became another kind
of important generalizations of rough sets. Specially, matroids also have been used to study rough sets recently32,33.
Matroids, as a simultaneous generalization of graph theory and linear algebra, was proposed by Whitney in 34. 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 spaces35. It has been found that matroids are effective to simplify various ideas in graph theory and are useful in combinatorial optimization problems.
In the existing works on the combination of rough sets and matroids, Zhu and Wang 32constructed a matroid by defining the concepts of upper approximation number in rough sets. Then they studied the generalized rough sets with matroidal approaches. As a result, some unique properties are obtained in this way. Wang et al. 33 studied the covering- based rough sets with matroids. Two matroidal structures of covering-based rough sets are established.
In this paper, we attempt to make a further contribution to studying rough sets with matroids. As we see inSection 2.3, it is somewhat hard to understand matroids. And this will also arise in the combination of matroids and rough sets. So, in order to give an intuitive interpreting to the combination, we will study it from the viewpoint of graph theory. There are at least two kinds of graphic ways, which can be used to build relationships between matroids and rough sets. The complete graph and the cycle. More specifically, for a partition over the universe, any equivalence class of the partition can be regarded as a complete graph or a cycle. Thus a partition is transformed to a graph composed of these complete graphs or circles induced by the equivalence classes of the partition. And we can establish a matroid in terms of the graph. Afterwards, some characteristics of the matroid are formulated and some new properties, which are hard to be found via the rough sets way, are obtained. With these characteristics and properties, a matroidal structure of rough sets is constructed. Finally, the relationships between the two kinds of matroids established from the viewpoints of complete graph and cycle are discussed.
The rest of this paper is organized as follows. In Section 2, we review some basic knowledge about rough sets, matroids, and graph theory. In Section 3, we analyze the relationships between rough set theory and graph theory from the viewpoints of complete graph and cycle, respectively. In Sections4and5, two kinds of matroids are established in terms of the analytical results ofSection 3. And two kinds of the matroidal structures of rough sets are constructed. InSection 6, the relationships between the two kinds of matroids are discussed.
2. Preliminary
For a better understanding to this paper, in this section, some basic knowledge of rough sets, graph theory, and matroids are introduced.
2.1. Rough Sets
LetUbe a nonempty and finite set called universe, R a family of equivalence relations over U, then the relational systemK U,Ris called a knowledge base1. If∅/Q⊆ R, then∩Q is also an equivalence relation1. And∩Q is called an indiscernibility relation and denoted by INDQ 1. If R ∈ R, then U/Rrepresents the partition of Uinduced byR. That is in
the partitionU/R {T1, T2, . . . , Tn}, for allTi ∈U/R,Ti ⊆UandTi/∅,Ti ∩ Tj ∅fori /j, i, j1,2, . . . , n, and∪TiU. EachTiinU/Ris an equivalence class, and it can also be denoted byxRifx∈Ti.
For any subsetX⊆U, the lower and the upper approximations ofXwith respect toR are defined as follows1:
RX ∪ {T ∈U/R:T⊆X}, RX ∪ {T ∈U/R:T∩X /∅}.
2.1
SetBNRX RX−RXis called theR-boundary ofX or the boundary region ofXwith respect toR1. IfRX RX, that is,BNRX ∅, thenX isR-definable, orX is called a definable set with respect to R; else, if RX/RX, that is, BNRX/∅, thenX is rough with respect toR, orX is called a rough set with respect toR1. The lower and the upper approximations satisfy duality, that is1,
P1for allX⊆U,RX ∼R∼X, P2for allX⊆U,RX ∼R∼X, where∼Xrepresents the setU−X.
Neighborhood and upper approximation number are another two important concepts, which will be used in this paper. They are defined as follows.
Definition 2.1Neighborhood36. LetRbe a relation onU. For allx∈U,RNRx {y ∈ U:xRy}is called the successor neighborhood ofxinR. When there is no confusion, we omit the subscriptR.
Definition 2.2Upper approximation number32. LetRbe a relation onU. For allX ⊆U, fR∗X |{RNRx:x∈U∧RNRx∩X /∅}|is called the upper approximation number of Xwith respect toR.
2.2. Graph Theory
A graphGis an ordered pair of disjoint sets V, Esuch that Eis a subset of the setV2 of unordered pairs ofV 37. The setV is the set of vertices andEis the set of edges. IfG is a graph, thenV VGis the vertex set of G, andE EGis the edge set. An empty graph is a graph whose edge set is empty. An edge{u, v}is said to join the verticesuand vand is denoted by uv. Thusuv and vumean exactly the same edge; the vertices u and vare the endpoints of this edge. Ifuv ∈ EG, thenuand vare adjacent and are neighbors. A loop 38is an edge whose endpoints are equal. Parallel edges are edges having the same pair of endpoints. The degree of vertexvin a graphG, denoted bydGvordv, is the number of edges incident tov, except that each loop atvcounts twice.
A simple graph is a graph having no loops or parallel edges38. An isomorphism38 from a simple graph G to a simple graphH is a bijectionf : VG → VH such that uv ∈EGif and only iffufv∈EH. That is to say “Gis isomorphic toH,” denoted by G∼Hif there is an isomorphism fromGtoH.
We say thatG V, Eis a subgraph ofG V, EifV ⊂V andE ⊂E37. In this case, we writeG⊂G. IfGcontains all edges ofGthat join two vertices inVthenGis said
to be the subgraph induced byVand is denoted by GV. Thus, a subgraphG ofG is an induced subgraph ifGGVG.
2.3. Matroids
Definition 2.3Matroid39. A matroidMis a pairE,I, whereEcalled the ground set is a finite set andIcalled the independent setsis a family of subsets of Esatisfying the following axioms:
I1∅ ∈ I;
I2ifI ∈ IandI⊆I, thenI∈ I;
I3ifI1, I2∈ Iand|I1|<|I2|, then∃e∈I2−I1such thatI1∪ {e} ∈ I, where| · |represents the cardinality of “·”.
The matroidMis generally denoted byM ME,I.EMrepresents the ground set ofMandIMthe independent sets ofM. Each element ofIMis called an independent set ofM. If a subsetX ofEis not an independent set, then it is called a dependent set. The family of all dependent sets ofMis denoted byDM, that is,
DM 2E− IM. 2.2
Example 2.4. LetE {a, b, c}, I {{a, b},{b, c},{a},{b},{c},∅}. ThenE,Iis a matroid, which satisfies the axiomsI1∼I3. And each element ofIis an independent set.{a, b, c}
and{a, c}are only two dependent sets ofE,I.
Next, we will introduce some characteristics of a matroid. For a better understanding to them, some operations will be firstly introduced as follows.
LetEbe a set andA ⊆2E. Then39:
MaxA {X ∈ A:∀Y ∈ A, if X⊆Y thenXY}, MinA {X ∈ A:∀Y ∈ A, if Y ⊆X thenXY}, OppA {X ⊆E:X /∈ A},
ComA {X ⊆E:E−X∈ A}.
2.3
Definition 2.5Circuit39. LetMbe a matroid. A minimal dependent set is called a circuit ofM, and the set of all circuits ofMis denoted byCM, that is,CM MinOppI.
A circuit in a matroidME,Iis a set which is not independent but has the property that every proper subset of it is independent. InExample 2.4,CM {{a, c}}.
Theorem 2.6Circuit axioms39. LetCbe a family of subsets ofE. Then there existsME,I such thatCCMif and if onlyCsatisfies the following properties:
C1∅∈ C;/
C2ifC1, C2∈ CandC1 ⊆C2, thenC1C2;
C3ifC1, C2∈ C,C1/C2, and∃e∈C1∩C2, then∃C3∈ Csuch thatC3 ⊆C1∪C2− {e}.
Definition 2.7Base39. LetMbe a matroid. A maximal independent set ofMis called a base ofM; the set of all bases ofMis denoted byBM, that is,BM MaxI.
InExample 2.4, according toDefinition 2.7, we can get thatBM {{a, b},{b, c}}.
It is obvious that all bases of a matroid have the same cardinality, which is called the rank of the matroid.
Definition 2.8Rank function39. LetM ME,Ibe a matroid. Then the rank function rMofMis defined as: for allX⊆E,
rMX max{|I|:I∈ I ∧I ⊆X}. 2.4
A matroid can be determined by its base, its rank function, or its circuit. For a set,I⊆E is independent if and only if it is contained in some base, if and only if it satisfiesrMI |I|, or if and only if it contains no circuit. It is possible to axiomatize matroids in terms of their sets of bases, their rank functions, or their sets of circuits40.
Definition 2.9 Closure 39. LetM ME,I be a matroid. For all X ⊆ E, the closure operator clMofMis defined as follows:
clMX {e∈E:rMX rMX∪ {e}}. 2.5
Ife ∈ clMX, we say that e depends onX. The closure of X is composed of these elements ofEthat depend onX. If clMX X, thenXis called a closed set ofM.
Definition 2.10Hyperplane39. LetM E,Ibe a matroid.H⊆Eis called a hyperplane ofMifHis a closed set ofMandrMH rME−1. AndHMrepresents the family of all hyperplanes ofM.
3. The Viewpoint of Graph Theory in Rough Sets
Graph theory provides an intuitive way to interpret and comprehend a number of practical and theoretical problems. Here, we will make use of it to interpret rough sets. There are at least two different ways to understand rough sets from the viewpoint of graph theory: the complete graph and the cycle. This will be analyzed in detail in the following subsections.
3.1. The Complete Graph
Definition 3.1Complete graph38. A complete graph is a simple undirected graph whose vertices are pairwise adjacent. A complete graph whose cardinality of vertex set is equal ton is denoted byKn.
In rough sets, an equivalence relation can generally be regarded as an indiscernibility relation. That means any two different elements in the same equivalence class are indis- cernible. In order to interpret this phenomenon from the viewpoint of graph theory, we can consider the two elements as two vertices and the indiscernibility relation between them as an edge connecting the two vertices. Then an equivalence class is represented by a complete graph. For a better understanding of it, an example is served as follows.
a b c
d
h e
f g
(a) (b) (c)
Figure 1: The complete graphs of equivalence classes.
Example 3.2. Let U {a, b, c, d, e, f, g, h} be the universe, R an equivalence relation, and U/R {T1, T2, T3} {{a},{b, c},{d, e, f, g, h}}. Then each equivalence class can be transformed to a complete graph showed inFigure 1.
Figure 1a represents the complete graph of the equivalence class T1. Because T1 just includes one element a, there is only one vertex and no edge in the complete graph Figure 1a.Figure 1brepresents the complete graph ofT2, which includes two vertices and only one edge connecting the two vertices. AndFigure 1crepresents the complete graph of T3. We can find that there are five vertices inFigure 1cand each pair of vertices are con- nected by an edge. Here, we denote the complete graphs Figures1a,1b, and1casK|T1|, K|T2|, andK|T3|, respectively.
From the above example, for any two elements in the universe, if they are indiscernible then there is one edge between them. Then the partition is transformed to be a graphG U, E, where
EP
xy:x∈T ∈P∧y∈T− {x}
. 3.1
It is obvious that ifxandybelong to the same equivalence class, then there is an edge xyinE. So, we can formulate the equivalence class as follows: for allx∈U,
xR {x} ∪
y:xy∈E
. 3.2
Furthermore, for any subsetX⊆U, the lower and the upper approximations ofXcan be formulated as follows:
RX ∪ {T ∈U/R:GT⊂GX}, RX ∪
T∈U/R:∃Y ⊆T s.t. K|T|Y⊂GX .
3.3
3.2. The Cycle
A walk 37 W in a graph is an alternating sequence of vertices and edges, say x0, e1, x1, e2, . . . , el, xlwhereei xi−1xi, 0< i ≤ l. For simplicity, the walkWcan also be denoted byx0x1· · ·xl; the length ofWisl, that is, the number of its edges. A walk that starts and ends
a a
b c
b
d
h e
f g
c Figure 2: The cycles of equivalence classes.
at the same vertex but otherwise has no repeated vertices is called a cycle41. A cycle on one vertex consists of a single vertex with a loop, and a cycle on two vertices consists of two vertices joined by a pair of parallel edges42.
Then, how to build a bridge between rough sets and cycle? In rough sets, elements contained in the same equivalence class are indiscernible, and any proper subset of an equivalence class is no longer an equivalence class. So, we can convert an equivalence class to a cycle whose vertices set is the equivalence class. Therefore, each vertex is connected with all vertices in the cycle42. This reflects the indiscernible relationship among the elements of an equivalence class. Furthermore, any subgraph of the cycle does not contain a cycle. That is, any subgraph of the cycle is no longer a cycle. This can be illustrated in the following example.
Example 3.3 Continued from Example 3.2. For any equivalence class in U/R, it can be represented by a cycle. As shown in Figure 2, the equivalence class T1, T2, and T3 are represented by Figures2a,2b, and2c, respectively.
Figure 2ais a cycle with only one vertex and one edge. It is also called a loop. That means the vertexais connected with itself.Figure 2bis a cycle with two vertices and two edges. And it is generally regarded as a parallel edges.Figure 2cis not only a cycle but also a simple graph. Obviously, any subgraph of each cycle inFigure 2is no longer a cycle. And, for any two different elements of the universe, they belong to the same equivalence class if and only if they are connected to each other.
It is worth noting that the sequence of vertices in a cycle is not emphasized here. We only care that the vertices, namely, elements of some equivalence class, can form a cycle. So, toFigure 2c, the cycledefghdand cycledfhegdcan be treated as the same cycle.
For convenience, to an equivalence classTinU/R, the cycle whose vertices set is equal toT is denoted byCT, that is,CT T, ETis a graphcyclewhereET is the set of edges of CT. Then the partitionU/Rcan be transformed to be a graphG U, Ewhere
E∪{ET:T ∈U/R}. 3.4
One may ask which edges belong toETexactly? In fact, it is nonnecessary to define the edges ofETexactly. Here, we just need to form a cycle with the vertex setT. That is, each pair of vertices ofT are connected and the degree of each vertex is equal to 2. In other words, we simply need to know that each vertex ofCT is adjacent with two other verticesexcept the loop and parallel edgesand do not need to care which two vertices they are.
We can find from the Example 3.3 that, for any two elements in the universe, they belong to the same equivalence class if and only if they are connected with each other.
Therefore, we can formulate the equivalence class as follows: for allx∈U, xR
y∈U:y is connected tox
. 3.5
Likewise, for any subsetX ⊆U, the lower and the upper approximations ofXcan be formulated as follows:
RX ∪ {T ∈U/R:CT ⊂GX},
RX ∪ {T ∈U/R:∃Y ⊆T s.t. CTY⊂GX}. 3.6
So far, rough sets are interpreted from the viewpoints of complete graph and cycle, respectively. The above analysis shows that there are some similarities, and also some differ- ences, between the two ways to illustrate rough sets. Because there are closed connections between graph theory and matroid theory, we will study the matroidal structure of rough sets through the two kinds of graphs.
4. Matroidal Structure of Rough Sets Constructed from the Viewpoint of Complete Graph
InSection 3, we discussed rough sets from the viewpoint of graph theory. Two graphic ways are provided to describe rough sets. In this section, we will construct two types of matroidal structures of rough sets. One of them is established by using the principle of complete graph and the other of cycle.
For convenience, in this section, we suppose thatUis the universe,Ran equivalence relation over Uand P U/Rthe partition. AndGP U, EPis the graph induced byP, whereEP {xy:x∈T ∈P∧y∈T− {x}}.
4.1. The First Type of Matroidal Structure of Rough Sets
We know that a complete graph is a simple graph. Then, for any vertexvof a complete graph, there is not a loop whose vertex isv. That is to say there is not an edge between a vertex and itself. Furthermore, for any two vertices coming from different complete graphs, there is not an edge between them as well. Because an equivalence class can be represented by a complete graph, we can construct the matroidal structure of rough sets from this perspective.
In this subsection, the first type of matroid induced by a partition will be established and defined. And then some characteristics of it such as the base, circuit, rank function, and closure are studied.
Proposition 4.1. LetIP {X ⊆U:GPXis an empty graph}. Then there is a matroidMonU such thatIM IP.
Proof. According toDefinition 2.3, we just need to prove thatIP satisfies axiomsI1∼I3. It is obvious thatI1andI2hold. Suppose thatX, Y ∈ IP and|X|<|Y|. BecauseGPXand GPYare empty graphs, according to the definition ofEP, eachx∈Xbelongs to a different equivalence class with the others ofXand the same to eachy∈Y. Since|X|<|Y|, thus there must be at least one elementy0 ∈ Y such that y0 belongs to some equivalence class which does not include any element ofX. Therefore,X ∪ {y0} ∈ IP. As a result,IP satisfiesI3.
That is, there exists a matroidMonUsuch thatIM IP.
IfGXis an empty graph, then it means that any two different vertices ofGXare nonadjacent. That is, each vertex ofGXcomes from a different complete graph with others.
For instance, inExample 3.2, we can getIP as follows:
IP
∅,{a},{b},{c},{d},{e}, f
, g
,{h},{a, b},{a, c},{a, d},{a, e}, a, f
, a, g
, {a, h},{b, d},{b, e},
b, f ,
b, g
,{b, h},{c, d},{c, e}, c, f
, c, g
,{c, h},{a, b, d}, {a, b, e},
a, b, f ,
a, b, g
,{a, b, h},{a, c, d},{a, c, e}, a, c, f
, a, c, g
,{a, c, h}
. 4.1
Definition 4.2 The first type of matroid induced by a partition. The first type of matroid induced by a partitionP overU, denoted byI-MIP, is such a matroid whose ground set EUand independent setsI{X⊆U:GPXis an empty graph}.
Obviously, matroids proposed inProposition 4.1is aI-MIP. From the above result of IP, we can find that any two elements ofXcome from different equivalence class. Therefore, we can get the following proposition.
Proposition 4.3. LetMP U,IPbe anI-MIP. Then for allX ⊆ U,X ∈ IP if and only if for allT ∈Psuch that|X∩T| ≤1.
Proof. ⇒: IfX ∈ IP, thenGPXis an empty graph. According to the definition ofEP, each element ofXcomes from a different equivalence class with the others ofX. That is, for all T ∈P,|X∩T| ≤1.
⇐: LetX ⊆U. If for allT ∈P,|X∩T| ≤1, thenGPXis an empty graph. Therefore, X∈ IP.
A matroid can be determined by its base, its rank function, or its circuit. So it is possible to axiomatize matroids in terms of their sets of bases, their rank functions, or their sets of circuits40. Here we will axiomatize theI-MIPin terms of its circuit.
Theorem 4.4. LetMbe a matroid induced byP. ThenMis anI-MIP if and only if for allC∈ CM,
|C|2.
Proof. According toDefinition 2.3, we know thatIM⊆2U. IfIM 2U, thenMis aI-MIP induced byP {{x} :x∈ U}. In this case, according to2.2,DM ∅andCM ∅. It indicates that there is not any circuit inCM, and, therefore, we do not need to care whether the cardinality of each circuit ofCMis equal to 2. That is, CM ∅ is compatible with
the description that for allC ∈ CM,|C| 2. Similarly, if CM ∅, thenM is aI-MIP induced byP {{x}:x∈U}. So,Theorem 4.4is true when the set of circuits ofMis empty.
Next, we prove thatTheorem 4.4is true when the set of circuits ofMis nonempty.
⇒: According to 2.2,DM 2U− IP. Therefore, in terms ofDefinition 4.2and Proposition 4.1, for allX ⊆U,X∈ DMif and only ifGPXis not an empty graph. That is, there is at least one edge inGPX. Obviously, the set of endpoints of each edge ofGPXis a dependent set. So, for allX ∈ DM, there is a setYcomposed of the endpoints of some edge ofGPXsuch thatY ⊆X. According toDefinition 2.5,Y ∈ CMandX /∈ CM. That is, for allC∈ CM,|C|2.
⇐:DM {X⊆U:∃C∈ CMs.t. C⊆X}. According to2.2,IM 2U−DM.
Therefore, for allI ∈ IM,C∈ CMsuch thatC⊆I, that is, for allC∈ CM,|C ∩ I| ≤1.
So, for allC1, C2 ∈ CM; ifI∩ C1/∅, thenI ∩ C2C1 ∩ C2. According toTheorem 2.6, if C1 ∩C2/∅, then∃C3 ∈ CMsuch thatC3 C1 ∪ C2 −C1∩C2. For allCi∈ CM, letTCi {C∈ CM:C∩ Ci/∅}. Then|I∩TC1|1. Furthermore, ifC1 ∩ C2∅, thenTC1 ∩ TC2∅.
If for allC ∈ CM,I ∩ C ∅, then for all y ∈ I,C ∈ CMsuch that y ∈ C. Thus, PCM {TCi :Ci∈ CM} ∪ {{y}:y∈U − ∪CM}is a partition overU. SoIM {I ⊆ U: for allX∈PCM, |I ∩ X| ≤1}. According toDefinition 4.2,M U,Iis aI-MIP.
Summing up,Theorem 4.4is true.
In terms ofProposition 4.1, we can get a matroid induced by a partition. Then one may ask whether there is a bijection between a partition and theI-MIPinduced by the partition.
This question will be answered by the following theorem.
Theorem 4.5. LetP be the collection of all partitions overU,Mthe set of all I-MIP induced by partitions ofP,f:P → M, that is, for allP ∈ P,fP MP, whereMP is theI-MIP induced by P. Thenfsatisfies the following conditions:
1for allP1, P2∈ P, and ifP1/P2thenfP1/fP2, 2for allM∈ M,∃PM∈ Ps.t.fPM M.
Proof. 1LetP1, P2 ∈ P,P1/P2, andMP1 U,IP1,MP2 U,IP2are twoI-MIP induced byP1 andP2, respectively. We need to prove that there is anI1 ∈ IP1 such thatI1 ∈ I/ P2, or there is anI2 ∈ IP2such thatI2 ∈ I/ P1. BecauseP1/P2, there is at least one equivalence class T1 ∈P1 such thatT1 ∈/P2. If∃T2 ∈P2such thatT1 ⊂T2, then∃X ⊆UandX ∈ IP1 such that X∩T2−T1/∅. That meansX /∈ IP2. Else, there at least two equivalence classesT2i, T2j ∈P2 such thatT2i∩T1/∅andT2j∩T1/∅. That is, there is a setY ∈ IP2such thatY∩T2i∩T1/∅and Y∩T2j∩T1/∅. Obviously, according toProposition 4.3,Y /∈ IP1.
2LetM U,Ibe aI-MIP, for allx∈U,Cx{x} ∪∪{C∈ CM:C∩ {x}/∅}.
According toTheorem 4.4, for ally∈Uandy /∈Cx, thenCx∩Cy∅. Therefore, we can get a familyCU{Cx:x∈U}. It is obvious that∪CUU. Therefore,CUis a partition ofU. That is,CU∈ PandfCU M.
Theorem 4.5shows that there is one-to-one correspondence between a partition and theI-MIPinduced by the partition.
4.2. Characteristics of I-MIP
The characteristics of a matroid are very important to describe the matroid from different aspects. In this subsection, we will study the characteristics ofI-MIPsuch as the base, circuit, rank function, and closure.
The set of bases of a matroid is the collection of all maximal independent sets.
Observing from the result of IP in Section 4.1, the maximal independent set is the vertex set whose cardinality is equal to the cardinality ofP. Then the following proposition can be obtained.
Proposition 4.6. LetMP be theI-MIP induced byP,Y ⊆U, andGPY Y, EYa subgraph of GP. ThenBP {X⊆U:|X||P| ∧EX∅}is the set of bases ofMP.
Proof. According toDefinition 2.7, we need to prove thatBMP BP, namely, MaxIP
{X ⊆ U :|X| |P| ∧EX ∅}. In terms of Proposition 4.3, for allI ∈ IP,|I ∩T| ≤ 1 for all T ∈P. So, for allI∈ BMP,|I||P|. According toProposition 4.1andDefinition 4.2, for all I∈ BMP,GPIis an empty graph, that is,I ∈ BP. Similarly, we can prove in the same way that for allX ∈ BP,X∈ BMP. That is,BMP BP.
For a baseBinBP, we can say thatBis such a set including one and only one element of every equivalence class ofP. Then we can get the following corollary.
Corollary 4.7. LetX ⊆U. ThenX∈ BP if and only if for allT ∈P,|X∩T|1.
Proof. According toProposition 4.6, it is straightforward.
Corollary 4.8. ∪BP U.
Proof. According toProposition 4.6, it is straightforward.
For a subsetX ofU,X is either an independent set or a dependent set of MP. And so the opposition to theProposition 4.1,X is a dependent set if and only if there is at least one pair of vertices of the vertex set ofGPX, which is adjacent. Furthermore, a minimal dependent set of MP is the vertex set of an edge of GP. Then we can get the following proposition.
Proposition 4.9. LetMP U,IPbe theI-MIP induced byP. ThenCP {{x, y}:xy∈EP}is the set of circuits ofMP.
Proof. According toDefinition 2.5, we need to proveCMP CP, that is, MinOppIP
{{x, y}:xy ∈EP}.DM OppIP, for allI ∈ DM,∃x, y ∈Isuch thatxy∈ EGPI.
Furthermore,xy∈EP. If{x, y} ⊂ I, then{x, y} ∈ CMPandI /∈ CMP; else,{x, y} I ∈ CMP. So, for allI ∈ CMP,I ∈ CP. Similarly, for all{x, y} ∈ CP,∃I ∈ DMPsuch that {x, y} ⊆I. Therefore,{x, y} ∈ CMP. As a result,CP {{x, y}:xy∈EP}.
Likewise, Proposition 4.3 provides a necessary and sufficient condition to decide whether a set is an independent set ofMP. In this way, we can get the family of dependent sets ofMP as follows:
DMP {X⊆U:∃T ∈P s.t.|X∩T|>1}. 4.2
Moreover, in terms of theDefinition 2.5, we can get the set of circuits ofMPas follows:
CMP MinDMP. 4.3
According toProposition 4.1, it can be found that each subset of Uwhich contains exactly one element is an independent set. So, for any dependent setXofMP, if|X|>2 then there must exist a subsetYofXsuch that|Y|2 andY is a dependent set. Thus, we can get the following proposition.
Proposition 4.10. LetMP be theI-MIP induced byP. ThenC {X ⊆ U : ∃T ∈ P s.t.X ⊆ T∧ |X|2}is the set of circuits ofMP.
Proof. According to Proposition 4.3, for all X ∈ C , X is a dependent set, that is, X ∈ DMP. In terms ofProposition 4.9,X ∈ CMP. Similarly, for allI ∈ CMP, according to Proposition 4.9,I∈ C . That is,C is the set of circuits ofMP.
From Propositions4.9and4.10, we can find thatCP and C are the set of circuits of MP. Therefore, we can get the following corollary.
Corollary 4.11. CP C .
Propositions 4.1 and 4.3provide two ways to transform an partition to a matroid.
Then, how to convert anI-MIP to a partition? In the following proposition, this question is answered through the set of circuits of theI-MIP.
Proposition 4.12. LetMPbe theI-MIP induced byP. Then for allx∈U, xR {x} ∪
y∈U: x, y
∈ CMP
. 4.4
Proof. According toProposition 4.10, for allT ∈ P, ifx ∈ T then{x, y} ∈ CMPfor each y∈T− {x}. And for anyy∈Uandy /∈T,{x, y}/∈ CMP. Therefore,T xR {x} ∪ {y∈ U:{x, y} ∈ CMP}.
Proposition 4.12shows that if two different elements form a circuit, then they belong to the same equivalence class. In terms of3.2, there is an edge inEP whose vertex set just contains the two elements. For a subsetX ⊆ U, ifX does not contain a circuit, thenX is an independent set and the rank of it is equal to|X|. In other words, ifGPXis an empty graph, that is, each pair of vertexes ofGPXis nonadjacent, then the rank ofX is equal to
|X|. According toDefinition 2.8, for any subset of the universe, the rank of the subset is the number of the maximal independent set contained in the subset. Therefore, we can get the following proposition.
Proposition 4.13. LetMPbe theI-MIP induced byP. Then for allX⊆U,rPX max{|Y|:Y ⊆ X, GPYis an empty graph}is the rank ofXinMP.
If the set of basesBMP ofMP has been obtained, then for allX ⊆ U; we can get the rank ofXas follows:
r X max{|B∩X|:B∈ BMP}. 4.5
It can be proved easily thatrPX r X. So,r is also the rank function ofMP. Different from the rank ofXinMP, the closure ofXis the maximal subset ofU, which containsXand its rank is equal toX. For an elementy∈U−X, if there is an elementx∈X
such that{x, y}form a circuit, then the rank ofXis equal to it ofX∪ {y}. That is,ybelongs to the closure ofX. Therefore, we can get the following proposition.
Proposition 4.14. LetMP be theI-MIP induced byP. Then for allX ⊆ U, clPX X∪ {y ∈ U−X:x∈X∧xy∈EP}is the closure ofXinMP.
Proof. According toDefinition 2.9, we need to prove that clPX clMPX, that is,X∪ {y∈ U−X:x∈X∧xy∈EP}{x∈U:rMPX rMPX∪ {x}}. It is obvious that, for allX⊆U, X ⊆ clPX. So, we just need to prove that for all y ∈ U−X if there is an elementx ∈ X such thatxy∈ EP if and if onlyy ∈ {x ∈U :rMPX rMPX∪ {x}}. According to3.1, xy ∈EP if and if onlyxandybelong to the same equivalence. According toDefinition 2.8, for allX⊆U,rMPXis equal to the number of the maximal independent set contained inX.
According toProposition 4.3, for allX⊆X; ifXis a maximal independent set contained inX, thenX ∪ {y}is not an independent set. That is,rMPX |X|rMPX∪{y} rMPX∪{y}.
Thus, for allx∈U,x∈clPXif and if onlyx∈ {x∈U:rMPX rMPX∪ {x}}.
From Proposition 4.14, it can be found that, for any element y ∈ U −X, if xy ∈ EGPX, theny∈clPX. Therefore, the closure ofXcan be equivalently represented as
clPX X∪
y∈U−X :xy∈EGPX
. 4.6
For any elementx∈U, according toFigure 1, it can be found that if there is an element y∈U− {x}such thatxy∈EP, thenxandymust belong to the same equivalence class. Then we can get the following corollary.
Corollary 4.15. Letx∈U. For allT ∈P; ifx∈T then clP{x} clPT.
Next, we will discuss the hyperplane of theI-MIP. From theDefinition 2.10, we know that a hyperplane of a matroid is a closed set and the rank of it is one less than the rank of the matroid. Because the rank of theI-MIP induced byPis equal to the cardinality ofP, we can get the following proposition.
Proposition 4.16. Let MP be theI-MIP induced by P. Then HP {U − T : T ∈ P} is the hyperplane ofMP.
Proof. According to4.5andProposition 4.6, we know that the rank of theI-MIP induced byPis equal to|P|. Furthermore, in terms ofProposition 4.14andCorollary 4.15, for allT ∈P, U−T is a closed set andrMPU−T |P| −1. SoU−T ∈ HMP, that is, for allX ∈ HP, X∈ HMP. Similarly, we can get that for allX∈ HMP,X∈ HP.
4.3. Approximations Established through I-MIP
So far, the base, circuit, rank function, closure, and hyperplane of aI-MIP are established.
Next, we will further study the approximations in rough sets in this subsection through these characteristics.
Proposition 4.17. LetMPbe theI-MIP induced byP,BMP BP. Then for allX ⊆U,
RX ∪{B−BX−X:B∈ BP∧BX−X⊆B}, 4.7
whereBX∈ BP a base having the maximal intersection withX.
Proof. For all B ∈ BP, B∩X is an independent set contained in X. Because BX is a base having the maximal intersection withX,rMPX |BX∩X|. Furthermore, for ally∈BX−X, yR∩X ∅. LetS1 {yR : y ∈BX−X}andS2 P−S1. ThenRX U− ∪S1 ∪S2. IfBX−X ⊆ B, thenB−BX−X ⊆ ∪S2. According toCorollary 4.7, for allY ⊆ ∪S2, if for all T ∈ P −S2and |Y ∩T| 1, then Y ∪BX−X ∈ BP. And∪{Y ⊆ ∪S2 : for allT ∈ P−S2,|Y∩T|1}∪S2. Therefore,∪S2 ∪{B−BX−X:B∈ BP ∧BX−X⊆B}. That is,RX ∪{B−BX−X:B∈ BP∧BX−X⊆B}.
In rough sets, an element in the lower approximation certainly belongs toX, while an element in the upper approximation possibly belongs toX43. And the boundary region of Xis the set of elements in which each element does not certainly belong to eitherXor∼X.
In general, we can get the boundary region ofXby the difference set of the lower and upper approximation ofX. But here, we can provide a matroidal approach to obtain the boundary region ofXfirstly, and then the lower and the upper approximations should be established.
Proposition 4.18. LetMPbe theI-MIP induced byP,CMP CP. Then for allX⊆U,
BNRX ∪{C∈ CP :|C∩X|1}. 4.8
Proof. According to Proposition 4.10andCorollary 4.11, for allC ∈ CP, ∃T ∈ P such that C⊆ T.|C∩X|1 means that each element ofCdoes not certainly belong either toXor to
∼X. And then∪{C∈ CP :|C∩X|1}is the collection of all elements, which do not certainly belong either toXor to∼X. SoBNRX ∪{C∈ CP :|C∩X|1}.
Proposition 4.19. LetMPbe theI-MIP induced byP,CMP CP. Then for allX⊆U,
RX X−BNRX,
RX X∪BNRX, 4.9
whereBNRX ∪{C∈ CP :|C∩X|1}.
Proof. According to the definition of the boundary region and Proposition 4.18, it is straightforward.
Corollary 4.20. LetMPbe theI-MIP induced byP,CMP CP andX⊆U. Then for allC∈ CP, C /⊆RXif and only if for allx∈X,{x} ∈P.
Proof. ⇒: According toProposition 4.10andCorollary 4.11, if for allC∈ CP, C /⊆RX, then for allT ∈P and|T| ≥2,T∩X ∅. That is, for allx∈X,{x} ∈P.
⇐: It is straightforward.
Proposition 4.21. LetMP be theI-MIP induced byP,rMP rP. Then for allX⊆U, the following equations hold:
1RX {x∈U:rPX rPX∪ {x}}, 2RX ∪ {T ∈P :rPX rPX∪T}, 3RX Max{A⊆U:rPX rPA}.
Proof. 1According toProposition 4.13,rPX |Y|whereY ⊆Xand for allT ∈P,|Y∩T| ≤1.
LetT ∈P. If|Y ∩T| 0, thenT ∩X ∅ and for allt ∈ T,rPX rPX∪ {t}−1, that is, T /⊆RX and for allt ∈ T,t /∈ {x ∈ U : rPX rPX ∪ {x}}; else, if|Y ∩T| 1, then X ∩T /∅ and for all x ∈ T,rPX rPX ∪ {x}, that is, T ⊆ RX and for all t ∈ T, t∈ {x∈U:rPX rPX∪ {x}}. That is,RX {x∈U:rPX rPX∪ {x}}.
Similarly, we can prove that2and3are true.
Proposition 4.21provides three ways to get the upper approximation ofXwith rank function. This intensifies our understanding to rank function ofMP.
Proposition 4.22. LetMPbe theI-MIP induced byP, clMP clP. Then for allX⊆U,
RX clPX. 4.10
Proof. According toProposition 4.14andCorollary 4.15, we can get that clPX ∪{T ∈P : x ∈ X ∧ x ∈ T}. Therefore, according to the definition of the upper approximation, it is obvious thatRX clPX.
The compact formulation of the upper approximation in Proposition 4.22 indicates that the closure is an efficient way to get the approximations in rough sets.
Proposition 4.23. LetMPbe theI-MIP induced byP,HMP HP. Then for allX ⊆U,
RX ∪{∼H:H∈ HP∧X−H /∅}. 4.11
Proof. According toProposition 4.16, for allH ∈ HP,U−H ∈ P, that is,∼ H ∈ P. And if X−H /∅, thenX∩∼H/∅. Therefore, in terms of2.1,∼H⊆RX. Thus,RX ∪{∼H: H∈ HP∧X−H /∅}.
5. Matroidal Structure of Rough Sets Constructed from the Viewpoint of Cycle
InSection 3.2, the relationships between a cycle and an equivalence class are analyzed in detail. And a partition over the universe is transformed to a graph composed of some cycles. So, inspired by the cycle matroid introduced in39, we will construct the matroidal structure of rough sets from this viewpoint. A new matroid will be established and the characteristics of it are studied. Then the approximations in rough sets are investigated via these characteristics.
For convenience, in this section, we suppose thatUis a universe,R an equivalence relation overU, andP U/Rthe partition. AndGP U, EPis the graph induced byP, whereEP ∪{ETi :Ti∈P}.
5.1. The Second Type of Matroidal Structure of Rough Sets
In this subsection, the second type of matroid induced by a partition is defined. Similar to the discussion ofI-MIP, the base, circuit, rank function, and closure of the second type of matroid are investigated.
From the analysis inSection 3.2, we know that for allT ∈Pand for allK⊂T,CKis not a cycle. Obviously, any subgraph ofCKis also not a cycle. Therefore, we can get the following proposition.
Proposition 5.1. LetIP {X ⊆U: for allT ∈P, CT/⊆GPX}. Then there exists a matroidMon Usuch thatIM IP.
Proof. According toDefinition 2.3, we need to prove thatIP satisfiesI1∼I3. In terms of Section 3.2, for allT ∈P,CT is the cycle whose vertices set isT, that is,CT T, ETwhereET is the set of edges ofCT. So, it is obvious thatIP satisfiesI1andI2. Here, we just need to proveIP satisfiesI3.
LetI1, I2 ∈ IP,|I1| < |I2|and I2 −I1 {e1, e2, . . . , em}1 ≤ m ≤ |U|. Suppose that for allei ∈ I2−I1 for 1 ≤ i ≤ m,∃Tei ∈ P such thatTei ⊆ I1∪ {ei}, that is,Tei − {ei} ⊆ I1. Because|Tei− {ei}| ≥1,|Te1− {e1}| |Te2− {e2}| · · · |Tem− {em}| ≥m|I2−I1|. It is obvious thatTei/⊆I1∩I2∪ {ei}. So|I1||Te1− {e1}| |Te2− {e2}| · · · |Tem− {em}| |I1∩I2|. Since
|I2||I2−I1| |I2∩I1|, we can get that|I1| ≥ |I2|. It is contradictory with the known conditions that|I1|<|I2|. So∃ei ∈I2−I1such that for allT ∈P,T /⊆I1∪ {ei}, namely,CT/⊆GPI1∪ {ei}.
That isI1∪ {ei} ∈ IP. As a result,IP satisfiesI1∼I3. That is, there exists a matroidMon Usuch thatIM IP.
The matroid mentioned inProposition 5.1is established from the viewpoint of cycle.
It is a new type of matroid induced by a partition and is defined as follows.
Definition 5.2 The second type of matroid induced by a partition. The second type of matroid induced by a partitionPoverU, denoted byII-MIP, is such a matroid whose ground setEUand independent setsI{X⊆U: for allT ∈P, CT/⊆GX}.
Because of the intuition of a graph, it is easy to understand the matroid established in Definition 5.2. In fact, we can formulate aII-MIPas follows.
Proposition 5.3. LetI {n
i1Si : Si ⊂ Ti∧Ti ∈ P}where n |P|. ThenM U,Iis a II-MIP.
Proof. BecauseSi ⊂ Ti, for allX ∈ I,X∩T ⊂ T for eachT ∈P. That means for allT ∈ P, CT/⊆GPX, that is,X ∈ IP. Conversely, for allX ∈ IP, since for allT ∈P,CT/⊆GPX, we can get thatT /⊆X, that is,T∩X⊂T. SoX∈ I. As a result,M U,Iis aII-MIP.
In terms of Propositions5.1and5.3, we can find that the two matroids established in them are equivalent. That is to say for any matroidM U,I, ifII, thenMis aII-MIP. So, the following corollary can be obtained.
Corollary 5.4. IP I.
Similar to the axiomatization ofI-MIP, we will axiomatizeII-MIP with the set of circuits of it in the following.
Theorem 5.5. LetM U,Ibe a matroid. ThenMis aII-MIP if and only if for allC1, C2 ∈ CM,C1∩C2∅and∪CM U.
Proof. ⇒: LetM U,Ibe the II-MIP induced byP. Therefore, for allT ∈ P,T /∈ I, and for allX ⊂ T,X ∈ I. And then for allT ∈ P,T ∈ DM. So, according to2.2and Definition 2.5,CM P. Thus, for allC1, C2∈ CM,C1∩C2∅, and∪CM U.
⇐: Since for allC1, C2 ∈ CM,C1 ∩C2 ∅, and∪CM U, we can regard the CMas a partition overU. Furthermore,DM {X⊆U:∃C∈ CMs.t. C⊆X}. Because I2U− DM, for allX ∈ I,C∈ CMsuch thatC⊆X. According toProposition 5.1and Definition 5.2, we can get thatII IP. That is,M U,Iis aII-MIP.
Theorem 4.5shows there is one-to-one correspondence between a partition and the I-MIP induced by the partition. In the following theorem, we will discuss the relationship between a partition and theII-MIPinduced by the partition.
Theorem 5.6. LetPbe the collection of all partitions overU,Mthe set of allII-MIP induced by partitions ofP,g:P → M, that is, for allP∈ P,gP MP whereMP is theII-MIP induced by P. Thengsatisfy the following conditions:
1for allP1, P2∈ P, ifP1/P2thengP1/gP2, 2for allM∈ M, ∃PM ∈ Ps.t.PM M.
Proof. 1 Let P1 and P2 are two different partitions over U, and MP
1 U,IP
1,MP
2
U,IP2are twoII-MIP induced byP1andP2, respectively. We need to prove that there is anI1 ∈ IP1such thatI1 ∈ I/ P2, or there is anI2 ∈ IP2such thatI2∈ I/ P1. BecauseP1/P2, there must be an equivalence classT1 ∈ P1 such thatT1 ∈/ P2. Suppose that for allT ∈P2,T1 /⊆T. Then∃X ⊂ T1 such thatX ∈ {S : S ⊂ T1}andX /∈ {S : S ⊂ T, for allT ∈ P2}. According to Proposition 5.3,X ∈ IP1 and X /∈ IP2. Conversely, if ∃T2 ∈ P2 such that T1 ⊆ T2, then
∃X ⊂T2such thatX ∈ {S :S⊂ T2}andX /∈ {S:S ⊂T, for allT ∈P1}. Thus, according to Proposition 5.3,X∈ IP2andX /∈ IP1.
2 Let M U,I be a II-MIP matroid. According to Theorem 5.5, CM is a partition onU. That is,gCM M.
Theorem 5.6shows that there is also a bijection between a partition and theII-MIP induced by the partition.
5.2. Characteristics of II-MIP
TheII-MIPis established from the viewpoint of cycle. There is a big difference between the formulations ofI-MIPandII-MIPand the same as the characteristics between them. In this subsection, we will formulate the characteristics ofII-MIP.
A base of a matroid is one of the maximal independent sets of the matroid. From Propositions5.1and5.3, the cardinality of one of the maximal independent sets is equal to
