网络流算法介绍.ppt

网络流算法介绍 1.基本概念 2.最大流问题求解 3.二分图匹配 4.二分图最佳匹配 网络流问题 类比：求最短路径 把实际问题的道路地图抽象为有向图，然后用一定算法求解最短路径。 我们也可以将一个有向图看作一个流网络来解决另一类型的问题 。 匹配问题、运输问题、任务分配问题。。。 流网络定义（Flow Network） V表示整个图中的所有结点的集合. E表示整个图中所有边的集合. G = (V,E) ,表示整个有向图. s表示网络的源点, t表示网络的汇点. 对于每条边(u,v),有一个容量c(u,v) (c(u,v)=0) 如果c(u,v)=0，则表示(u,v)不在网络中。 如果原网络中不存在边(u,v)，则令c(u,v)=0 对于每条边(u,v),有一个流量f(u,v). 流网络示例 网络流三个性质 容量限制：f(u,v) = c(u,v) 对称性：f(u,v) == -f(v,u) 收支平衡: 对于不是源点也不是汇点的任意结点,流入该结点的流量和等于流出该结点的流量和。 只要满足这三个性质,就是一个合法的网络流. 网络的流量、最大流 一个合法的网络流量|f|定义为： 从源点流出的流量 ∑f(s,v) 流向汇点的流量 ∑f(v,t) |f|的最大值表示为最大流 流网络示例 残量网络 对于网络中的每一条边，计算容量与流量的差即表示为残量。 R(u,v) = C(u,v) – F(u,v) 形象的说，一条边的残量即为该边还能流过的流量。 残量网络举例 残量网络 后向弧 其中像(v1,s)这样的边称为后向弧,它表示从v1到s还可以增加4单位的流量。 但是从v1到s和原网络中的弧的方向相反。这样的弧称为后向弧。 问题：有必要建后向弧线？ 为什么要建立后向弧 在寻找最大流的过程中，有些弧的选择一开始可能就是错误的。 所以在路径中加上后向弧，作为标记。 当发现了另一条可增广的路径是并包含后向弧，意味这条路径对以前对这条弧顶选择进行取消 后向弧为算法纠正自己所犯的错误提供了可能性，它允许算法取消先前的错误的行为 增广路径 在残量网络中，从源点S出发到汇点T的一条路径。 增广路径上的最小残量表示该网络还可增加的额外流量。 点集间的流量 定义点集间的流量：f(X, Y) = ∑ ∑f(x, y) 则有： f(X,X) = 0 (流的对称性) f(X,Y) = -f(Y,X) (流的对称性) f(X∪Y,Z) = f(X,Z) + f(Y,Z) f(X,Y∪Z) = f(X,Y) + f(X,Z) 点集间的流量 不包含s,t的点集，与它关联的边上的流量和为零 证明：f(X, V) = ∑ {∑f(x,v)} = ∑0 (流量收支平衡) = 0 网络中的割 割（S,T）由两个点集S,T组成，满足 1、 S + T = V 2、 源点在S集合中 3、 汇点在T集合中 4、 f(S,T)表示割的流量 5、 c(S,T)表示割的容量 最小切割时使c(S,T)最小的切割 割的流量 任意割的流量等于网络的流量 证明： f(S,T) = f(S,V) – f(S,S) = f(S,V) + 0 = f(s, V) + f(S-{s}, V) = f(s, V) + 0 = |f| 割的流量 网络的流量小等于任意割的容量 证明： |f| = f(S, T) = ∑ ∑f(x, y) = ∑ ∑c(x, y) = c(S, T) 所以有最小割等于最大流 最小割最大流定理 网络的最大流等于最小割 f是网络的最大流 残量网络中无可增广路径 存在某个切割(S,T),使f = c(S, T) 以上三个命题是等价的，证明之： 1 — 2 反证法 假设残量网络中还有增广路径， 增广路径上的流量至少为1 由该路径增广后的流量f 与f是最大流矛盾 2 — 3 此时的残量网络中不存在s-t通路 定义S为s可达的点集 定义T为可达t的点集 显然S＋T = V (S,T)中所有弧都满载，否则残量网络将不为0，使s-t有通路 所以|f| = c(S,T) 3 — 1 由|f| = c(S,T)（任意割） 当|f| == c(S,T) |f|为最大值 从上面的证明，我们可以得到求最大流从增广路径算法。 从2-3的证明给出了从最大流构造最小割的过程，即求出s的可达点集S， 再令T = V - S 求