资源描述
最大流问题苏鹏鹏2015.4.121大纲u最大流的概念u最大流算法Ford-Fulkerson算法Edmonds-Karp算法Push-Relabel算法Relabel-to-Front算法2流网络有向图G（V ,E）每条边有非负容量c(u，v)0不存在双向边stv4v3v2v1167204134149123源点汇点最大流的概念|E|V|1流f（u，v）,满足：容量限制：f(u,v)c(u,v)流量守恒:流入流量之和=流出流量之和最大流问题：给定流网络G，源点s，汇点t，问从s到t最多能输送多大的流？stv4v3v2v111/167/715/201/48/134/411/144/912/124最大流的概念f=11+8=19管道中液体的流动 电网中电流的流动 通信网络中的信息流动 运输路线上货物的流动大纲u最大流的概念u最大流算法Ford-Fulkerson算法Edmonds-Karp算法Push-Relabel算法Relabel-to-Front算法5残存容量cf(u，v)与残存边6sv4v3v2v111/167/715/201/48/134/44/912/12t11/14sv4v3v2v1553745t1111811242715流网络G=(V,E)，f=19残存网络Gf=(V,Ef)Ford-Fulkerson算法uv11/16uv16-11=511残存网络Gf=(V,Ef)uv0/16uv16-0=16uv16/16uv16|Ef|2|E|7增广路径:残留网络G f中一条从s 到t 的路径sv4v3v2v10/160/70/200/40/130/40/90/12t0/14sv4v3v2v1162041349t12147流网络，f=0残存网络Ford-Fulkerson算法Ford-Fulkerson算法8增广路径:残留网络G f中一条从s 到t 的路径sv4v3v2v10/160/70/200/40/130/40/90/12t0/14sv4v3v2v1162041349t12147流网络，f=0残存网络Ford-Fulkerson算法Ford-Fulkerson算法12/1612/2012/12流网络，f=1212/169增广路径:残留网络G f中一条从s 到t 的路径sv4v3v2v10/712/200/40/130/40/912/12t0/14sv4v3v2v14841349t12147流网络，f=12残存网络Ford-Fulkerson算法Ford-Fulkerson算法16127/77/137/14流网络，f=1912/1610增广路径:残留网络G f中一条从s 到t 的路径sv4v3v2v112/200/40/40/912/12tsv4v3v2v1484649t1277残存网络Ford-Fulkerson算法Ford-Fulkerson算法16127/77/137/14流网络，f=197716/204/411/1311/14流网络，f=2316/204/411/1311/14流网络，f=2312/1611增广路径:残留网络G f中一条从s 到t 的路径sv4v3v2v10/40/912/12tsv4v3v2v1444249t1237残存网络Ford-Fulkerson算法Ford-Fulkerson算法16167/71111当在残存网络中找不到增广路径停止。此时获得最大流最大流最小切割定理：f是最大流残存网络中不存在增广路径16/204/411/1311/14流网络，f=2312/1612sv4v3v2v10/40/912/12tsv4v3v2v1444249t1237残存网络Ford-Fulkerson算法分析Ford-Fulkerson算法16167/71111时间复杂度：O(E|f*|)在残存网络中找一条增广路径的时间复杂度：O(V+Ef)=O(E)每次添加的流值是1，则一共要找|f*|次增广路径。大纲u最大流的概念u最大流算法Ford-Fulkerson算法Edmonds-Karp算法Push-Relabel算法Relabel-to-Front算法1314Ford-Fulkerson算法广度优先搜索Edmonds-Karp算法增广路径p方法不限svut999 999999 9991 1 1 999 999999 9991 1 svut999 999999 9991 1 1 1 000 0001 000 000Edmonds-Karp算法f=1 残存网络f=2 残存网络svu1 000 000t1 000 0001 000 0001 000 0001 f=0 残存网络15Edmonds-Karp算法分析时间复杂度：O(VE2)找增广路径的时间复杂度：O(E)定理：EK算法执行的流量递增操作的总次数是为O(VE)证明：一条边成为关键边的次数最多|V|/2;残存网络中最多有2|E|边可以成为关键边关键边的总数：O(VE)大纲u最大流的概念u最大流算法Ford-Fulkerson算法Edmonds-Karp算法Push-Relabel算法Relabel-to-Front算法1617Push-Relabel算法边：有一个预流，满足：弱化的流量守恒：流入结点u的流流出该结点u的流结点：超额流e(u)=流入u的流 流出u的流当e(u)0,称结点u溢出高度h：高 流向 低u128/814/1610/11uv1v2321018Push-Relabel算法u4v22/8PUSH(u，v)u溢出，cf(u,v)0残存边,u的高度是v的高度+1cf(u,v)=8-2=60有残存边，40有残存边,106非饱和推送饱和推送v326/8cf(u,v3)=3有残存边u.h=v1.h+1v1是由残存边的邻接点中的最低点6534210S S-29-29v3v30 0v2v21313t t0 0v4v40 0v1v1161616/160/413/130/120/90/140/70/200/419Push-Relabel算法PUSH(u，v)u溢出，有残存边,u的高度是v的高度+1RELABEL(u)检查v1，v2，v3，v4是否满足条件直到v1，v2，v3，v4超额流都是0停止u溢出u不能向邻接点推送206534210S S-2323v3v30 0v2v20 0t t2323v4v40 0v1v10 012/160/97/719/204/411/1412/120/411/13最大流23PUSH(u，v)RELABEL(u)u溢出，有残存边,u的高度是v的高度+1Push-Relabel算法O(VO(V2 2E)E)u溢出u不能向邻接点推送21Push-Relabel算法分析时间复杂度：O(V2E)前面提到三类操作：重贴标签，饱和推送，非饱和推送三个引理分别给出三个操作的次数界重贴标签次数界：O(V2)饱和推送次数 界：O(VE)非饱和操作次数 界：O(V2E)三个操作在O(1)完成，最终时间复杂度是O(V2E)大纲u最大流的概念u最大流算法Ford-Fulkerson算法Edmonds-Karp算法Push-Relabel算法Relabel-to-Front算法2223Relabel-To-Front算法Push-Relabel算法对基本操作限定一定的次序Relabel-To-Front算法允许任意次序执行基本操作246534210S-29v30v213t0v40v11616/160/413/130/120/90/140/70/200/4PUSH(u，v)RELABEL(u)释放操作DISCHARGE(u)Relabel-To-Front算法6534210S-29v30v213t0v40v11616/160/413/130/120/90/70/200/40/14释放结点v1：将v1的额外流推送到相邻接点上25Relabel-To-Front算法266534210S-29v30v213t0v40v11616/160/413/130/120/90/70/200/40/14释放结点v1：将v1的额外流推送到相邻接点上Relabel-To-Front算法v312v1412/12276534210S-29v312v213t0v40v1416/160/413/1312/120/90/70/200/40/14释放结点v1：将v1的额外流推送到相邻接点上Relabel-To-Front算法S-25v1012/16286534210S-25v312v213t0v40v1012/160/90/70/200/40/1412/120/413/13释放结点v1：将v1的额外流推送到相邻接点上Relabel-To-Front算法v1v2v3v4head296534210s-25v312v213t0v40v1012/160/90/70/200/40/1412/120/413/13释放结点v2Relabel-To-Front算法v1v2v3v4head306534210s-25v312v213t0v40v1012/160/90/70/200/40/1412/120/413/13释放结点v2Relabel-To-Front算法v1v2v3v4head高度提升，前置v2v1v20v41313/14为什么要前置？v20v41313/14316534210s-25v312t0v1012/160/90/70/200/412/120/413/13释放结点v2Relabel-To-Front算法如果不前置.v1v2v3v4head326534210S-25v312v20t0v413v1012/160/90/70/200/413/1412/120/413/13释放结点v3Relabel-To-Front算法v2v1v3v4head336534210s-25v30v20t12v413v1012/160/90/712/200/413/1412/120/413/13释放结点v3Relabel-To-Front算法v2v1v3v4head高度提升，前置v2v1v3346534210S-25v30v20t12v413v1012/160/90/712/200/413/1412/120/413/13释放结点v4Relabel-To-Front算法v1v2v1v4headv3V2356534210S-25v30v29t16v40v1012/160/90/712/204/44/1412/120/413/13释放结点v4Relabel-To-Front算法v2v1v3v4head高度提升，前置v2v1v3v1v3v2v4366534210S-25v30v29t16v40v1012/160/90/712/204/44/1412/120/413/13释放结点v2Relabel-To-Front算法v1v2v2v1headv4V3376534210S-25v30v20t16v49v1012/160/90/712/204/413/1412/120/413/13释放结点v2Relabel-To-Front算法v1v2v2v1headv4V3高度提升，前置386534210S-25v30v20t16v49v1012/160/90/712/204/413/1412/120/413/13释放结点v4Relabel-To-Front算法v1v2v3v1headv2V4396534210S-25v37v22t16v40v1012/160/97/712/204/411/1412/120/413/13释放结点v4Relabel-To-Front算法v1v2v3v1headv4V2高度提升，前置406534210S-25v37v20t16v42v1012/160/97/712/204/413/1412/120/413/13释放结点v4Relabel-To-Front算法v1v2v3v1headv2V4高度提升，前置416534210S-25v37v22t16v40v1012/160/97/712/204/411/1412/120/413/13释放结点v4Relabel-To-Front算法v1v2v3v1headv4V2高度提升，前置426534210S-23v37v20t16v40v1012/160/97/712/204/411/1412/120/411/13释放结点v2Relabel-To-Front算法v1v2v3v1headv2V4高度提升，前置436534210S-23v37v20t16v40v1012/160/97/712/204/411/1412/120/411/13释放结点v3Relabel-To-Front算法v1v2v3v1headv2V4446534210S-23v30v20t23v40v1012/160/97/719/204/411/1412/120/411/13释放结点v3Relabel-To-Front算法v1v2v3v1headv2V4456534210S-23v30v20t23v40v1012/160/97/719/204/411/1412/120/411/13释放结点v3Relabel-To-Front算法最大流23v1v2v3v1headv2V4O(V3)时间复杂度比较算法算法时间复杂度时间复杂度Ford-FulkersonO(E|f*|)Edmonds-KarpO(VE2)Push-RelabelO(V2E)Relabel-to-FrontO(V3)在稠密图中有优势46谢 谢47
展开阅读全文