Some Applications Of Graph Theory In Network And Information Extraction

Graph theory is a mathematical research on objects.A network is a structure composed by nodes(also known as objects)and the connection between nodes in order to represent the nodes and the relationships among the nodes.We can use a weighted graph to express information directly.In practical applications,any network can be modeled by a graph.A class of multi-dimensional and complex information can be divided into two-dimensional and simple one with a kind of intuitive and clear binary matrix.In this way,the relationship between objects can be dealt with a way which is standardized,convenient and quick.In fact,graph theory has been widely applied in various fields such as natural science,social science,military,transportation and so on.During the process in network traffic and information extraction with graph theory,we firstly consider the network with K_n — a complete graph.Then,using graph theory,the information is extracted.Secondly,we construct a 0-1 correlation matrix,followed by ultimately studied and found matrix representation about binary matroid which is parallel to this special background in real life.In fact,the storage of information is also used 0-1.This property makes us transforme the information into 0-1 form background,followed by creating an information extraction method for the concept lattice of the above information table.Addtionally,based on the needs of users,utilized the instrument of data mining and information extracted,we construct grid in order to demonstrate what we need with Hasse diagram of the concept lattice,followed by illustrate alternative approach to the users.This dissertation uses graph theory to solve some problems in network and information extraction:1.The first is two applications of graph theory in the shortest time path network and goods delivery location network.One is to take transportation with the shortest time,and the following is to select the best route for the study in order to give the travelers for the shortest path in multiple properties under constraints of the k shortest path time path algorithm.Another is to give the courier mail goods so as to get a solution method of k-means clustering algorithm based on the improved rational distribution scheme.2.The second application of graph theory is in information extraction in traffic network.According to the algorithm of the considered contexts,we discover an algorithm for K_n graph to search out all of concepts of the context based on binary matroids.Utilizing an example,we prove the feasibility of the proposed method.