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

摘要：

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

关键词：动态网络、最大流、(最速)最大流、最小割定理

分类号：TP181(自动化基础理论)

资助基金：国家自然科学基金资助项目61073117,61273302

在线出版日期：2013-08-25（万方平台首次上网日期，不代表论文的发表时间）

页数：共6页

页码：609-614