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

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

作　　者：刘石坚 邹峥[3] 乐晓波[4] 

机构地区：[1]福建工程学院信息科学与工程学院,福建福州350118 [2]福建工程学院福建省大数据挖掘与应用技术重点实验室,福建福州350118 [3]中南大学信息科学与工程学院,湖南长沙410083 [4]长沙理工大学计算机与通信工程学院,湖南长沙410076

出　　处：《福建工程学院学报》2018年第1期66-73,共8页Journal of Fujian University of Technology

基　　金：福建省属高校科研专项项目(JK2017029);福建工程学院校级科研项目(GY-Z160138;GY-Z160130)

摘　　要：给出了任意流网络及其残留网络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

关 键 词：最大流-最小割 PETRI网 建模 补库所 活性 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]