posts - 18,  comments - 5,  trackbacks - 0
 一、    定义与定理

流网络:G=(V, E)是一个有向图,其中每条边(u, v)E均有一个非负容量c(u, v) 0,否则c(u, v)0.流网络中有两个特别的顶点:源点s和汇点t。对于每个顶点vV,都存在一条路径s…v…t

流:G上的一个实值函数(V×VR),满足1)对于任意u, vVf(u, v)c(u, v)2)对于任意u, vVf(u, v)=-f(u, v)3)对于任意uV-{s, t},∑f(u, i)=0。定义流|f|=f(s, i)

残留网络:给定流网络和一个流,其残留网络由可以容纳更多网络流的边组成。定义残留容量cf(u, v)=c(u, v)-f(u, v)。残留网络Gf=(V,Ef),其中Ef={(u, v)V×V:cf(u, v)>0}

增广路径:增光路径p为残留网络Gf中从st的一条简单路径。

流网络的割:流网络的割(S, T)V划分为ST=V-S两部分,使得sStT。穿过割的净流定义为f(S, T),且有f(S, T)=|f|。割的容量为c(u, v)。一个网络的最小割就是网络中所有割中流量最小的割。

最大流最小割定理:以下三个条件等价:1)fG的一个最大流;2)残留网络Gf不包含增广路径;3)G的某个割(S, T),有|f|=c(S, T)

前置流:是一个函数fV×VR,它满足1)对于任意u, vVf(u, v)c(u, v)2)对于任意u, vVf(u, v)=-f(u, v)3)对于任意uV-{s, t}f[V, u]0。定义余流e[u]=f[V, u],对于uV-{s, t},当e[u]>0时,称顶点u溢出。

高度函数:函数hVN满足h[s]=|V|h[t]=0,且对每条残留边(u, v)Ef,有h[u]h[v]+1

容许边:如果cf(u, v)>0h[u]=h[v]+1,则称(u, v)是容许边。否则,(u, v)是非容许边。容许网络为Gf,h=(V, Ef,h),其中Ef,h为容许边的集合。根据容许边有关高度的定义,易知,容许网络不存在回路。
  
二、     Ford-Fulkerson方法

1) 基本的Ford-Fulkerson算法
      描述:

1 FORD-FULKERSON(G, s, t)
2     for each edge(u, v) in E(G)
3         do f[u, v] = 0
4            f[v, u] = 0
5     while exists a path p from s to t in Gf
6         do cf(p) = min{cf(u, v) : (u, v) in p}
7            for each edge(u, v) in p
8                do f[u, v] = f[u, v] + cf(p)
9                   f[v, u] = - f[u, v]

     分析:Ford-Fulkerson过程的效率取决于如何确定增广路径。如果选择不好,对于非有理的容量,算法有可能不能终止。如果容量是整数(如果容量不是整数,可以乘以特定的因子转化为整数)。这时,第2~4行运行时间为O(E),第5~9行,while循环至多执行|f*|,这是因为在每次迭代后,流值至少增加1。故算法效率为O(E|f*|)。当最大流f*较小时,这个算法的效率还是不错的。

2)Edmonds-Karp算法

     描述:将基本的Ford-Fulkerson算法的第5行中用广度优先搜索来实现增广路p的计算,即增广路径是残留网络中从s到t的最短路径(其中每条边为单位距离或权),则能够改进Ford-Fulkerson算法的界。
     分析:随着算法的运行,对于所有顶点v∈V-{s, t},残留网络Gf中的最短路径长度δf(s, v)随着每个流的增加而单调递增。直观看来,每次增加流的操作都将使得当前最短路中的一条边(即关键边,cf(a, b)=cf(p))从p中消失,从而使得新生成的Gf中的最短路径的长度增加。同时,任意边(u, v)至多能成为|V|/2-1次成为关键边。这是因为第i次成为关键边时有δf(s, v)=δf(s, u)+1,而第i+1次时f[u, v]只可能与上次异号,则有δf'(s, u)=δf'(s, v)+1,且有δf'(s, v)≥δf(s, v),则δf'(s, u)=δf'(s, v)+1)≥δf(s, v)+1=δf(s, u)+2。故(u, v)每次成为关键边都将使得δf(s, u)增加2,有由于δf(s, u)最大值为|V|-2,则任意边(u, v)至多能成为|V|/2-1次成为关键边。故该算法的时间复杂性为O(VE2)。
      示例:POJ 1273 解题报告

三、     Push-Relabel算法
      描述:

1 //Push操作
2 PUSH(u, v)
3     if cf(u, v)<=0 or h[u] != h[v]+1
4         then return
5     df(u, v) = min{e[u], cf(u, v)}
6     f[u, v] = f[u, v] + df(u, v)
7     f[v, u] = -f[u, v]
8     e[u] = e[u] - df(u, v)
9     e[v] = e[v] + df(u, v)

1 //Relabel操作
2 RELABEL(u)
3     if e[u]==0 or there is no v that (u, v) in Ef and h[u]>h[v]
4         then return
5     h[u] = 1 + min{h[v] : (u, v) in Ef}

 1 //初始化前置流
 2 INTIALIZE-PREFLOW(G, s)
 3     for each vertex u in V[G]
 4         do h[u] = 0
 5            e[u] = 0
 6     for each edge(u, v) in E[G]
 7         do f[u, v] = 0
 8            f[v, u] = 0
 9     h[s] = |V[G]|
10     for each vertex u in Adj[s]
11         do f[s, u] = c[s, u]
12            f[u, s] = -c[s, u]
13            e[u] = c(s, u)
14            e[s] = e[s] - c(s, u)

