无向网络中有流量需求的转运节点的最大流算法

论文摘要

最大流问题是一个经典的网络优化问题,除了解决实际网络中的问题以外,在许多科学技术领域也有广泛的应用.目前的大多数最大流算法都是针对有向网络的,并且是在容量限制条件和流量守恒条件下进行的.但是,通信、计算机网络等现实问题实际上可以归结为一个加权无向图上的最大流问题.另外在实际的网络应用中,转运节点有流量需求的问题普遍存在,它违背流量守恒条件,因此,单纯使用传统的算法不能够有效地解决这类最大流问题.基于以上问题,本文主要做了以下工作:首先概述了几个经典的组合算法,这些算法是以后的最大流算法研究基础;同时介绍了最大流算法的研究现状和发展趋势.其次,针对有流量需求的转运节点的无向网络,利用标号法、正向追踪和有流量需求的转运节点的分配思想给出了一种最大流算法.示例表明,该算法具有较好的实用性.

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 课题背景及研究意义
• 1.1.1 课题背景
• 1.1.2 课题研究意义
• 1.2 网络最优化与线性规划
• 1.2.1 网络最优化概述
• 1.2.2 最优化问题的数学模型
• 1.2.3 最优化问题算法
• 1.2.4 线性规划
• 1.3 本文主要内容与结构安排
• 第二章 网络流问题
• 2.1 网络与流
• 2.1.1 基本概念
• 2.1.2 几个基本定理
• 2.2 网络最大流
• 2.2.1 基本概念和数学模型
• 2.2.2 Ford-Fulkerson 算法
• 2.3 算法应用
• 第三章 网络最大流问题研究进展
• 3.1 算法的研究进展
• 3.1.1 算法简述
• 3.1.2 算法的进展
• 3.2 问题应用的研究进展
• 第四章 有流量需求的转运节点的最大流算法
• 4.1 问题的提出
• 4.1.1 无向网络
• 4.1.2 带有流量需求的转运节点
• 4.2 无向网络最大流算法概述
• 4.2.1 算法步骤
• 4.2.2 复杂度分析
• 4.3 有流量需求的转运节点的最大流算法
• 4.3.1 问题描述
• 4.3.2 算法思想
• 4.3.3 算法步骤
• 4.3.4 算法示例
• 结束语
• 致谢
• 参考文献
• 在读期间的研究成果