[1]刘石坚,邹峥,乐晓波.基于Petri网的最大流-最小割问题建模与求解[J].福建工程学院学报,2018,16(01):66-73.[doi:10.3969/j.issn.1672-4348.2018.01.013]
　LIU Shijian,ZOU Zheng,LE Xiaobo.Using Petri network for modeling and solving the max-flow/min-cut problem[J].Journal of FuJian University of Technology,2018,16(01):66-73.[doi:10.3969/j.issn.1672-4348.2018.01.013]
点击复制

基于Petri网的最大流-最小割问题建模与求解()
分享到：

《福建工程学院学报》[ISSN:2097-3853/CN:35-1351/Z]

卷:
第16卷
期数:
2018年01期
页码:
66-73
栏目:
出版日期:
2018-02-25

文章信息/Info

Title:
Using Petri network for modeling and solving the max-flow/min-cut problem
作者:
刘石坚; 邹峥; 乐晓波
福建工程学院信息科学与工程学院
Author(s):
LIU Shijian;  ZOU Zheng;  LE Xiaobo
School of Information Science and Engineering, Fujian University of Technology
关键词:
最大流-最小割;  Petri网;  建模;  补库所;  活性
Keywords:
max-flow/min-cut;  Petri network (PN);  modeling;  complementary places;  activity
分类号:
TP301
DOI:
10.3969/j.issn.1672-4348.2018.01.013
文献标志码:
A
摘要:
给出了任意流网络及其残留网络Petri网模型的构造流程；通过对模型中各元素的实际意义进行分析，指出如何得到最大流的各个分布；从理论上证明达到最大流的条件并给出通过活性分析可以得到一个最小割的结论；将残留网络和流网络Petri网模型结合起来给出最大流-最小割问题完整的解决方案。Petri网图形化的仿真过程为研究网络流从局部到整体的变化提供了直观的描述。仿真结果证实该方法准确、有效。
Abstract:
The construction process of a given flow network and its corresponding residual Petri network(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

参考文献/References:

[1] GENRICH H, KFFNER R, VOSS K. Executable Petri net models for the analysis of metabolic pathways[J]. International Journal on Software Tools for Technology Transfer, 2001, 3(4): 394-404.
[2] 尹延通,刘高飞,季亮.基于最小割集的光学测云系统故障诊断[J].延边大学学报（自然科学版）,2016,42(3):267-270.
[3] 张永发,蔡琦,赵新文.应用Petri网模型改进最小割集的算法[J].核动力工程,2007,28(5):63-68.
[4] 刘玲艳,吴晓平,田树新.基于粗糙集和Petri网的随机流网络可靠性评价方法[J].控制与决策,2010,25(8):1273-1276.
[5] 胡雄鹰,胡斌,张金隆,等.基于Petri网求解网络最大流的并发仿真方法[J].武汉理工大学学报（信息与管理工程版）,2010,32(1):27-30.
[6] FAN L, LIU K. Paint mesh cutting[J]. Computer Graphics Forum, 2011, 30(2): 603-611.
[7] 刘松涛，殷福亮.基于图割的图像分割方法及其新进展[J].自动化学报,2012,38(6):912-922.
[8] DELONG A, OSOKIN A, ISACK H N, et al. Fast approximate energy minimization with label costs[C]∥ IEEE Conference on Computer Vision and Pattern Recognition, IEEE, 2012: 1-27.
[9] 向红艳,张邻,杨波.基于最大流的路网结构优化[J].西南交通大学学报,2009,44(2):284-288.
[10] 寇玮华,李宗平.运输网络中有流量需求的转运结点最大流分配算法[J].西南交通大学学报,2009,44(1):118-121.
[11] 蔡伟,张柏礼,吕建华.不确定图最可靠最大流算法研究[J].计算机学报,2012,35(11):2371-2380.
[12] 张宪超,江贺,陈国良.节点和边都有容量的有向平面网络中的最小截和最大流[J].计算机学报,2006,29(4):544-551.
[13] CORMEN T H, LEISERSON C E, RIVEST R L, et al. Introduction to algorithms, Third[M]. London: The MIT Press, 2009.
[14] SEDGEWICK R.算法:C语言实现(第5部分:图算法)[M].霍红卫，译.北京:机械工业出版社,2010.
[15] 袁崇义. Petri 网原理与应用[M].北京:电子工业出版社,2005.
[16] 刘石坚,乐晓波,邹峥.关于 Petri 网系统S-补相关定理的补充证明及其分析[J].系统仿真学报,2009,40(S2):1-5.

更新日期/Last Update: 2018-02-25