Here we are continuing the story of Ford-Fulkerson algorithm. Assume that , i.e. the capacities are all integers. Then starting the Ford-Fulkerson from the zero flow, we see that at each iteration . Thus the optimal flow will have integer values for each arc (such flows are called *integral*). We have

Corollary 3A maxflow problem with integer capacities has an integral optimal solution.

This has various graph-theoretic applications. We can convert an undirected graph into a digraph by replacing each edge by a pair of opposite arcs and , set all arc capacities to 1, and see what this implies for a pair of non-adjacent vertices . Running Ford-Fulkerson algorithm, we obtain an integral maximum flow , of value .

We also know that there is, by the maxflow-mincut Theorem, an cut s.t. . Instead of capacity, it is more appropriate to talk here about the *size* of the cut, i.e. the number of edges crossing from one part of the cut to another. Obviously, by definition of the capacity, we have .

The flow can be viewed as a collection of edge-disjoint -paths from to , as can be seen by induction on : indeed, if then by construction (via the Ford-Fulkerson algorithm) is a path. Suppose now this statement holds for all . As induces a connected subgraph, it contains a shortest path . Then, is cut by a minimum cut —otherwise the cut does not cut! Removing all the edges of from , we thus obtain a graph that has the cut of size , for . The flow in corresponding to has value , and is an augmenting path for this flow, with . Thus , i.e. cuts just 1 edge in , and by induction contains edge-disjoint -paths, and we obtain

Corollary 4(Menger Theorem (for edge-disjoint paths)) The minimum size of an cut in equals the maximal number of edge-disjoint paths in .

There is a graph transformation that allows one to prove Menger Theorem for internally disjoint paths (two paths between and are called internally disjoint is their only common vertices are and ). Our goal is to prove the following.

Theorem 5(Menger Theorem (for internally disjoint paths)) The minimum size of an cut in equals the maximal number of internally disjoint paths in .

*Proof:* Assume and are not adjacent. Replace each by a pair of vertices , , joined by an arc . Then replace each edge of by a pair of opposite arcs and . Replace every arc such that by the arc , each arc with or by , and each arc with or by . Now each path corresponds to the path in the new graph, and the opposite holds, too: each path in the new graph has this form.

Assign capacities 1 to the arcs , and infinite capacities (it suffices to take this “infinity” to be bigger than, say, ) to the rest of the arcs. Due to the choice of capacities, a minimum cut will satisfy , and thus the only arcs from to will be of type . Say, there will be such arcs. By (a straightforward generalisation of) Menger Theorem for edge-disjoint paths (to directed graphs), there will be exactly arc-disjoint paths in this digraph. By its construction, they cannot share a vertex (resp. ), as there is only one outgoing (resp. incoming) arc on it. Thus these paths are internally disjoint, and the corresponding paths in are internally disjoint, too.

One more classical application is a maxflow-based algorithm to construct a maximum matching in a bipartite graph , with the bipartition . We add two more vertices and to it, and connect to each by an edge. In the resulting new graph we solve the maxflow problem with all capacities set to 1. More precisely, we orient each edge so that each , , becomes an arc , respectively, , respectively .

Ford-Fulkerson algorithm, when started from the zero flow, will produce an integral maximal flow, of value . As we know from Menger’s theorem, we will have internally disjoint -paths. They will induce a matching on (just look at the edges only). On the other hand, any matching on can be used to construct an -flow of value in with all capacities 1. Hence is a maximum matching in .

Tags: graph theory, MAS324

## Leave a Reply