6   Network Flow Problems
Yet another area of rich applications of graphs (actually digraphs) deals with so called networks and "commodity flows" in them.
This time, the main optimization task is to maximize a flow from the designated source to the designated sink, respecting given constrains - capacities of network arcs.
4
Brief outline of this lecture
• Networks (weighted directed graphs) and flows in them.
• A network-flow algorithm(s) based on augmenting paths.
• Applications in connectivity, matching, and SDR problems.
Petr Hliněný,  FI MU Brno_1_
FI: MA010: Network Flows
5
5
6.1   Defining a flow network
The underlying structure of a flow network is a directed graph, with its vertices representing network nodes, and arcs representing the (existing or possible) connections between nodes. c
Definition 6.1. A How network is a quadruple S = (G,z, s, w) such that
- G is a digraph,
- the vertices z G V(G), s G V(G) are the source and the sink, respectively,
- and w : E(G) — R+ is a positive weighting of the arcs (edges) of G, these weights are called edge capacities.
Remark: In reality, more than one source or sink may exist in a flow network, but that is not a problem — we simply create a single artificial source and draw arcs from it to all the real sources (even with source capacities!).
Petr Hliněný,  Fl MU Brno
Fl: MAOIO: Network Flows
5
5
Notation: For simplicity, we shall write e — v to mean that an arc e "comes to" (has its head in) the vertex v, and e — v analogously for e "leaving" (having tail in) v. c
Definition 6.2. A network flow, in a flow network S = (G, z, s,w),
is an assignment f : E(G) — R+ satisfying (we say f is admissible)
- Ve G E(G) : 0 < f (e) < w(e),
- Vv G V(G),v = z,s :   E f (e)= E f (e).
e—>v —v
The size (value) of a flow f is the quantity ||f || = E f (e) — E f (e). D
e——z e—>z
Notation: The flow value F and the capacity C of an arc in a picture of a network will be shortly denoted by F/C, respectively.
So what is the value of the depicted flow? 5
2/4
2/5
3/3
3/5
Remark: Notice the following simple identity
0 = E (/(«) - f («)) = E (E f («) - E f       = E (E f (e) - E f ■
e£E vGV \e——v e—>v /        v = z,s \e——v e—>v /
What interesting does it tell us? Briefly, that the (negative) flow value can be analogously defined at the sink s.
if II = (^E
Petr Hlineny,  FI MU Brno
E f (e) - E f («)) = (E f (e) - E f (e))
e——z e—>z / \e—>s e——s /
FI: MA010: Network Flows
6.2   Finding the maximum flow value
There exist quite simple and fast algorithms to determine the maximum flow value in a given network.
Problem 6.3. The Max-Flow problem
Given a flow network S = (G, z, s, w), the task is to find a flow f in S from z to s such that the value ||f || is maximized (among all admissible flows in S). c
2/5
The main question is; how can we certify that no better flow exists in S1
Fortunately, a nice and simply understandable criterion exists there — notice that there is an "arc cut" between z and s of total value 6, and hence obviously there cannot be a larger flow!
Petr Hlineny,  FI MU Brno_6_FI: MA010: Network Flows
Definition 6.4. A cut in a flow network S = (G, z, s,w)
is a subset of edges (arcs) C C E(G) such that there is no z — s directed path in G
completely avoiding C (i.e. a directed z — s path existing in G — C).
The size of a cut C is the sum of the capacities of arcs in C, i.e. ||C|| =    eec w(e)x
Theorem 6.5. The maximum (admissible) flow value in a network S equals the minimum cut size in S.
See the following example with a cut of size 5 (in the middle), and so the flow value 5 is maximum.
1
4
Remark: Theorem 6.5 is an example of a so called good characterization of a property—not having a larger flow can be certified by showing an obvious constrain, a cut of the corresponding size.
Petr Hliněný,  Fl MU Brno
Fl: MAOIO: Network Flows
Residual and augmenting paths
Definition: Consider a flow network S and a flow f in it. A residual z-s path (in S w.r.t. f) is an undirected path in G from the source z to the sink s, i.e. a sequence of adjacent edges ei, e2,..., em, such that f (ej) < w(ej) if ej is directed from z, and f (ej) > 0 if ej is directed from s. □
The quantity w(ej) — f (ej), or f (ej), respectively, is called the residual capacity of the edge ej. □
A residual path is that of strictly positive residual capacities. . .
3/4        1/2        1/1 2/3
residual capacities:
2/4
+1 +1
+1
+2 +2
Petr Hliněný,  FI MU Brno
FI: MA010: Network Flows
4
Algorithm 6.6. Ford-Fulkerson's for network Hows.
input <   flow network S = (G, z, s, w); flow f = 0; repeat {
Search (BFS) the graph G to find the set U of those vertices
accessible from the source z along residual paths; if ( s G U ) {
P = any residual z-s path in S (this P then called an augmenting path); Augment ("enlarge") f by the minimal residual capacity along P;
}
until ( s G U );
output >   a maximum flow f in S;
output >   a minimum cut in S from U to V(G) — U.
Petr Hliněný,  FI MU Brno
FI: MA010: Network Flows
1
Proof of Algorithm 6.6:
For any flow f and any cut C in S, it holds ||/1| < ||C||. If the algorithm stops with a flow f in S and a cut C such that ||C|| = ||f ||, then it is clear that f is a maximum flow in S. (We have, however, not proved yet that the algorithm stops!) c
So to prove that whenever the algorithm stops with f, C, then ||f || = ||C||, we use the following schematic picture (in which s does not belong to the "accessible" set U):
f (e) = w(e)
©
U
f (e)
0
Since no further vertex than U is accessible along residual paths, every arc e leaving U has full flow f (e) = w(e), and every arc e entering U has zero flow f (e) = 0. Therefore;
£ f (e) - £ f (e) = £ f (e) = £ w(e) = ||C|| .
e^U e^U e^U eGC
That is nice, and it remains to argue that ||C|| = e^u f (e) e^U f (e) = ||f ||, finishing the proof. □
Petr Hlineny,  FI MU Brn<
FI:MA010: Network Flows
The proof of Algorithm 6.6 shows several interesting things:
Fact: If we can prove that Algorithm 6.6 stops, we prove also Theorem 6.5.c
Fact: If the edge capacities in S are integral, then Algorithm 6.6 always stops.
Corollary 6.7. If the edge capacities in S are integral, then Algorithm 6.6 outputs an integral flow. c
Improved flow algorithms
Generally, one cannot guarantee that Algorithm 6.6 stops, since counterexamples exist with real capacities, but we can do better as follows. c
Algorithm 6.8. Edmonds-Karp's for network flows.
As in Algorithm 6.6, we always enlarge one of the shortest residual paths in G (i.e. find the path P using BFS, cf. Corollary 3.4).
This implementation is guaranteed to stop after O(\V(G)| • \E(G)\) iterations, so in total computing time O(\V(G) \ • \E(G)\2).
Petr Hlineny,  FI MU Brno_11_FI:MA010: Network Flows
Even better, we can use the following "clever" algorithms.
Algorithm 6.9. Dinitz's for network flows (a sketch). We modify Algorithm 6.6 with the following iteration:
• Using BFS, we find all the shortest residual paths in S, creating a "layered" residual network.
• The layered network is then completely saturated in one run.
This implementation makes only O(\V(G)|) iterations of the main cycle. Total computing time now is O(\V(G)\2 • \E(G)\). □
Algorithm 6.10. MPM "Three Indians" (a sketch).
Same as Algorithm 6.9, except that a layered network is saturated faster, and the total computing time is O(\V(G)\3).
Petr Hiineny,  FI MU Brno_12_FI:MA010: Network Flows
6.3   Generalized network How settings
Among the many ways flow networks can be generalized, we briefly mention three which are interesting and often used.
Networks with vertex capacities
In a flow network with vertex capacities (of course, retaining edge capacities as well), the weight function is w : E(G) U V(G) — R+.
The meaning for admissible flows is that the total sum of incoming flow to any vertex x is not more than w(x). (Differently applicable to the source or the sink, though...)
Fact. Such a generalized flow network can easily be translated to an ordinary network via "doubling" the capacitated vertices (replacing them with new arcs between the two copies), as follows.
i----1
Networks with lower capacities
In a flow network with lower capacities, in addition to the weight function w, there is another weight function I : E(G) — R+ giving the lower edge capacities.
A flow f is admissible in such a network if 1(e) < f (e) < w(e) for every edge e of the network. nNotice that an admissible flow may not exist in such a lower-capacitated network. c
Algorithm 6.11. Flows in lower-capacitated network
For this kind of a flow network, the solution has two steps.
- First, an admissible circulation is found (with a "back-arc" sz), respecting both the lower an upper bounds I, w. This is done by finding a maximum flow in an artificial network modelling the "surplus" of lower capacities at every vertex...
- Second, this admissible circulation is enlarged by a maximum possible excessive flow from z to s (the capacities are now w(e) — r(e) where r is the circulation found above). c
Multicommodity flows
This is a difficult problem setting reaching beyond the scope of our lecture.
V
Petr Hlineny,  FI MU Brr
FI: MA010: Network Flows
6.4   Other applications of network flows Bipartite matching
Definition: A matching in a graph G (bipartite here) is a subset of edges M C E(G) such that no two edges from M share a vertex. c
Algorithm 6.12. Finding maximum matching in a bipartite graph
Given a bipartite graph G with the vertex parts A, B, we construct the following flow network S:
AB
All the edges are implicitly directed from the source towards the sink, and all capacities are 1. We run Algorithm 6.6, and form the resulting matching M by those edges of G having nonzero flow at the end. c
Proof of Algorithm 6.12: By Corollary 6.7, the maximum flow found by our algorithm is integral, which now means that each flow unit is 0 or 1. Hence no two edges of M could share a vertex. Conversely, any matching M' gives an admissible flow in S. □
Petr Hliněný,  FI MU Brno_15_FI:MA010: Network Flows
Higher graph connectivity
Let us consider a graph G as a generalized (symmetrically-oriented) network with all vertex capacities equal to 1. Then the network flow theorem immediately says:
Corollary 6.13. Let u, v be two vertices of G and k > 0 be an integer. Then there exists at least k internally disjoint u-v paths in G if, and only if, removing any subset of at most k — 1 vertices of G (other than u,v) does not disconnect u from v. c
This statement immediately implies Theorem 2.6 (Menger's)!
V
Petr Hlineny,  Fl MU Brr
Fl:MAO1O: Network Flows
Systems of distinct representatives (SDR)
Definition: Let Mi, M2,..., Mk be a collection of nonempty sets. A system of distinct representatives (SDR) of the set family [M\,M2,... ,Mk} is a sequence of pairwise distinct elements (x\, x2,..., xk) such that xi G Mi for i = 1, 2,... ,k. c
Theorem 6.14. (Hall) Let {M\,M2l..., Mk} be a family of nonempty sets. Then there exists a system of its distinct representatives if, and only if,
i.e., the union of any subfamily of these sets has at least that many elements as the number of sets in it.
Necessity of Hall's condition in this theorem is obvious, and its sufficiency can be proved by an application of network flows again.
VJ c{1,2,...,k} : |U     Mj I >\J \,
V
Petr Hlineny,  FI MU Brr
FI: MA010: Network Flows