位置:成果数据库 > 期刊 > 期刊详情页
动态网络上最大流概念及其性质的研究
  • ISSN号:1003-6059
  • 期刊名称:模式识别与人工智能
  • 时间:2013.7.7
  • 页码:609-614
  • 分类:TP181[自动化与计算机技术—控制科学与工程;自动化与计算机技术—控制理论与控制工程]
  • 作者机构:[1]安徽大学计算机科学与技术学院,合肥230039
  • 相关基金:国家自然科学基金资助项目(No.61073117,61273302)
  • 相关项目:动态商空间理论及应用
作者: 张铃|
中文摘要:

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

英文摘要:

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.

同期刊论文项目
期刊论文 37 会议论文 14 著作 1
同项目期刊论文
期刊信息
  • 《模式识别与人工智能》
  • 中国科技核心期刊
  • 主管单位:中国科学技术协会 中国自动化学会
  • 主办单位:国家智能计算机研究开发中心 中国科学院合肥智能机械研究所
  • 主编:郑南宁
  • 地址:安徽省合肥市蜀山湖路350号中国科学院合肥智能机械研究所
  • 邮编:230031
  • 邮箱:bjb@iim.cas.cn
  • 电话:0551-5591176
  • 国际标准刊号:ISSN:1003-6059
  • 国内统一刊号:ISSN:34-1089/TP
  • 邮发代号:26-69
  • 获奖情况:
  • 国内外数据库收录:
  • 被引量:10169