全部 标题 作者
关键词 摘要

OALib Journal期刊
ISSN: 2333-9721
费用:99美元

查看量下载量

相关文章

更多...

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

, PP. 609-614

Keywords: 动态网络,最大流,(最速)最大流,最小割定理

Full-Text   Cite this paper   Add to My Lib

Abstract:

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

References

[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 )

Full-Text

Contact Us

service@oalib.com

QQ:3279437679

WhatsApp +8615387084133