Abstract：Based on the dynamic quotient space model,the definitions of the max-flow and min-cut,and the condition that min-cut theorem holds in dynamic networks,are investigated. The analysis of the characteristics of max-flow in dynamic networks shows if the max-flow concept in the static environment is simply transferred to the dynamic one,the transformed max-flow does not have the two main properties,i.e. the additivity and total flow maximization. By introducing the concept of t-cut networks,a dynamic network is transformed into the combination of a set of static networks. Therefore,a new definition of the max-flow (steepest flow) is proposed and the defined concept is proved to have the above two properties. Then,a corresponding min-cut concept is presented and it is proved that the min-cut theorem holds under the new concepts of max-flow and min-cut. Finally,the algorithm for computing dynamic max-flow (steepest flow) is given.
张铃. 动态网络上最大流概念及其性质的研究[J]. 模式识别与人工智能, 2013, 26(7): 609-614.
ZHANG Ling. The Concept of Max-Flow and Its Properties in Dynamic Networks. , 2013, 26(7): 609-614.
[1] Zhang Ling,Zhang Bo. The Theory and Applications of Problem Solving. 2nd Edition. Beijing,China: Tsinghua University Press,2007 (in Chinese) (张 铃,张 钹.问题求解理论及应用——商空间粒度计算理论及应用.第2版.北京:清华大学出版社,2007) [2] Zhang Ling,Zhang Bo. Dynamic Quotient Space Model and Its Basic Properties. Pattern Recognition and Artificial Intelligence,2012,25(2): 181-185 (in Chinese) (张 铃,张 钹.动态商空间模型及其基本性质.模式识别与人工智能,2012,25(2): 181-185) [3] Ling Zhang,Fuqui He,Yanping Zhang,et al. A New Algorithm for Optimal Path Finding in Complex Networks Based on the Quotient Space. Fundamenta Informaticae,2009,93(4): 459-469 [4] He Fugui,Zhang Yanping,Chen Jie,et al. Path Queries on Massive Graphs Based on Multi-Granular Graph Partitioning // Proc of the 6th International Conference on Rough Sets and Knowledge Technology. Banf,Canada,2011: 569-578 [5] He Fugui,Zhang Yanping,Zhang Ling. Network Granular Storage and Its Application to Path finding. Computer Applications and Software,2011,28(11): 99-101 (in Chinese) (何富贵,张燕平,张 铃.网络的粒度存储及在路径搜索中的应用.计算机应用与软件,2011,28(11): 99-101) [6] Ford L R Jr,Fulkerson D R. Flows in Networks. Princeton,USA: Princeton University Press,1962 [7] Lu Kaicheng,Lu Huaming. The Graph Theory and Its Applications. Beijing,China: Tsinghua University Press,1995 (in Chinese) (卢开澄,卢华明.图论及其应用.第2版. 北京:清华大学出版社,1995 )
2013, Vol. 26 
