下载文档原格式
⽹络流算法2018-03-13 19:02:13在图论中，⽹络流（英语：Network flow）是指在⼀个每条边都有容量（capacity）的有向图分配流，使⼀条边的流量不会超过它的容量。
通常在运筹学中，有向图称为⽹络。
顶点称为节点（node）⽽边称为弧（arc）。
⼀道流必须匹配⼀个结点的进出的流量相同的限制，除⾮这是⼀个源点（source）──有较多向外的流，或是⼀个汇点（sink）──有较多向内的流。
⼀个⽹络可以⽤来模拟道路系统的交通量、管中的液体、电路中的电流或类似⼀些东西在⼀个结点的⽹络中游动的任何事物。
⼀、最⼤流最⼩割定理最⼤流最⼩割定理提供了对于⼀个⽹络流，从源点到⽬标点的最⼤的流量等于最⼩割的每⼀条边的和。
这个定理说明，当⽹络达到最⼤流时，会有⼀个割集，这个割集中的所有边都达到饱和状态。
这等价于在⽹络中再也找不到⼀个从s到t的增⼴路径。
因为只要能找到⼀条增⼴路径，这条增⼴路径肯定要经过最⼩割集中的⼀条边，否则这个割集就不能称之为割集了。
既然这个割集中所有的边都饱和了，因此也就不会存在这样的增⼴路径了。
这个定理的意义在于给我们指明了⽅向：任何算法，只要最后能达到“再也找不到⼀条增⼴路径”，就可以说明这个算法最后达到了最⼤流。
⼆、最⼤流问题在优化理论中,最⼤流问题涉及到在⼀个单源点、单汇点的⽹络流中找到⼀条最⼤的流。
最⼤流问题可以被看作是⼀个更复杂的⽹络流问题（如循环问题（circulation problem））的特殊情况,。
s-t流（从源点s到汇点t）的最⼤值等于s-t割的最⼩容量，这被称为最⼤流最⼩割定理。
下⾯举例来说明这个问题：问题描述：给定⼀个有向图G=(V,E)，把图中的边看作管道，每条边上有⼀个权值，表⽰该管道的流量上限。
给定源点s和汇点t，现在假设在s处有⼀个⽔源，t处有⼀个蓄⽔池，问从s到t的最⼤⽔流量是多少。
这个问题有如下的⼀些限制：容量限制：也就是在每条通路上的流量都不能超过其capacity。
网络流算法在实际生活中有许多流量问题，例如在交通运输网络中的人流、车流、货物流，供水网络中的水流，金融系统中的现金流，通讯系统中的信息流，等等。
50年代以福特(Ford)、富克逊(Fulkerson)为代表建立的“网络流理论”，是网络应用的重要组成部分。
在最近的奥林匹克信息学竞赛中，利用网络流算法高效地解决问题已不是什么稀罕的事了。
本节着重介绍最大流(包括最小费用)算法，并通过实际例子，讨论如何在问题的原型上建立—个网络流模型，然后用最大流算法高效地解决问题。
［问题描述］如图4-1所示是联结某产品地v1和销售地v4的交通网，每一弧(vi,vj)代表从vi到vj的运输线，产品经这条弧由vi输送到vj，弧旁的数表示这条运输线的最大通过能力。
产品经过交通网从v1到v4。
现在要求制定一个运输方案使从v1到v4的产品数量最多。
一、基本概念及相关定理1)网络与网络流定义1 给一个有向图N=(V，E)，在V中指定一点，称为源点(记为vs，和另一点，称为汇点(记为vt)，其余的点叫中间点，对于E中每条弧(vi，vj)都对应一个正整数c(vi，vj)≥O(或简写成cij)，称为f的容量，则赋权有向图N=(V，E，c，vs，vt)称为一个网络。
如图4-1所给出的一个赋权有向图N就是一个网络，指定v1是源点，v4为汇点，弧旁的数字为cij。
所谓网络上的流，是指定义在弧集合E上一个函数f={f(vi，vj)}，并称f(vi，vj)为弧(vi，vj)上的流量(下面简记为fij)。
如图4-2所示的网络N，弧上两个数，第一个数表示容量cij，第二个数表示流量fij。
2)可行流与最大流在运输网络的实际问题中，我们可以看出，对于流有两个显然的要求：一是每个弧上的流量不能超过该弧的最大通过能力(即弧的容量)；二是中间点的流量为0，源点的净流出量和汇点的净流入量必相等且为这个方案的总输送量。
因此有：定义2 满足下列条件(1)容量约束：0≤fij≤cij，(vi,vj)∈E，(2)守恒条件对于中间点：流入量=流出量；对于源点与汇点：源点的净流出量vs(f)=汇点的净流入量（-vt(f)）的流f，称为网络N上的可行流，并将源点s的净流量称为流f的流值v(f)。
网络流的Edmonds-Karp算法讲解（简称EK算法，时间复杂度为O(m^2n)）首先来看一下基本的网络流最大流模型。
有n个点，有m条有向边，有一个点很特殊，只出不进，叫做源点，通常规定为1号点。
另一个点也很特殊，只进不出，叫做汇点，通常规定为n号点。
每条有向边上有两个量，容量和流量，从i到j的容量通常用c[I,j]表示,流量则通常是f[I,j]。
通常可以把这些边想象成道路，流量就是这条道路的车流量，容量就是道路可承受的最大的车流量。
很显然的，流量<=容量。
而对于每个不是源点和汇点的点来说，可以类比的想象成没有存储功能的货物的中转站，所有”进入”他们的流量和等于所有从他本身”出去”的流量。
把源点比作工厂的话，问题就是求从工厂最大可以发出多少货物，是不至于超过道路的容量限制，也就是，最大流。
比如这个图。
每条边旁边的数字表示它的容量。
下面我们来考虑如何求最大流。
首先，假如所有边上的流量都没有超过容量(不大于容量)，那么就把这一组流量，或者说，这个流，称为一个可行流。
一个最简单的例子就是，零流，即所有的流量都是0的流。
我们就从这个零流开始考虑，假如有这么一条路，这条路从源点开始一直一段一段的连到了汇点，并且，这条路上的每一段都满足流量<容量，注意，是严格的<,而不是<=。
那么，我们一定能找到这条路上的每一段的(容量-流量)的值当中的最小值del ta。
我们把这条路上每一段的流量都加上这个del ta，一定可以保证这个流依然是可行流，这是显然的。
这样我们就得到了一个更大的流，他的流量是之前的流量+delta，而这条路就叫做增广路。
我们不断地从起点开始寻找增广路，每次都对其进行增广，直到源点和汇点不连通，也就是找不到增广路为止。
网络流算法（NetworkFlow）网络流算法，是指寻找网络流问题的解的算法，它是一类重要的组合优化问题，被广泛应用于计算机科学及工程领域。
网络流是个有向图，它模拟了许多实际问题，如输电方案、货物运输、油管输送和信息传输等。
网络流算法的目的是在给定的网络流中，尽可能地将流量从源点流向汇点，同时满足各个节点的容量约束和流量平衡约束。
本文将介绍网络流模型的构建和基本算法。
一、网络流模型的构建网络流模型是一个有向图G=(V,E)，其中V表示节点集合，E表示边集合。
每条边都有一个容量c(e)表示其流量的最大值。
设源点为s，汇点为t，则网络流模型可以表示为一个三元组(N,s,t)，即：N=(V,E) s∈V t∈V s≠t在网络流模型中，源点始终是起点，汇点始终是终点。
我们在模型中引入一个源汇节点s'和汇源节点t'，并连接源点和汇点，得到源汇图G'=(V,E')，其中：E'=E∪{(s',s,c(s,t))}∪{(t,t',c(s,t))}即，在原图的基础上，加入两个新的虚拟节点s'和t'，并连接到源点和汇点。
这样构造的网络流模型中，所有的节点都满足容量和流量平衡约束。
在网络流问题中，我们需要求解最大流或最小割，以满足约束条件，并且尽可能地提高网络的利用率。
二、网络流的基本概念和算法1. 流量和容量网络流图中，首先需要确定每条边的容量和流量。
流量指的是通过该边的流量大小，容量指的是该边能够承受的最大流量。
在网络流模型中，每条边的容量是一个正实数，而流量可以是任意实数。
流量和容量通常表示为f(e)和c(e)。
2. 割在网络流模型中，割是一种对源汇图做出的划分，其中源点s和汇点t被分为两个集合S和T。
网络流通过割的概念来定义障碍物，即对流量的限制。
在网络流图中，割C(S,T)是指将源点s和汇点t割成两部分的划分，C(S,T)满足：s∈S t∈T S∩T=∅根据割的定义，可将所有割分为最小割和最大割。
图论中网络流算法及优化图论中的网络流算法及优化一、引言网络流算法是图论中的重要分支，它被广泛应用于解决各种实际问题，如交通流、电力传输等。
本文将介绍网络流算法的基本概念和常用的优化方法。
二、网络流算法1. 最大流问题最大流问题是网络流算法中最基本的问题之一。
其目标是在给定网络中找到从源点到汇点的最大流量。
常用的解决方法包括：（1）Ford-Fulkerson算法：该算法通过不断寻找增广路径来增加流量，直到无法再找到增广路径为止。
（2）Edmonds-Karp算法：在Ford-Fulkerson算法的基础上，引入了BFS搜索策略来寻找增广路径，提高了算法的效率。
2. 最小割问题最小割问题与最大流问题密切相关。
最小割是指将网络划分为两个部分，并且使得网络中横跨这两个部分的边的权重之和最小。
常用的解决方法包括：（1）Ford-Fulkerson算法：该算法在求解最大流问题的同时可以得到最小割的结果。
（2）Dinic算法：通过构造分层图和阻塞流的概念，提高了算法的效率。
三、网络流算法的优化网络流算法在实际应用中可能面临大规模问题的挑战，因此需要采用一些优化方法来提高算法的效率和准确性。
1. 改进的数据结构使用合适的数据结构可以减少算法的时间和空间复杂度。
例如，使用邻接矩阵或邻接表来存储图的信息，选择合适的数据结构来表示流量、残余网络等。
2. 快速增广快速增广是一种对增广路径进行选择的策略，可以减少算法的时间复杂度。
常见的快速增广方法包括Dinic算法和HLPP算法。
3. 预流推进预流推进是一种改进的增广策略，它通过将多余的流量分配到其他边上，减少了增广路径的数量。
常用的预流推进算法包括Push-Relabel 算法和Preflow-Push算法。
4. 分阶段算法对于大规模的网络流问题，可以采用分阶段算法来解决。
分阶段算法将整个问题划分为多个子问题，并结合贪心、动态规划等方法进行求解。
四、总结网络流算法在图论中扮演着重要的角色，可以解决许多实际问题。
网络流常用算法：
1.Fort_Fulkerson算法.
2.Edmonds_Karp算法(最短增广路算法).-------------------O( n*m^2 )
3.SAP算法(使用距离标号的最短增广路算法).--------------O( n^2*m )
4.Dinic算法.------------------------------------------O( n^2*m )
5.Push_Relabel算法(预流推进算法).---------------------O( n^2*m )
6.FIFO Preflow_Push算法.-------------------------------O( n^2*m)
7.Relabel_to_Front算法.--------------------------------O( n^3 )
8.Highest Label Preflow_push算法.----------------------O( n^2*m^1/2)
网络流算法讲座材料
1 概念与性质
网络N是指具有以下结构的有向图D，D中有两个称为源和汇的不同顶点s, t，在D的弧集E上定义了非负整数值函数c。
网络N的流是定义在弧集E上的整数值函数，满足对任意边a，
0<=f(a)<=c(a)，且对任意顶点，入流量等于出流量。
性质1：任何st-流都具有如下性质：从s的出流量等于到t的入流量。
性质2：任何st-流都有一个最大流，它可以表示为从s到t，至多E条有向路径集合上的流。
图的切割是将顶点分成两个独立的集合，交叉边是一条连通两个集合中顶点的边，交叉边的集合叫做切割集合。
网络N的st-切割是这样的一个切割，它将源s放到一个集合，将汇t放到另一个集合。
与st-切割对应的每条交叉边或者是st-边(从集合s指向集合t)，或者是ts-边(从集合t指向集合s)，st-切割的容量是st-边的容量之和，st-切割的流量等于st-边上的流量和与ts-边上的流量和之差。
性质3：网络中所有st-流的最大值等于所有st-切割的最小容量。
残余网络
边费用是定义在边集E上的整数值函数h。
流的费用是该流的所有边的流值与边费用乘积的总和。
最小费用最大流是费用最小的最大流。
性质4：当且仅当残余网络不包含负开销的有向环时，最大流才是一个最小费用流。
2 最大流应用
2.1 一般网络的最大流
描述：给定一个含多个源和多个汇的网络，找出其中的最大流。
解法：在原网络的基础上，增加一个虚源s和一个虚汇t。
若原网络有p个源s1, s2, …, sp和q个汇t1, t2, …, tq，则在原网络中增加p条以s为起
点的边(s,s1), (s,s2), …, (s,sp)，以及q条以t为终点的边(t1,t),
(t2,t), …, (tq,t)，新增各边的容量分别定义为各源si的流出量和各汇t的流入量。
新网络的s-t最大流与原网络的最大流等价。
例题：HOJ 1229, Power Network
2.2 顶点容量约束的最大流问题
描述：给定一个某些顶点存在容量约束的流网络，找出其最大流。
解法：在原网络的基础上，将具有顶点容量约束的顶点u拆成两个顶点u, u*, 原顶点u 的入边仍为u的入边，原顶点u的出边改为u*的出边，增加一条边(u, u*)，其边容量为原顶点u的顶点容量。
新网络的s-t最大流与原网络的最大流等价。
例题：
2.3 可行流问题
描述：在一个流网络中给每个顶点分配权重，如果为正值，可以解释为供给，如果为负值，可以解释成需求，顶点权重的总和等于0。
如果每个顶点的出流和入流差等于该顶点的权重(如果为正，则为供给，如果为负，则为需求)，定义此流为可行流。
已知这样一个网络，判断是否存在一个可行流。
解法：已知一个可行流问题，构建一个具有相同顶点和边，但顶点上不带权重的网络。
添加一个源s和一个汇t，s有一条边到达每个供给顶点，其边容量等于该顶点的供给，t有一条边从需求顶点出发，其边容量等于该顶点的需求。
当且仅当新网络的s-t最大流为满流时(充满从源s出发的所有边及到达汇t的所有边)，原网络才有一个可行流。
例题：
2.4 带下界约束的最大流问题
描述：求边有容量下限的网络的最大流。
解法：设边(u, v)的容量上下限分别为c, l，再添加一个源s'和汇t'，将(u, v)的下限去掉，上限改为c-l，增加两条边(u, t')，(s', v)，容量均为l。
这样，将原网络带下限约束的最大流转换为双源点无容量下限的最大流。
例题：
2.5 循环流问题
描述：考虑无源也无汇的网络，设N是具有基础有向图D=(V，A)的网络，l 和c是定义在A上的非负整数值且对任意边a，l(a)<=c(a)，分别称l和c为下容量函数和上容量函数。
如果定义在A上的函数f满足：
f(v, V) - f(V, v) = 0, V中任意顶点v
l(a) <= f(a) <= c(a)
则称f为网络N的循环流。
对一般的网络N，循环流未必存在。
给一个这样的网络，判断循环流是否存在。
解法：添加一个源s和汇t，对于每个下限容量l不为0的边(u, v)，将其下限去掉，上限改为c-l，增加两条边(u, t)，(s, v)，容量均为c。
这样，原网络存在循环流等价于新s-t网络的最大流是满流。
例题：
2.6 带下界约束的最小流问题
2.7 二分图的最大匹配
描述：利用最大流求一个二分图的最大匹配。
解法：已知一个二分图匹配问题，让所有的边从一个集合U指向另一个集合T，再添加一个源s和一个汇t，s有一条边指向U中所有顶点的边，t有一条边从T中所有顶点指向它自身，最后给图中所有边分配容量1。
新s-t网络中的最大流对应于原二分图的一个最大匹配。
例题：
2.8 图的连通性问题
HOJ 1646，Cable TV Network
3 最小费用流应用
3.1 运输问题
描述：公司有工厂和零售部门，工厂生产的商品必须通过一定的运输渠道到达零售部门进行销售。
不同的运输渠道具有不同的容量和单位开销。
问是否可以从工厂配送商品到零售问题，使得供应满足每个地方的需求，并找出这样做的最低开销途径。
解法：转化为多源多汇的最小费用最大流问题。
例题：PKU 2516, Minimum Cost
3.2 二分图的最小权最大匹配
描述：利用最大流求一个二分图的最大匹配。
解法：已知一个二分图匹配问题，让所有的边从一个集合U指向另一个集合T，再添加一个源s和一个汇t，s有一条边指向U中所有顶点的边，t有一条边从T中所有顶点指向它自身，最后给图中所有边分配容量1。
新s-t网络中的最大流对应于原二分图的一个最大匹配。
例题：HOJ 2025, Going Home。
