动态网络上最大流概念及其性质的研究

本文在动态商空间模型的基础上，研究动态网络环境下最大流、最小割的定义及最小割定理成立的条件。首先分析动态网络最大流量的特点，发现直接将静态环境下的最大流量概念移植到动态的情况，所得的最大流不具有可加性和总流量最大性。为此引入t-截网络的概念，将动态网络化成静态网络的组合，为动态网络的分析提供一个有效的方法;在此基础上提出(最速)最大流量的定义，并证明新定义的最大流具有可加性和总量最大性。接着给出相应的最小割概念，证明新定义下的最大流、最小割对应的最小割定理成立。最后给出求动态(最速)最大流量的算法。

The Concept of Max-Flow and Its Properties in Dynamic Networks

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.