Rough Graph And Its Application

In 1982,Professor Z.Pawlak presented rough set theory,which provides theory tool for explanation of rough phenomena and solution of rough problems in the real world.In 2002,by extending Z.Pawlak rough set Professor Shi Kaiquan presented singular rough set which has dynamic properties,denoted as S-rough set for short,which enables rough set to apply to more fields.This thesis aims to improve computation ability of rough set and S-rough set and constructs rough graph and S-rough graph by combining classical graph theory with rough set and S-rough set respectively.Furthermore,this thesis gives theory and application researches of rough graph and S-rough graph.The main research contents and innovation points of this thesis are as follows:·Main Research ContentsRough graph and S-rough graph are constructed and their properties are discussed respectively.Weighted rough graph and rough network are constructed.Some important algorithms of weighted rough graph and rough network are designed by extending corresponding algorithms in classical weighted graph and classical network and their applications are also given.Finally,a new rough graph structure which based on algebraic operators is constructed.The graph structure analysis method of algebraic relationship among rough sets is presented and its application is also given.Chapter 1 firstly provides a brief introduction of background and recent situation of development and research of rough set and gives definition and properties of Z.Pawlak rough set.Secondly,it gives definition of S-rough set and function S-rough set,which provide theory basis for the research in the following chapters.Chapter 2 firstly constructs rough graph by combining classical graph with Z.Pawlak rough set for the purpose of improving computation ability of rough set and analyzing rough phenomena and solving rough problems by using graph theory knowledge.The basic idea is that based on the structure of classical graph,take vertices of an edge as its attribute.Furthermore,allow edge to have more attributes and construct attribute set of edge,so get the definition of rough graph.Secondly,based on several kinds of representation form of classical graph,two presentation forms of rough graph which take up less computer space are presented,and they are adjacency matrix and edge list,which supplies convenience for the computation in rough graph.Thirdly,the rough characteristic of rough graph is analyzed in detail.Some conceptions such as edge precision,rough similarity degree and so on are defined and their properties are also given.Finally,some kinds of important subgraph of rough graph such as class path,class cycle,class tree and so on are defined and the class connection of rough graph is analyzed.Chapter 3 firstly constructs weighted rough graph by adding weight attribute to edge of rough graph for the necessity of doing comparison in actual application,and some conceptions in weighted rough graph such as class shortest path,class optimum tree and so on are defined.For the convenience of computation,two representation forms of weighted rough graph are given,which are weight matrix and weight list.Secondly,class optimum tree algorithm(COTA) and class shortest path algorithm(CSPA) in weighted rough graph are designed by extending optimum tree algorithm and shortest path algorithm in classical weighted graph respectively and they are successfully applied to relationship mining at same relationship level.Chapter 4 firstly constructs directed rough graph and rough network by only adding direction attribute to edge of rough graph and adding both direction attribute and weight attribute to edge of rough graph at same time respectively for the necessity of differentiating direction in actual application.Meanwhile,some important conceptions such as directed class path in directed rough graph,class flow in rough network and so on are given.For the convenience of computation,two representation forms of directed rough graph and rough network are represented respectively,which are adjacency matrix and arc list of directed rough graph and weight matrix and weight list of weighted rough graph.Secondly,class maximum flow algorithm(CMFA) in rough network is designed by extending maximum flow algorithm in classical network and it is successfully applied to relationship mining between different relationship levels. Chapter 5 firstly constructs S-rough graph by combining classical graph with S-rough set for the necessity of analyzing rough problem which has dynamic properties,and its basic properties is also analyzed.Secondly,some subgraphs which have dynamic properties and only exist in S-rough graph are presented,such as F-class path,F-class path,(?)-class path and so on and their properties are also given.Finally,the comparison between rough graph and its S-rough graph is given by using rough similarity degree, which enables us to analyze S-rough graph according to the information and results of rough graph.Chapter 6 constructs a new rough graph structure by taking rough set as vertex and the result of algebraic operation between rough sets as edge.Furthermore,graph structure analysis method of algebraic relationship analysis among rough sets is presented and it is successfully applied to affective computing,which is one of hotspots in artificial intelligence field.Chapter 7 concludes the whole thesis.·Innovation Points of ThesisInnovation point 1.Rough graph is constructed by combining classical graph theory with rough set.This is the first time to combine rough set with graph knowledge,which is not only a new research direction of rough set theory,but also the algorithms in classical graph theory can improve the computation ability of rough set.Furthermore,rough graph enables graph theory to research rough problem,which widen the application field of graph theory.Innovation point 1 can be found in Chapter 2.Innovation point 2.Weighted rough graph,directed rough graph and rough network are constructed by adding different attributes to edge of rough graph.And class optimum tree algorithm(COTA),class shortest path algorithm(CSPA) and class maximum flow algorithm(CMFA) are designed by extending optimum tree algorithm,shortest path algorithm and maximum flow algorithm in classical graph.The construction of new kind of rough graphs and designation of new algorithms not only enrich rough graph theory, but also the applications of new algorithms still have built a rational relationship analysis and relationship mining system.Innovation point 2 can be found in Chapter 3 and Chapter 4. Innovation point 3.S-rough graph is constructed by combining classical graph theory with S-rough set theory,which enables rough graph to research rough problems that have dynamic properties.Innovation point 3 can be found in Chapter 5.Innovation point 4.A new rough graph structure is constructed by taking rough set as vertex and the result of algebraic operation between rough sets as edge.Meanwhile, graph structure analysis method of algebraic relationship analysis among rough sets is presented.Furthermore,by modeling human emotions based on rough set,this method is successfully applied to mining affective transfer law in affective computing,which is one of hotspots in artificial intelligence field.Innovation point 4 can be found in Chapter 6.