基于Petri网的最大流-最小割问题建模与求解

Using Petri network for modeling and solving the max-flow/min-cut problem

给出了任意流网络及其残留网络Petri网模型的构造流程;通过对模型中各元素的实际意义进行分析,指出如何得到最大流的各个分布;从理论上证明达到最大流的条件并给出通过活性分析可以得到一个最小割的结论;将残留网络和流网络Petri网模型结合起来给出最大流-最小割问题完整的解决方案。Petri网图形化的仿真过程为研究网络流从局部到整体的变化提供了直观的描述。仿真结果证实该方法准确、有效。

The construction process of a given flow network and its corresponding residual Petri net- work（PN） were introduced. Analysis of the actual meaning of each element in the PN models was conducted so as to show how to achieve each of the maximum flow distributions. After that, the conditions for achieving a maximum flow in the PN model were proved, and it was concluded that a minimum cut can be obtained through activity analysis. Finally, the residual network and the PN models of the flow network were combined to give an integrated solution for the max-flow/min-cut problem. The graphic simulation of PN provided a visual description of the network＇ s flow variation from part to whole. The max-flow/min-cut solution resulting from the simulation results verified the accuracy and effectiveness of the method