网络流理论及其应用

网络流及其应用1网络流及其应用bernie@中国科学技术大学网络流及其应用2摘要网络流理论最初由Ford和Fulkerson于1956年创立，包括理论与算法两部分。网络流理论的关键是在网络中引入了“流”的概念。在我们的日常生活中有大量的网络，如电网、水管网、交通运输网、通讯网等，这些网络中，“流”都是普遍存在的。近年来在解决网络方面的有关问题时，网络流理论发挥了重要作用。在网络流理论中，可行流是整个体系的关键。流及其相关概念都与图论有着密切关系，因此，为了更好地介绍网络流理论，本文首先将介绍图论的基本概念和网络的相关基础。在网络流理论中，最大流问题是其中的重要部分。在求解最大流问题方面，利用可增路逐步增加流量是得到最大流的基本思路。标号算法、Dinic算法都是在可增路的基础上对最大流问题进行求解的。这些算法都能独立解决最大流问题，需要根据实际情况进行选择。在实际网络中，网络的费用问题也需要考虑，为此，除了最大流之外，最小费用流也应该受到关注，本文将介绍最小费用问题的最小费用路算法。网络流理论不仅能用于物质流，也能用于现代通信领域。物质流与信息流在某些形式上是相同的，但是在存储和处理上也有一些特殊的性质。针对这些特殊性质，需要在信息流中加以区分和利用，充分利用信息流的特性，尽可能提高网络效率。网络流理论在计算机网络领域有着广泛的应用，本文将以延时容忍网络为例进行分析。延时容忍网络的主要特点是端到端的路径不能得到保证，因此，在延时容忍网络中，节点需要采用先存储后转发的机制，这将可能导致同一数据会在网络中的多个节点中出现，造成信息冗余。本文将利用网络流理论对这样的信息冗余的必要性进行分析。本文的主要内容安排如下。首先介绍网络流理论的背景；随后，在第二章中介绍图论的基础知识和网络的基本概念；第三章将介绍网络的最大流与最小割；在第四章中，我们对网络流的扩展问题进行描述和介绍，包括最小费用流问题和信息流理论；最后，我们将介绍网络流在延时容忍网络中的应用。网络流及其应用3目录第1章引言.......................................................................................................................1第2章图论基础和网络基本概念...................................................................................12.1图论基本概念............................................................................................................12.2网络的基本概念........................................................................................................32.3网络的可行流............................................................................................................42.4最大流与最小割.........................................................................................................5第3章网络最大流问题求解...........................................................................................53.1可增路........................................................................................................................63.2最大流问题的标号算法............................................................................................73.3最大流问题的Dinic算法........................................................................................10第4章最大流问题的扩展.............................................................................................144.1最小费流..................................................................................................................144.2信息流理论..............................................................................................................16第5章应用举例.............................................................................................................175.1延时容忍网络介绍..................................................................................................175.2单份拷贝和多份拷贝方式选择问题分析..............................................................17网络流及其应用1第1章引言在日常生活中，网络是一个非常常见的概念，例如电网、水管网、交通运输网、通讯网等。在这些网络中，会遇到各种各样的问题，如网络的容量和费用问题等。近年来，在解决网络方面的有关问题时，网络流理论起到了越来越大的作用。我们可以用一个简单的实例来看网络流问题。假设有一个简单的交通网络，该网络只有一个入口和一个出口，其它道路均形成回路返回网络之中。网络中每条道路用它的车道数作为道路的权重，它们反映道路在单位时间内可能通过的最大车流量。我们把单位时间内能通过的车流量称为道路的容量。现在，一些车辆从入口进入网络，经由相同或不同的道路后从出口驶出，这就形成一个实际的流动，称为流。分析这种实际流动，有如下性质：（1）实际流动是一个有向的流动；（2）每条道路上单位时间内通过的流量不可能超过该道路的容量；（3）每个内部节点处流入节点的流量等于流出节点的流量；（4）流入入口的车流量应等于流出出口的车流量，这一流量就是实际流动的车流量。当车流量进一步加大后，由于受道路宽度的限制，加到一定的流量后，再也加不进去了，这就是此交通网络能通过的最大流量。网络流理论正是从这些实际问题中提炼出来的。本文将从图论和网络流的基本概念开始介绍，着重对最大流问题进行分析，并利用网络流理论分析计算机网络特别是延时容忍网络中的流量问题。对于计算机网络来说，网络的容量是一个重要的指标，它给出了网络的最大承载能力。Shannon信息论给出了信道容量的极限。但是，由于每条链路上的容量并不相同，对于网络中的流来说，仅仅知道链路容量并不能解决实际问题。为此，需要有效地利用链路容量，从而承载尽可能多地网络流，这就是网络流理论需要解决的问题。对于计算机网络来说，仅仅考虑流量最大并不能完全符合实际情况，在某些场合，需要考虑链路的开销问题，这就是网络的费用问题，引入费用问题后，网络流的求解变得更为复杂，需要新的方法解决；另一方面，由于不同流中包含的消息可能会有冗余量，这些冗余的消息不能带来信息量的增加，因此，仅仅考虑流的大小也是不科学的，如何尽可能的传输更多有用信息才是网络最终所需要的。为了解决这些问题，我们将从网络流理论的基础知识开始介绍，通过最大流、最小费用流、信息流问题的分析，提炼出计算机网络最大化信息流的有用知识，并将这些知识用于延时容忍网络的流分析和转发策略选择中。第2章图论基础和网络基本概念2.1图论基本概念1.图论介绍图论是一门古老而又具有丰富生命力的学科，它是组合数学的分支，具有极其广泛的应用。图论来源于欧拉的工作，他成功的解决了著名的格尼斯堡七桥问题，从而奠定了图论的基础。基尔霍夫发展了树图理论，并且成功地将其应用到电网络中，这就是著名的基尔霍夫网络流及其应用2电压定律和电流定律。随着计算机技术和计算机网络的发展，图论也被越来越多地用于计算机网络领域。图论中的流理论的很多概念与计算机网络的重要元素能很好的对应，例如路、流等概念恰恰是计算机网络中最重要的因素，因此，流理论相关研究受到了很多计算机网络领域学者的关注。2.图的基本概念一集元素以及他们之间的某种关系称为图。图可以用一个二元组G(V,E)表示，其中集合V称为顶点集，其元素就是图的顶点，集合E称为边集，它是顶点集V中元素组成的某些无序对的集合，边用(i,j)或(j,i)形式表示，其中，i,jV。特别的，如果边的两个端点是同一个顶点，则称这条边为环边。图的顶点又称为节点、点和连接点等；边又称为连线、线、支路、弧、链路等。通常，连接顶点i与顶点j的边用(i,j)表示，而顶点i和j称为边(i,j)的端点。如果图的边具有方向性，则这样的图称为有向图。在有向图中，(i,j)表示从顶点i指向顶点j的边。3.图的图示通常，图的顶点可以用平面上的一个点来表示，边可以用平面上的线段或曲线表示。图2.1.1是一个具有4个顶点和5条边的图。其中，顶点v2和v4是边e3的端点，而连接顶点v2和v3的边有两条，分别是e4和e5，这两条边称为并行边（重边）。v1v2v3v4e1e2e3e4e5图2.1.1图的图示4.一些术语在图论中，有一些专业术语，为了后续讨论方便，我们把后面章节中用到的术语做一个简单的介绍。点与边的关联：在图G中，如果点v是边e的一个端点，则称点v与边e关联。点与点的相邻：如果在图G中有一条边同时连接两点u和v，则称点u和v在图G中是相邻的。入邻点和出邻点：对于有向图，点与点的相邻分为出邻点和入邻点，如果有一条从u指向v的边，则称v为u的出邻点，u为v的入邻点。边与边的相邻：如果两条边有一个公共端点，则称这两条边在图G中相邻。简单图：既没有环边也没有重边的图称为简单图。完全图：任意两点之间都有一条边的简单图称为完全图。顶点v的度：图G中与顶点v关联的所有边的数目（环边计算两次）称为顶点v的度。在有向图中，需要区分指向顶点v的边和相反方向的边，指向顶点的边的数目称为顶点v的入度，反之称为顶点v的出度。底图：如果把一个有向图的每一条有向边的方向都去掉，得到的无向图称为的原有向图的底图。途径（walk）：图G中点边连续交替出现的序列称为G的一条途径。网络流及其应用3迹（trail）：图G中边不重复出现的途径称为迹。实际上，格尼斯堡七桥问题就是求给定的图（七座桥可以看作七条边）的迹。路：图G中顶点不重复出现的迹称为路。将图论应用到计算机网络时，路是一个非常重要的概念，在计算机网络中，路对应于网络的一条路由。而求网络的路由是计算机网络的一个核心问题。因此，在后续讨论中，路的概念会反复出现。2.2网络的基本概念实际应用中经常需要考虑网络和网络上的流，网络是一个很宽泛的概念，例如：油气管道、交通网、因特网等。这些网络往往具