网络流的定义

发布网友 发布时间：2022-04-19 09:42

我来回答

共1个回答

热心网友 时间：2023-09-19 11:50

图论中的一种理论与方法，研究网络上的一类最优化问题 。1955年 ，T.E.哈里斯在研究铁路最大通量时首先提出在一个给定的网络上寻求两点间最大运输量的问题。1956年，L.R. 福特和 D.R. 富尔克森等人给出了解决这类问题的算法，从而建立了网络流理论。所谓网络或容量网络指的是一个连通的赋权有向图 D= （V、E、C） ， 其中V 是该图的顶点集，E是有向边(即弧)集，C是弧上的容量。此外顶点集中包括一个起点和一个终点。网络上的流就是由起点流向终点的可行流，这是定义在网络上的非负函数，它一方面受到容量的*，另一方面除去起点和终点以外，在所有中途点要求保持流入量和流出量是平衡的。如果把下图看作一个公路网，顶点v1…v6表示6座城镇，每条边上的权数表示两城镇间的公路长度。现在要问 ：若从起点v1将物资运送到终点v6去 ，应选择那条路线才能使总运输距离最短?这样一类问题称为最短路问题 。 如果把上图看作一个输*道网 ， v1 表示发送点，v6表示接收点，其他点表示中转站 ，各边的权数表示该段管道的最大输送量。现在要问怎样安排输油线路才能使从v1到v6的总运输量为最大。这样的问题称为最大流问题。
最大流理论是由福特和富尔克森于 1956 年创立的 ，他们指出最大流的流值等于最小割(截集)的容量这个重要的事实，并根据这一原理设计了用标号法求最大流的方法，后来又有人加以改进，使得求解最大流的方法更加丰富和完善 。最大流问题的研究密切了图论和运筹学，特别是与线性规划的联系，开辟了图论应用的新途径。
假设G(V,E) 是一个有限的有向图，它的每条边(u,v)∈E都有一个非负值实数的容量c(u,v) 。如果(u,v)不属于E，我们假设c(u,v) = 0 。我们区别两个顶点：一个源点s和一个汇点t。一道网络流是一个对于所有结点u和v都有以下特性的实数函数f:V×V→R 容量* (Capacity Constraints): f(u,v)≤c(u,v)一条边的流不能超过它的容量。 斜对称 (Skew Symmetry): f(u,v)=-f(v,u)由u到v的净流必须是由v到u的净流的相反（参考例子）。（既然要看网络流，这是一定要知道的） 流守恒 (Flow Conservation): 除非u=s或u=t，否则Σ（w∈V）f(u,w)=0 一结点的净流是零，除了“制造”流的源点和“消耗”流的汇点。 注意f(u,v) 是由u到v的净流。如果该图代表一个实质的网络，由u到v有 4 单位的实际流及由v到u有 3 单位的实际流，那么f(u,v) = 1 及f(v,u) = − 1。
边的剩余容量 (Resial Capacity)是cf(u,v) =c(u,v)−f(u,v)。这定义了以Gf(V,Ef)表示的剩余网络 (Resial Network)，它显示可用的容量的多少。留意就算在原网络中由u到v没有边，在剩余网络乃可能有由u到v的边。因为相反方向的流抵消，减少由v到u的流等于增加由u到v的流。扩张路径 (Augmenting Path)是一条路径 (u1,u2...uk)，而u1 =s、uk=t及cf(ui,ui+ 1) > 0，这表示沿这条路径传送更多流是可能的。