Petri Nets Based Max-flow/Min-cut Modeling and Analyzing

Abstract

Max-flow/min-cut is named by the dual problem of finding a flow with maximum value in a given network and looking for a cut with minimum capacity overall cuts of the network. Petri Nets (PNs) is an effective modeling tool which has been widely used for the description of distributed systems in terms of both intuitive graphical representations and primitives well-defined by mathematics. Most cited references related to the max-flow/min-cut focus on either the improvement of the solving algorithm or its applications. Whereas in this paper, PNs are adopted to model and analyze the max-flow/min-cut. Firstly, algorithms for generating models from a given flow network and its residual network are introduced based on the PNs theory. Then, the models are combined to simulate the classic Ford-Fulkerson for solving the max-flow/min-cut and finding flow distributions when the max-flow achieves. Finally, simulation results and proofs are presented to show that our method is an intuitive and effective way of understanding and presenting the max-flow/min-cut theory and to ensure its validity. The proposed PNs based method is extensible because the idea can easily be applied to other graph problems similar to the Max-flow/min-cut.