Research And Application Of Problems Related To Independence Systems Of Matroids

Graph theory is a very active and practical subject,which is widely used in natural science,social science and other fields.Matroid theory closely related to graph theory has a history of several decades.In 1935,Whitney firstly proposed the concept of matroid and gradually established the axiom systems.From then on,matroid has attracted the attention of many mathematicians and has been applied to combinatorial mathematics and combinatorial optimization,in which it plays an extremely important role.This thesis studies the relationships of matroid independence system,Hamiltonian graph and topological structure and obtains some important results.The main work is as follows:1.The relationship between independence systems of matroids and Hamiltonian graph problems is studied,and a necessary and sufficient condition for judging Hamiltonian graph is given by using adjacency matrix.The thesis puts forward a necessary and sufficient condition for judging Hamiltonian graphs according to the properties of the circuit matroid and Hamiltonian graph.The relationship between the basis of circuit matroid and spanning tree of graph is studied and an algorithm for the optimization problems of Hamiltonian graph is proposed.2.The operations of independence systems are studied and the tree structure of all independence systems on a ground set are given.This thesis studies the intersection and union operation of independence systems on the same or different ground sets.The set-value independence system is proposed and the connectivity property of independence systems is studied.3.The relationship between independence system and point set topology is studied,and the pseudo-topological independence system is defined.Then the neighborhood,interior,boundary of independence system are studied.The thesis gives the metric function on independence system,and studies the related properties of pseudotopological independence system.Finally,some examples are used to illustrate the proposed algorithm and properties and to show the feasibility of the proposed conclusions in this thesis.