# 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.