Research On Tolerance In Maximum Flow Algorithm Though A Network

Network optimization is an important branch of optimization, which is also the cross-discipline of combination of graph theory with optimization theory. It mainly studies the network algorithm with mathematical models searched with graph theory algorithm. The issue of network maximum flow is to study the maximum transport capacity of a flow between the source and the sink in a capacity-limited network. Maximum flow problem is a close connection between graph theory and operations research, in particular with the linear programming, which has opened up new ways in graph theory application.The thesis starts with the network maximum flow algorithm, which includes five chapters.In the first chapter, we introduce the basic issues of network optimization at first, together with the history and development of network maximum flow algorithm. Later we learn the development of the algorithms classification, and we finally analyze the wide range of applications and development prospects for network maximum flow algorithm.The second chapter is an introduction of the involved common concept of network optimization and the mainstream algorithms of the network maximum flow.In the third chapter, we first give the related definitions and theorems of minimum cut, later give the solution to determine the maximum flow and minimum cut of the network, where the tolerance of the network is non-positive or non-tolerance as well as structure balanced, and we also give the theorem of it.In the forth chapter, we first brief on the process of the improvement of network maximum flow 2F algorithm by adding tolerance determination into it, later we give the methods of data preprocessing, steps as well as the flow chart algorithm of the new algorithm.In the fifth chapter, we give a few examples of the improved 2F maximum flow algorithm, also make a comparison of efficiency with the original 2F algorithm, which confirms that the improved algorithm has achieved good effect. Also, we widely discuss the application of the improved algorithm.