Matroid Structure Based On Generalized Rough Sets And Its Characteristics

Rough set theory is an effective mathematical tool to deal with fuzzy and uncertain problems in information systems,and as an important intelligent information processing technique,it is especially successful in processing the data of complex systems.It has attracted much researcher's interest all over the world.However,because rough set theory is under development,the limitation of its application in real life is very strong.For example,the classical rough sets,which is based on partition,have been greatly restricted on application and theory.To address this issue,scholars have made many extended research on rough sets from different angles.In order to meet various practical applications of rough set theory,many research scholars propose many different generalizations of the classical rough set.There are two kinds of important extension methods.One is extending the equivalence relation to fuzzy binary relation,similarity relation,tolerance relation and the other general binary relation,the other one is relaxing the partition to covering.The concept of matroid was originally introduced by H.Whitney in 1935 as a generalization of graph theory and linear algebra.The matroid theory was proposed only eighty years,but with the promotion of actual needs and the efforts of mathematics researchers,it has already had a complete axiom system.However,many practical problems in rough set theory are NP-hard,such as attribute reduction.Therefore,most algorithms to solve them are often greedy ones.Matroid theory provides a well platform for greedy algorithms.Therefore,it is important to combine matroid theory with rough set theory.In this thesis,we construct some types of matroidal structure of generalized rough sets,and make a systematic investigation on the two structures.First,we establish two types of matroidal structure based on generalized binary relation and describe some characteristics of these matroidal structures of rough sets from different perspectives.Second,we establish a matroidal structure based on covering and find out the conditions for a covering to inducespanning matroid.We also study the connectivity of matroid by covering-based rough sets.The main work of this paper is as follows:(1)We extent the equivalence relation to similarity relation and tolerance relation,that is to say,the classical rough sets is extended to generalized binary relation based rough sets.We establish two types of matroidal structures.One matroidal structure is established based on tolerance relation through the lower approximations,the other one is established based on similarity relation through the lower and upper approximations.Some characteristics of the two types of matroidal structures of rough sets are depicted and the matroid whether is graphic or not is studied.(2)We extent the equivalence relation to covering.Firstly,we establish a matroidal structure based on covering-based rough sets through neighborhood and complementary neighborhood.Secondly,we study the conditions under which covering-based rough sets can induce spanning matroids.At first some families of sets are constructed in different covering-based rough set models.Then we present conditions under which these families of sets satisfy the spanning set axiom of matroids and study the relationships among these families of sets.(3)We combine the covering-based rough sets,graph and matroids.At first,we present an approach to induce a covering by a graph and study the connectivity of the graph by the second covering-based rough set models.Then,a matroid is established by the covering and the connectivity of this matroid is studied.At last,we study the relationship between the graph and the matroid.