1 //Push-Relabel算法
2 PUSH-RELABEL(G, s)
3     INTIALIZE-PREFLOW(G, s)
4     while there exists an applicable push or relabel operation
5         do select an applicable push or relabel operation and perform it

      正确性:用循环不变式来说明
      1)初始化:INITILIZATION-FREFLOW初始化f为前置流
      2)保持:算法中只使用了push与relabel操作,relabel操作只影响高度,不影响f;而push(u, v)操作,只会增加点v的流入量即f(V, v),
所以如果操作以前是前置流,操作后还是前置流
      3)终止:在终止时,V-{s, t}中的每个顶点的余流必为0(如果存在不为0的点,则必可以进行push或relabel操作),且最终得到的是一个前置流,故最终得到的是一个流。又在最终的残留网络中,不存在s到t的路径(否则,如存在一条路径s,v1,...,t,则s可以向压入流,使得v1溢出),根据最大流最小割定理,f是最大流。
      分析:首先,证明对于任意溢出点u,均存在一条在Gf上的u到s的路,设U={v|在Gf存在一条s到v的路径},设U#=V-U,假设s不属于U,对于顶点对(v, w),v属于U,w属于U#,有f(v,  w)≤0,否则,如果f(v, w)>0,则有cf(v, w)=c(v, w)-f(v, w)=c(v, w)+f(w, v)>0,这与w不属于U矛盾!e[u] =f(V, U)=F(U, U)+f(U#, U)=F(U#, U)≤0,而对于v∈V-{s},e[v]≥0,又e[u]>0,则U中必有s,矛盾!
      relabel操作:对于源点与会点,不存在relabel操作,而对于其它顶点u,初始时,h[u]=0≤2|V|-1,当u进行relabel时,u溢出,则Gf中必存在一条u到s的路径p=<u=v0,v1,...,vk=s>,由高度函数的定义(u, v)∈Ef,有h[u]≤h[v]+1,则h[u]=h[v0]≤h[vk]+k≤h[s]+|V|-1=2|V|-1,算法中总共的relabel操作次数为O(V2)。
      饱和push操作:进行操作后,(u, v)边从Ef中消失,则称该push操作为饱和push操作,进行一次(u, v)的饱和push操作必有h[u]=h[v]+1,同时,要进行下一次(u, v)的饱和push操作,必先经过一次(v, u)的饱和push操作,则两次饱和操作室h[u]增加2,又h[u]≤2|V|-1,则每个顶点至多进行|V|次饱和push操作,则总共的饱和push操作次数为O(|V||E|)。
      不饱和push操作:push操作中除去饱和push操作,剩下的就是不饱和push操作。定义一个函数g,值为所有e值大于0的顶点的高度和,故g≥0。考察三种操作对g值的影响:1)relabel操作不会改变溢出性且只会改变一个点,而一个点的变化至多为2|V|-1,则g至多增加2|V|-1;2)饱和push操作可能能增加一个溢出点,g至多增加2|V|-1;3)不饱和push(u, v)操作会使u变为不溢出,而在v从不溢出到溢出时,减小的最少,为1(因为h[u]=h[v]+1)。则不饱和push操作的次数至多为O(|V|2|E|+|V|3)。
      综上,Push-Relabel算法是正确的且效率为O(V2E)。
      示例:POJ 1459 解题报告

四、     Relabel-To-Front算法
      描述(Push、Relabel与Initalize-Flow操作参看Push-Relab):
 1 //Discharge操作
 2 DISCHARGE(u)
 3     while e[u]>0
 4         do v = current[u]
 5            if  v == NIL
 6               then RELABEL(u)
 7                    current[u] = head[N[u]]
 8            else if cf(u, v)>0 and h[u]=h[v]+1
 9               then PUSH(u, v)
10            else
11               current[u] = next-neighbor[v]

 1 //Relabel-To-Front算法
 2 RELABEL-TO-FRONT(G, s, t)
 3     INITIALIZE-PREFLOW(G, s)
 4     L = V[G]-{s, t}, in any order
 5     for each vertex u in V[G]-{s, t}
 6         do current[u] = head[N[u]]
 7     u = head[L]
 8     while u != NIL
 9         do old-height = h[u]
10            DISCHARGE(u)
11            if h[u] > old-height
12                then move u to the front of list L
13            u = next[u]

      正确性:Relabel-To-Front算法只有在Push与relabel操作时才会改变f,故它是Push-Ralabel的一个实现,所以只要证明当算法终止时只要再无Push与Relabel操作即可。用循环不变式证明:
      1)初始化:运行INITIALIZE-PREFLOW后,无容许边,故任意顶点序列就是拓扑排序的顶点。
      2)保持:容许网络可通过Push和Relabel操作改变,对于Push操作,不会产生容许边,故u的前面的顶点与u不会有余流;而对于Relabel(u)操作,不会产生进入u的容许边,只会产生离开u的容许边,注意Relabel-To-Front算法的12行,将u移入L的前端,保证任意离开u的容许边都满足拓扑排序,同时,保证u的前面与u没有余流。
      3)终止:循环终止时,u恰好在L最后,于是,L中所有的顶点均无余流,也就再无Push与Relabel操作。
      分析:该算法是Push-Relabel算法的一种实现,所以每个顶点Relabel操作的界为O(V),则全部顶点的Relabel操作的界为O(V2)。如算法的11~13行表明两次Relabel操作之间,最多进行|L|次,即|V|次Discharge操作。每次Discharge操作至多只会有1不饱和Push操作,则不饱和操作的界为O(V3),同时通过Push-Ralabel算法对饱和Push操作的分析,整个算法的界为O(V3+VE)=O(V3)。
      示例:
POJ 1149 解题报告
      
posted on 2009-06-26 19:49 Icyflame 阅读(3503) 评论(0)  编辑 收藏 引用 所属分类: 图论

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理