网络流理论及其的应用.doc

实用标准文案 精彩文档 网络流及其应用 bernie@中国科学技术大学  摘要 网络流理论最初由Ford和Fulkerson于1956年创立，包括理论与算法两部分。网络流理论的关键是在网络中引入了“流”的概念。在我们的日常生活中有大量的网络，如电网、水管网、交通运输网、通讯网等，这些网络中，“流”都是普遍存在的。近年来在解决网络方面的有关问题时，网络流理论发挥了重要作用。 在网络流理论中，可行流是整个体系的关键。流及其相关概念都与图论有着密切关系，因此，为了更好地介绍网络流理论，本文首先将介绍图论的基本概念和网络的相关基础。 在网络流理论中，最大流问题是其中的重要部分。在求解最大流问题方面，利用可增路逐步增加流量是得到最大流的基本思路。标号算法、Dinic算法都是在可增路的基础上对最大流问题进行求解的。这些算法都能独立解决最大流问题，需要根据实际情况进行选择。在实际网络中，网络的费用问题也需要考虑，为此，除了最大流之外，最小费用流也应该受到关注，本文将介绍最小费用问题的最小费用路算法。 网络流理论不仅能用于物质流，也能用于现代通信领域。物质流与信息流在某些形式上是相同的，但是在存储和处理上也有一些特殊的性质。针对这些特殊性质，需要在信息流中加以区分和利用，充分利用信息流的特性，尽可能提高网络效率。 网络流理论在计算机网络领域有着广泛的应用，本文将以延时容忍网络为例进行分析。延时容忍网络的主要特点是端到端的路径不能得到保证，因此，在延时容忍网络中，节点需要采用先存储后转发的机制，这将可能导致同一数据会在网络中的多个节点中出现，造成信息冗余。本文将利用网络流理论对这样的信息冗余的必要性进行分析。 本文的主要内容安排如下。首先介绍网络流理论的背景；随后，在第二章中介绍图论的基础知识和网络的基本概念；第三章将介绍网络的最大流与最小割；在第四章中，我们对网络流的扩展问题进行描述和介绍，包括最小费用流问题和信息流理论；最后，我们将介绍网络流在延时容忍网络中的应用。  目录 TOC \o 1-3 \h \z \u HYPERLINK \l _Toc243382207第1章 引言 PAGEREF _Toc243382207 \h 1 HYPERLINK \l _Toc243382208第2章 图论基础和网络基本概念 PAGEREF _Toc243382208 \h 1 HYPERLINK \l _Toc2433822092.1 图论基本概念 PAGEREF _Toc243382209 \h 1 HYPERLINK \l _Toc2433822102.2 网络的基本概念 PAGEREF _Toc243382210 \h 3 HYPERLINK \l _Toc2433822112.3 网络的可行流 PAGEREF _Toc243382211 \h 4 HYPERLINK \l _Toc2433822122.4最大流与最小割 PAGEREF _Toc243382212 \h 5 HYPERLINK \l _Toc243382213第3章 网络最大流问题求解 PAGEREF _Toc243382213 \h 5 HYPERLINK \l _Toc2433822143.1 可增路 PAGEREF _Toc243382214 \h 6 HYPERLINK \l _Toc2433822153.2 最大流问题的标号算法 PAGEREF _Toc243382215 \h 7 HYPERLINK \l _Toc2433822163.3 最大流问题的Dinic算法 PAGEREF _Toc243382216 \h 9 HYPERLINK \l _Toc243382217第4章 最大流问题的扩展 PAGEREF _Toc243382217 \h 13 HYPERLINK \l _Toc2433822184.1 最小费流 PAGEREF _Toc243382218 \h 13 HYPERLINK \l _Toc2433822194.2 信息流理论 PAGEREF _Toc243382219 \h 16 HYPERLINK \l _Toc243382220第5章 应用举例 PAGEREF _Toc243382220 \h 17 HYPERLINK \l _Toc2433822215.1 延时容忍网络介绍 PAGEREF _Toc243382221 \h 17 HYPERLINK \l _Toc2433822225.2 单份拷贝和多份拷贝方式选择问题分析 PAGEREF _Toc243382222 \h 17 引言 在日常生活中，网络是一个非常常见的概念，例如电网、水管网、交通运输网、通讯网等。在这些网络中，会遇到各种各样的问题，如