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