1. Definitions:
-- Input : An edge-weighted digraph (edge capacity) , source vertex s, and target vertex t.
-- st-cut : A partition of the vertices into two disjoint sets, with s in one set A and t in the other set B.
-- capacity of the cut (A, B) : The sum of the capacities of the edges from A to B.
-- Minimum st-cut (mincut) problem: Find a cut of minimum capacity.
2. Maxflow problem :
-- Input: An edge-weighted (capacity) digraph , source vertex s, and target vertex t.
-- An st-flow (flow) is an assignment of values to the edges such that:
- Capacity constraint: 0 ≤ edge's flow ≤ edge's capacity.
- Local equilibrium: inflow = outflow at every vertex (except s and t).
-- The value of a flow is the inflow at t.( we assume no edge points to s or from t. )
-- Maximum st-flow (maxflow) problem: Find a flow of maximum value.
3. Remarkable fact: Mincut problem and Maxflow problem are dual!
4. Ford-Fulkerson algorithm
-- Initialization: Start with 0 flow.
-- Find an augmenting path : undirected path from s to t such that:
-- Can increase flow on forward edges (not full).
-- Can decrease flow on backward edge (not empty).
-- Increase flow along augmenting paths
-- Termination: No augmenting path : All paths from s to t are blocked by either a
-- Full forward edge.
-- Empty backward edge.
5. Relationship between flows and cuts:
-- The net flow across a cut (A, B) is the sum of the flows on its edges from A to B minus the sum of the flows on its edges from from B to A.
-- Flow-value lemma. Let f be any flow and let (A, B) be any cut. Then, the net flow across (A, B) equals the value of f.
-- Pf. By induction on the size of B.
- Base case: B = { t }.
- Induction step: remains true by local equilibrium when moving any vertex from A to B.
-- Weak duality: Let f be any flow and let (A, B) be any cut. Then, the value of the flow ≤ the capacity of the cut.
-- Pf. Value of flow f = net flow across cut (A, B) ≤ capacity of cut (A, B).
6. Maxflow-mincut theorem
-- Augmenting path theorem: A flow f is a maxflow iff no augmenting paths.
-- Maxflow-mincut theorem. Value of the maxflow = capacity of mincut.
-- Pf. The following three conditions are equivalent for any flow f :
i. There exists a cut whose capacity equals the value of the flow f.
ii. f is a maxflow.
iii. There is no augmenting path with respect to f.
-- [ i ⇒ ii ]
- Suppose that (A, B) is a cut with capacity equal to the value of f.
- Then, the value of any flow f ' ≤ capacity of (A, B) = value of f.
- Thus, f is a maxflow.
-- [ ii ⇒ iii ] We prove contrapositive: ~iii ⇒ ~ii.
- Suppose that there is an augmenting path with respect to f.
- Can improve flow f by sending flow along this path.
- Thus, f is not a maxflow.
-- [ iii ⇒ i ]
- Suppose that there is no augmenting path with respect to f.
- Let (A, B) be a cut where A is the set of vertices connected to s by an undirected path with no full forward or empty backward edges.
- By definition, s is in A; since no augmenting path, t is in B.
- Capacity of cut = net flow across cut = value of flow f.
7. Computing a mincut from a maxflow:
-- By augmenting path theorem, no augmenting paths with respect to f.
-- Compute A = set of vertices connected to s by an undirected path with no full forward or empty backward edges.
8. Does FF always terminate?
yes, provided edge capacities are integers (or augmenting paths are chosen carefully)
9. Ford-Fulkerson algorithm with integer capacities :
-- Important special case: Edge capacities are integers between 1 and U.
-- Invariant: The flow is integer-valued throughout Ford-Fulkerson.
-- Pf. [by induction]
- Bottleneck capacity is an integer.
- Flow on an edge increases/decreases by bottleneck capacity.
-- Proposition. Number of augmentations ≤ the value of the maxflow.
-- Pf. Each augmentation increases the value by at least 1.
-- Integrality theorem. There exists an integer-valued maxflow.
-- Pf. Ford-Fulkerson terminates and maxflow that it finds is integer-valued.
-- Bad news : Even when edge capacities are integers, number of augmenting paths could be equal to the value of the maxflow.
-- Good news : This case is easily avoided. [use shortest/fattest path]
10. FF performance depends on choice of augmenting paths :
11. Implementation Considerations of FF:
-- Flow edge data type: Associate flow fe and capacity ce with edge e = v→w.
-- Flow network data type: Need to process edge e = v→w in either direction: Include e in both v and w's adjacency lists.
-- Residual capacity:
- Forward edge: residual capacity = ce - fe.
- Backward edge: residual capacity = fe.
-- Augment flow.
- Forward edge: add Δ.
- Backward edge: subtract Δ.
-- Residual network : Augmenting path in original network is equivalent to directed path in residual network.
12. Flow edge: Java implementation:
public class FlowEdge { private final int v, w; // from v to w private final double capacity; // capacity private double flow; // flow public FlowEdge(int v, int w, double capacity) { this.v = v; this.w = w; this.capacity = capacity; } public int from() { return v; } public int to() { return w; } public double capacity() { return capacity; } public double flow() { return flow; } public int other(int vertex) { if (vertex == v) return w; else if (vertex == w) return v; else throw new RuntimeException("Illegal endpoint"); } public double residualCapacityTo(int vertex) { if (vertex == v) return flow; // from w to v , backward edge else if (vertex == w) return capacity - flow; // from v to w, forward edge else throw new IllegalArgumentException(); } public void addResidualFlowTo(int vertex, double delta) { if (vertex == v) flow -= delta; //backward edge else if (vertex == w) flow += delta; //forward edge else throw new IllegalArgumentException(); } }
13. Flow network: Java implementation :
public class FlowNetwork { private final int V; private Bag<FlowEdge>[] adj; public FlowNetwork(int V) { this.V = V; adj = (Bag<FlowEdge>[]) new Bag[V]; for (int v = 0; v < V; v++) adj[v] = new Bag<FlowEdge>(); } public void addEdge(FlowEdge e) { int v = e.from(); int w = e.to(); adj[v].add(e); adj[w].add(e); } public Iterable<FlowEdge> adj(int v) { return adj[v]; } }
14. Ford-Fulkerson: Java implementation :
public class FordFulkerson { private boolean[] marked; // true if s->v path in residual network private FlowEdge[] edgeTo; // last edge on s->v path private double value; // value of flow public FordFulkerson(FlowNetwork G, int s, int t) { value = 0.0; while (hasAugmentingPath(G, s, t)) { double bottle = Double.POSITIVE_INFINITY; for (int v = t; v != s; v = edgeTo[v].other(v)) bottle = Math.min(bottle, edgeTo[v].residualCapacityTo(v)); for (int v = t; v != s; v = edgeTo[v].other(v)) edgeTo[v].addResidualFlowTo(v, bottle); value += bottle; } } public double value() { return value; } public boolean inCut(int v) { return marked[v]; } private boolean hasAugmentingPath(FlowNetwork G, int s, int t) { edgeTo = new FlowEdge[G.V()]; marked = new boolean[G.V()]; Queue<Integer> queue = new Queue<Integer>(); queue.enqueue(s); marked[s] = true; while (!queue.isEmpty()) { int v = queue.dequeue(); for (FlowEdge e : G.adj(v)) { int w = e.other(v); if (e.residualCapacityTo(w) > 0 && !marked[w]) { edgeTo[w] = e; marked[w] = true; queue.enqueue(w); } } } return marked[t]; } }
15. Maxflow application on bipartite matching :
-- Problem definition: (Given a bipartite graph, find a perfect matching.)
- N students apply for N jobs.
- Is there a way to match all students to jobs?
-- Network flow formulation of bipartite matching :
- Create s, t, one vertex for each student, and one vertex for each job.
- Add edge from s to each student (capacity 1).
- Add edge from each job to t (capacity 1).
- Add edge from student to each job offered (infinite capacity).
-- When no perfect matching, mincut explains why :
Consider mincut (A, B).
- Let S = students on s side of cut.
- Let T = companies on s side of cut.
- Fact: | S | > | T |; students in S can be matched only to companies in T.
16. Maxflow application on Baseball elimination problem :
-- Problem definition: Which teams have a chance of finishing the season with the most wins?
-- Observation. Answer depends not only on how many games already won and left to play, but on whom they're against.
-- maxflow formulation : Remaining games flow from s to t.
-- Team 4 not eliminated iff all edges pointing from s are full in maxflow.
相关推荐
Network Algorithms Maximum Flow:网络最大流算法.ppt
用增广路法计算最大流问题,给出了C++代码
无界平行分批机器上的最小化最大流程的在线排序,李文华,原晋江,This paper considers online scheduling on m unbounded parallel-batch machines to minimize maximum flow-time of the jobs. The research ...
As a fundamental problem, the maximum flow problem is of vital importance for routing and service scheduling in networks. However, there exists no permanent end-to-end path since the topology and the...
minimum cut/maximum flow algorithms on graphs emerged as an increasingly useful tool for exact or approximate energy minimization in low-level vision. The combinatorial optimization literature ...
在优化理论中,最大流最小割定理指:在一个网络流中,能够从源点到达汇点的最大流量,等于,如果从网络中移除就能够导致网络流中断的边的集合的最小容量和。
最大流程序,在这个函数的编制中存在一个细节,当任取一个已标号未检查的点的时候,我取的最靠前的点。如果加进随机选取的语句,每次运行程序可能会出现不同的最大流结果。
Max Flow, Min Cut_有关图像切割 Minimum cut Maximum flow Max-flow min-cut theorem Ford-Fulkerson augmenting path algorithm Edmonds-Karp heuristics Bipartite matching
求下列网络的最小费用最大流,其中括号......
Chapter 26 - Maximum Flow Part VII - Selected Topics Chapter 27 - Sorting Networks Chapter 28 - Matrix Operations Chapter 29 - Linear Programming Chapter 30 - Polynomials and the FFT ...
Chapter 26 - Maximum Flow Part VII - Selected Topics Chapter 27 - Sorting Networks Chapter 28 - Matrix Operations Chapter 29 - Linear Programming Chapter 30 - Polynomials and the FFT ...
Chapter 26 - Maximum Flow Part VII - Selected Topics Chapter 27 - Sorting Networks Chapter 28 - Matrix Operations Chapter 29 - Linear Programming Chapter 30 - Polynomials and the FFT ...
Chapter 26 - Maximum Flow Part VII - Selected Topics Chapter 27 - Sorting Networks Chapter 28 - Matrix Operations Chapter 29 - Linear Programming Chapter 30 - Polynomials and the FFT ...
CHAPTER 4 - Maximum Flow Problem CHAPTER 5 - Minimum Cost Flow Problem CHAPTER 6 - Multicommodity Flows SECTION III - Algebraic Graph Theory CHAPTER 7 - Graphs and Vector Spaces CHAPTER 8 - Incidence...
Chapter 26 - Maximum Flow Part VII - Selected Topics Chapter 27 - Sorting Networks Chapter 28 - Matrix Operations Chapter 29 - Linear Programming Chapter 30 - Polynomials and the FFT ...
最大流 Maximum flow 1.6.3.1.1. 基本算法 Basic algorithms 1.6.3.1.1.1. Ford-Fulkerson method 1.6.3.1.1.1.1. Edmonds-Karp algorithm 1.6.3.1.1.1.1.1. Minimum length path 1.6.3.1.1.1.1.2. Maximum ...
1.6.3.1. 最大流 Maximum flow 1.6.3.1.1. 基本算法 Basic algorithms 1.6.3.1.1.1. Ford-Fulkerson method 1.6.3.1.1.1.1. Edmonds-Karp algorithm 1.6.3.1.1.1.1.1. Minimum length path 1.6.3.1.1.1.1.2. Maximum...
目前最全的算法导论第三版的答案 清晰度极好 另每章都有章节重点总结 在第二版基础上...Chapter 26: Maximum Flow Lecture Notes 26-1 Solutions 26-12 Chapter 27: Multithreaded Algorithms Solutions 27-1 Index I-1