6.4 Maximum Flow
This section under major construction.
Maximum flow and minimum s-t cut.
Program FordFulkerson.java computes the maximum flow and minimum s-t cut in an edge-weighted digraph in E^2 V time using the Edmonds-Karp shortest augment path heuristic (though, in practice, it usually runs substantially faster). It uses FlowNetwork.java and FlowEdge.java.Percolation.
Max flow in 2D (always choose leftmost path) and 3D.Applications to computer graphics.
Yuri Boykov has papers on maxflow applications to segmentation in computer vision. maxflow data.Bipartite matching.
Exercises
- Cycle containing two vertices.
Given an undirected graph G and two distinguished vertices s and t,
find a cycle (not necessarily simple)
containing s and t, or report that no such cycle exists.
Your algorithm should run in linear time.
Answer. The answer is yes if and only if the maximum flow from s to t is at least 2. So, run two iterations of Ford-Fulkerson in the digraph with each edge replace by two antiparallel edges and unit capacity.
- k-connected. Given an undirected graph, determine whether two vertices s and t are k-connected (or equivalently whether there are k edge-disjoint paths).
- True or false. If true provide a short proof, if false
give a counterexample.
- In any max flow, there is no directed cycle on which every edge carries positive flow.
- There exists a max flow for which there is no directed cycle on which every edge carries positive flow.
- If all edge capacities are distinct, the max flow is unique.
- If all edge capacities are distinct, the min cut is unique.
- If all edge capacities are increased by an additive constant, the min cut remains unchanged.
- If all edge capacities are multiplied by a positive integer, the min cut remains unchanged.
- Simple cycle containing two vertices.
Given an undirected graph and two vertices s and t, find a simple cycle
containing both s and t (or report that no such cycle exists).
Hint: there is a directed cycle containing both s and t if and only if there are two (internally) vertex-disjoint paths between s and t.
- Vertex disjoint paths in an digraphs.
Given a digraph G and two vertices s and t, find the maximum number of
of vertex-disjoint paths from s and t.
Hint: Replace each vertex v (other than s and t) with two vertices v1 and v2; add an edge of capacity 1 from v1 to v2; redirect all edges pointing to v to point to v1; redirect all edges pointing from v to point from v2.
- Vertex disjoint paths in an undirected graph.
Given an undirected graph G and two vertices s and t, find the maximum number of
of vertex-disjoint paths between s and t.
Hint: Replace each undirected edge v-w by two directed edges v->w and w->v.
- Simple path containing three vertices.
Given an undirected graph and three vertices u, v, and w, find a simple path
containing both u, v, and w (or report that no such path exists).
Hint: there is a simple path between u and w that passes through v if and only if there are two (internally) vertex disjoint paths, one between v to u and one between v to w.
- Unique mincut.
Given an s-t flow network, determine whether the mincut is unique.
Hint: solve s-t mincut problem in G and in G^R.
- Unmatchable edges in a bipartite graph.
Given a bipartite graph G, an edge is unmatchable if it does not appear in
any perfect matching of G.
Hint: if G has no perfect matching, then all edges are unmatchable. Otherwise, find a perfect matching; orient all of the edges in the perfect matching in one direction and all of the remaining edges in the opposite direction; the unmatchable edges are all of the edges not in the perfect matching that have endpoints in different strongly-connected components of the resulting digraph.
- Mincut with fewest edges.
Given a flow network, among all mincuts, find one that has the fewest number of edges.
Hint: create a new flow network G' that is equal to G, except that w'(e) = w(e) * n + 1.