Network Maximum Flow Algorithm And Applied Research

The maximum flow problem is widely used in science and engineering, is a closeconnection between graph theory and linear programming problem, many linear programmingproblems can be transformed into the network flow model to solve, opened up a new way inapplication of graph theory. As the rapid development of the traffic, electric power, logistics andthe wide application of computer technology, people put forward a series of algorithm throughmake a deeply research continuously,and gradually complete the maximum flow theory. Thereare a lot of complicated calculation and steps in the existing algorithm for solving the maximumnetworks flow, and because of improper selection order of augmented path, we can not get theideal maximum flow. Around these problems some investigations are made as follows.Firstly, this paper puts forward a new algorithm for solving the maximum flow problemwhich make use of depth first search theory and hierarchical network. By adding the concept ofterminator, the entire operation process only needs drawing a diagram to be completed. Theimproved algorithm effectively improved the efficiency of the algorithm, and by using a realcase, the applicability and effectiveness of the method are demonstrated.Secondly, a new algorithm based on the existing algorithm is proposed, which quote theconcept of degree. The main idea of this algorithm is based on augmented chain algorithm,introduce the concept of vertex degree to select augmented chain. It is strong intuitive andconvenient to calculate.Thirdly, the paper describes the application of the maximum flow in real life, and introducesthe method to realize algorithm on the computer. Network maximum flow problem is widelyused in real life, some actual problems can be converted to solve the network maximum flowproblem, this paper summed up application of maximum flow problem. In addition, this paperintroduces the implementation of the maximum flow algorithm in the computer, thus get rid ofthe limitations which the algorithm is only for small network.