The Application Of Matroid In Some Networks And The Constructive Method Of Greedoids

In this paper,firstly,it studies some common types of network structure using the method of matroid.The methods provided here are different from commonly methods which are using the sort,graph,optimization theory and so on,because it shows the advantages of matroid theory studying in the network such as simple,intuitive and easy.Afterwards,in order to make further study on much more network structures by matroid theory,this paper also discusses a broader significant structure—greedoids,and gives a constructive method for a special class of greedoids.The main content of the text is shown as follows:The applications of matroid theory in several types of network aspects:according to the situations of paving the lines of water supply networks and setting on the scenic lights,this paper builds up the mathematical modes with the knowledge of graph theory resepectively.The optimal solutions of the above models are obtained based on the relative knowledge of matroid theory especially the improvrd greedy algorithm of matroid.In addition,it analyzes the above algorithms ,complexity. Finally,it gets the best programs in the lines of water supply network and scenic decoration repectively.In the aspect of constructing greedoids,this paper presents a new greedoids—Searching-arc greedoids which is generated in a directed tree,and at the same time, it gives a way to produce this kind of greedoids which is called as Searching-arc method.The advantages of this approach are:in the light of depth-first principle,constructing greedoids in a tree is quick and simple.Therefore, the presented method here has also instructive ideas for searching greedoids in the other directed graphs.