| 【中文题名】 | K-通道流与其改进算法 |
| 【英文题名】 | K-route Flows and Its Variant Algorithm |
| 【学科专业】 | 运筹学与控制论 |
| 【论文级别】 | 硕士论文 |
| 【投稿时间】 | 2007-8-20 |
| 【中关键词】 | 网络流,K-通道流,最大流,,, |
| 【英关键词】 | Network flows,Maximum flows,K-route flows, |
| 【分类导航】 | 数理科学和化学>数学>运筹学>最优化的数学理论>> |
| 【论文摘要】 |
设G=(N，A，u)是一个顶点集为N，弧集为A，始点为s∈N，终点为t∈N，有限容量向量u={u_(ij):(i,j)∈A}及正整数K的网络。一个基本K-通道流是一个从始点s∈N到终点t∈N的K个单位流，使得在每个弧上的流是0或1。一个K-通道流是一个从s到t的流，使得这个流可以表示成基本K-通道流的非负线性组合的流。因此，K-通道流问题是求解从s到t不仅要满足顶点平衡(s和t除外)和弧的容量限制下通常的最大流问题，而且这个流必需满足沿着K条弧不交的s—t路发送。在本文中，我们给出了另一个解决K-通道流问题组合算法，分析了这个改进算法的时间复杂性，并且研究了这个算法在理论上的迭代步数少于Kishimoto算法和Newton算法的迭代步数，但不少于原始对偶算法的迭代步数。另外，简要地介绍了K-通道流从弧流形式到路流形式的转化算法。 |
| 【论文题纲】 |
|
摘要 |
4-5 |
|
Abstract |
5-7 |
|
第一节 绪论 |
7-11 |
|
1.1 问题的提出 |
7-9 |
|
1.2 K-通道流的研究现状 |
9-11 |
|
第二节 多通道流的基本定理 |
11-24 |
|
2.1 基本概念和记号 |
11-14 |
|
2.2 多通道流的基本性质 |
14-17 |
|
2.3 多通道流的最大流最小割定理 |
17-24 |
|
第三节 多通道流的一个改进算法 |
24-33 |
|
3.1 多通道流的一个改进算法 |
24-26 |
|
3.2 多通流的一个改进算法的时间复杂性分析 |
26-29 |
|
3.3 K-通道流改进算法的应用 |
29-33 |
|
3.3.1 Kishimoto算法 |
30 |
|
3.3.2 Aggarwal及Orlin的原始对偶算法 |
30-31 |
|
3.3.3 牛顿迭代算法 |
31-33 |
|
第四节 K-通道流的分解算法 |
33-36 |
|
第五节 主要结论和下一步工作 |
36-37 |
|
参考文献 |
37-39 |
|
致谢 |
39 |
|
| 【DOI】 | LunWen.ID:2.2008.14831 |
