最大流问题最小割集,帮我解释下网络流 _生活百科

网络流中的最小割和无向图的最小割有哪些差别啊?

文章插图
网络流是有向图，有向图中对于s,t两点有s-t最小割，有向图最小割等于网络流最大流。
不知道你说的无向图最小割是什么概念，有s,t点对应的s-t最小割，按有向图做，
有全局最小割，就是将全图按边割为两部分取边权和最小的方案，按SW算法做，
有割点，就是删去此点后图不连通，按tarjan算法做，
有连通度，就是至少删除多少点图才不连通，按网络流做。
这些术语现在用的不严谨啊，所以没啥定论，一般都要加以解释。
帮我解释下网络流

文章插图
必须知识：最短路径问题
1.Dijkstra
适用于满足所有权系数大于等于0（lij≥0）的网络最短路问题，能求出起点v1到所有其他点vj的最短距离；
朴素的Dijkstra算法复杂度为O(N^2)，堆实现的Dijkstra复杂度为O(NlogN).
2.bellman-ford
适用于有负权系数，但无负回路的有向或无向网络的最短路问题，能求出起点v1到所有其它点 vj的最短距离。bellman-ford算法复杂度为O(V*E) 。
3.Floyed
适用于有负权系数，可以求出图上任意两点之间的最短路径。DP思想的算法，时间复杂度为O(N^3);
for ( k= 1; k<= n; k++)
for ( i= 1; i<= n; i++)
if (graph[i][k]!=INF)
for ( j= 1; j<= n; j++)
if (graph[k][j]!=INF && graph[i][k]+graph[k][j]< graph[i][j])
graph[i][j]= graph[i][k]+ graph[k][j];
NO.1s-t最大流
两大类算法
1.增广路算法
Ford-Fulkerson算法: 残留网络中寻找增加路径
STEP0：置初始可行流。
STEP1：构造原网络的残量网络，在残量网络中找s－t有向路。如果没有，算法得到最大流结束。否则继续下一步。
STEP2：依据残量网络中的s－t有向路写出对应到原网络中的s－t增广路。对于增广路中的前向弧，置s(e)＝u(e)- f(e) 。对于反向弧，置s(e)＝f（e）STEP3：计算crement=min{s（e1），s（e2），…，s（ek）}
STEP4：对于增广路中的前向弧，令f(e)＝f(e)＋crement；对于其中的反向弧，令f(e)＝f(e)-crement，转STEP1 。
关键点:寻找可增广路。决定了算法复杂度。
实现：Edmonds-Karp通过采用了广度优先的搜索策略得以使其复杂度达到O(V*E^2) 。
优化—> Dinic算法(*)
Dinic算法的思想是为了减少增广次数，建立一个辅助网络L，L与原网络G具有相同的节点数，但边上的容量有所不同，在L上进行增广，将增广后的流值回写到原网络上，再建立当前网络的辅助网络，如此反复，达到最大流。分层的目的是降低寻找增广路的代价。
算法的时间复杂度为O(V^2*E) 。其中m为弧的数目，是多项式算法。邻接表表示图，空间复杂度为O(V+E) 。
2.预流推进算法
一般性的push-relabel算法: 时间复杂度达到O(V^2*E) 。(*)
relabel-to-front算法->改进
最高标号预流推进:时间复杂度O(V^2*sqrt(E))
NO2. 最小费用最大流
求解最小费用流的步骤和求最大流的步骤几乎完全一致，只是在步骤1时选一条非饱和路时，应选代价和最小的路，即最短路。
步骤1. 选定一条总的单位费用最小的路，即要给定最小费用的初始可行流，而不是包含边数最小的路。
步骤2. 不断重复求最大流的步骤来进行，直到没有饱和路存在为止。然后计算每个路的总费用。
和Edmonds-Karp标号算法几乎一样，因为这两种算法都使用宽度优先搜索来来寻找增广路径，所以复杂度也相同，都是O(V*E^2) 。