4   Graph Cuts and Network Flows
Yet another area of rich applications of graphs (digraphs) deals with so called flow networks and "commodity flows" in them.
Brief outline of this lecture
• More on graph connectivity - vertex and edge cuts in graphs.
• Flow networks, admissible flows and network cuts, circulations.
• Finding a maximum flow via augmenting of residual paths.
• Extensions, and applications in connectivity, SDR and vision.
□
4.1   Connectivity and Cuts
Recall from Lecture 2:
• A graph G is edge-k-connected, k > 1, if G stays connected even after removal of any subset of < k — 1 edges. □
• A graph G is (vertex-) k-connected, k > 1, if G stays connected even after removal of any subset of < k — 1 vertices.
Specially, the complete graph Kn is vertex-(n— l)-connected by the definition.□
• Menger's theorem:    A graph G is ^-connected iff there exist > k internally disjoint paths between any pair of vertices (the paths may share only their ends).
Small so-called cuts are the obstacles to high connectivity in graphs.
Petr Hliněný,   Fl MU Brno, 2014
Fl: MAOIO: Cutsand Network Flows
^Edge / vertex cuts
An s-t path in a graph G is a path in G with the ends s,t G V(G).
Definition: Let G be a graph and s, t e V(G). An edge set F C £'(G) is an s-t edge cut in G if the subgraph G — F (deleting of the edges F from G) has no s-t path.n
In other words, if s and t belong to different conn, components of the subgraph G — F.
□
Similarly, a vertex set X C T/(G) is a s-t vertex cut in G if the subgraph G — X (deleting of the vertices X from G) has no s-t path. □
An s-t cut is called minimal if no proper subset of it is an s-t cut again.
If s-t are implic. known, or irrelevant, then we shortly say an edge/ vertex cut in G.
vcrt£%Jedge cut = kranomj /urefwitymj hz minimal cut = minimalnifaz
Petr Hlinený,   Fl ML) Brno,  2014 3/28 Fl: MA010: Cuts and Network Flows
Small cuts and blocks
Definition: A bridge in a graph is a minimal edge cut consisting of one edge. A cutvertex in a graph is a minimal vertex cut consisting of one vertex.
Fact: A connected graph G is not 2-connected iff G has a cutvertex or G ~ K\, K^.o
A graph G on |V(G)| > k vertices is not ^-connected iff G has a vertex cut of size k — 1 or less. (Note that a disconnected graph has a cut of size 0.) □
Definition: A block in a graph G is a maximal (by inclusion) 2-connected subgraph of G. Moreover, a vertex with no edges and an edge not contained in any larger block of G are also called blocks of G. □
Proposition 4.1. A subgraph H C G is a block if, and only if, H is maximal (among subgraphs of G) with the property that H contains no cutvertex (of H itself).
bridge = most, cutvertex artikiiCace, disconnected.graph = nesoumshjgraf
Petr Hlinený,   Fl ML) Brno,  2014 4/28 Fl: MA010: Cuts and Network Flows
An excersise: the structure of graph blocks
Proposition 4.2. Let G be a graph and B1, ...,Bk be the blocks of G. IfB^Bj ^ 0, then Bi n Bj — {c} where c is a cutvertex of G. □
Proof by means of contradiction: Let Bi n Bj D {c,d} where c ^ d. Since Bj is connected by the definition, there exists a path P C Bj with the ends c, d. □
Let B+ :— Bi U P C G. Since is 2-connected, so is B+ (Thm. 2.13, "adding an ear P"). However, this contradicts the definition of a block; Bi already was a maximal 2-connected subgraph of G. □
The same argument proves the last part, that c G Bi P\Bj is a cutvertex, too. Assume not, then for some neighbours u,v of c such that u e V(Bi) and v e V(Bj), there exists a w-f path Q C G and B+ := Bj U (Q + fc) contradicts maximality of Bj. □ C
Corollary 4.3. T/?e bipartite "incidence graph" between the blocks and the cutvertices of a graph G is a forest (it contains no cycles).
... 6y contradiction = d&kaz sporem
Petr Hlinený,   Fl MU Brno,  2014 5/28 Fl: MA010: Cuts and Network Flows
Menger's theorem reformulated
Recall...
• Menger's theorem:    A graph G is ^-connected iff there exist > k internally disjoint paths between any pair of vertices (the paths may share only their ends).
Theorem 4.4. Let G be a graph and s,t G V(G). There exist k internally disjoint s-t paths in G if, and only if, there is no s-t vertex cut in G of size less than k. □
A sketch: the "only if" direction is obvious, and for the "if" direction, □ we will generalize the whole setting to "weighted connectivity" next...
Petr Hliněný,   Fl MU Brno, 2014
Fl: MAOIO: Cutsand Network Flows
4.2   Digraphs as Flow Networks
Flow networks present a convenient "weighted generalization" of the concept of graph connectivity and cuts, with long history of research and many practical applications. □
Definition 4.5. A flow network is a quadruple G — (G,z,s,w) such that
- G is a digraph (it is important to have directed edges),
- the vertices z e V(G), s G V(G) are the source and the sink, respectively,
- and w : E(G) —>• R+ U {00} is a positive weighting of the arcs (edges) of G, these weights are called edge capacities.
Remark: In a real world, more than one source or sink may exist in a flow network, but that is not a problem—we simply create a single artificial "supersource" and draw arcs from it to all the real sources (even with source capacities), and the same with a "supersink".
fiozu nctzoork.= síť, source = zctroj, sink. = stoi^ capacity = kapacita
Petr Hlinený,   Fl MU Brno,  2014 7/28 Fl: MA010: Cuts and Network Flows
Notation: For simplicity, we shall write e —>• v to mean that an arc e "points to" (has its head in) the vertex v, and e ^— f analogously for e "leaving" (having tail in) v. □
Definition 4.6. A network flow, in a flow network G — (G,z,s,w),
is an assignment / : E(G) —>• hq~ satisfying (we say / is admissible)
- Ve G E(G) : 0 < /(e) < w(e), (capacity constraints)
- Vv e V(G),u ^ z,s :       f(e) —      f(e)-        (flow conservation) □
The i/a/ue (s/zej of a flow / is the quantity ||/|| — Y f(e) ~ Y f(e)- c
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.
tietzuorkjíozu = tok.v síti
actmissiúCe = přípustný, capacity constraints = kapacitní omezení, flozu conservation = zachování toliu
Petr Hlinený,   Fl MU Brno,  2014 8/28 Fl: MA010: Cuts and Network Flows
^Circulations
Definition: A flow in a flow network G — (G, z, s, w) satisfying the flow conservation constraint at all the vertices including the source and sink z,s is called a circulation.
The source and the sink hence become irrelevant for circulations. □
Fact: There is a one-to-one correspondence between a flow f in a flow network G and the following circulation in the enhanced network G + (s,z):
• simply add the "reverse" arc (s,z) assigned flow value ||/|| and capacity +00.
circulation = cirkjdacc (v sítí)
Petr Hlinený,   Fl MU Brno,  2014 9/28 Fl: MA010: Cuts and Network Flows
Boundary flow property
Notation: For G and U C V(G), let e —>• C/ mean that an arc e points from F(G) \ [/ towards U, and e <— U mean that an arc e points from [/ towards V(G) \ U.
Definition: Let G be a flow network and U C y(G). The boundary surplus of a flow / on [/ is
, <  f: e->E7
Surplus on J7 is 5 in the picture:
Fact: The boundary surplus of / on {z} is exactly the flow size ||/|| by the definition.
We aim to extend this finding to other suitable U's.
bounihirii surpCus = pfebytt'k iiti hruiiki
_
Lemma 4.7. Let G be a flow network and 0 ^ U C V(G). /f / /s a circulation in G, then the boundary surplus of f on U is always 0.
Proof: We use induction on \U\. For U — {x}, the claim is just the flow conservation constraint at x. □
Consider now arbitrary U C V(G) where \U\ > 2 and y E U. By the induction assumption, the claim holds for U' — U \ {y}. Now we compute
and similarly
E M :
£/(e)-      E /(e)
e-i—U' e*—U' A e—s-^
E/(ß)- E
e—*U' e—>U' A e«— ^
£/(e)-      E /(e)
e«— 1/ e«— y A e—>£/'
E/(ß)- E
e—e—!-y A e-ir-XJ'
Therefore, the new surplus is
E zw - E
E        - E
E   - E
o + o.
z
Petr Hliněný,   Fl MU Brno, 2014
Fl: MAOIO: Cuts and Network Flows
Where to measure flow size
Lemma 4.7. Let G be a flow network and 0 ^ U C V(G). If f is a circulation in G, then the boundary surplus of f on U is always 0.
Corollary 4.8. Let G — (G, z, s, w) be a flow network and f an admissible flow in G. For any U C V(G) such that z e U ^ s (U "separating" z from s), the boundary surplus of f on U is always the same, equal to ||/||. □
Proof: Turn / into a circulation /' in G+sz by letting /' = / on G and f'(sz) — ||/||, and apply Lemma 4.7.
Then, for any such U, it is sz —>• U and so f'(sz) is accounted for in the boundary surplus of /' on U, which is 0. The surplus of / on U hence equals f'(sz) — ||/||. C
2/4
2/5
3/3
4/5
Petr Hliněný,   Fl MU Brno, 2014
Fl: MAOIO: Cuts and Network Flows
4.3   The Max-flow Min-cut Theorem
Edge cuts in graphs have a natural weighted generalization into flow networks.
Definition 4.9. A cut in a flow network G — (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., s is not reachable from z in G — G). □
The capacity (size) of a cut G is the sum of the capacities of arcs in G, i.e.,
||c|| = 5>(eO-D
eeC
The most important result in this area is the following:
Theorem 4.10. (Ford—Fulkerson) In any flow network G, there exists an admissible flow of size r e R+ if, and only if, there is no cut in G of capacity less than r. □
Maximum possible flow size minimum cut capacity.
Petr Hliněný,   Fl MU Brno, 2014
Fl: MAOIO: Cuts and Network Flows
An example
What is a cut of the least capacity in this example? Is it unique?
||c||=5
We can see two cuts C and C' of the same size 5, and no smaller one.
Petr Hliněný,   Fl MU Brno, 2014
Fl: MAOIO: Cuts and Network Flows
On the flow-cut duality
Theorem 4.10 (repeated).   In any flow network G, there exists an admissible flow of size r e i?+ if, and only if, there is no cut in G of capacity less than r.
How to read this theorem? □
• If one looks for a certificate that a flow is maximum possible, then it always suffices to exhibit a cut of the same value. □
• Likewise, to certify minimality of a cut, one exhibits a flow of the same value. □
• Nice properties of this kind are commonly called good characterizations (of a problem)—one can certify optimality of a solution by giving an obvious obstacles
Such as, in our case, the following:
Proposition 4.11. In any G, for any adm. flow f and any cut C, it holds ||/| < ||c||.n
Proof: Let U be the set of vertices of G reachable from z in G — C, where s ^ U. Let Fjj = {e : e <- u}. Then Fv C c by the definition of u. By Corollary 4.8,
ii/ii = £pp /(e)-£ >) ^ epp ^)<iicii.
^-^eEFu *—^e^>U ^-^eEFu
c
good characterizations = doBrd cftaraki-crizacc, oBstacic = pre^az^a
Petr Hliněný,   Fl MU Brno,   2014 15/28 Fl: MA010: Cuts and Network Flows
4.4   Finding the Maximum Flow
A question: is the following flow maximum possible?
Now it is, of size 6, and we have got a cut of capacity 6 as well. □
Fact: There exist quite simple and fast algorithms to find the maximum flow (and the minimum cut at the same time) in a given flow network.
- These simple algorithms are based on an idea to saturate "residual z—s paths".
Petr Hliněný,   Fl MU Brno, 2014
Fl: MAOIO: Cuts and Network Flows
Problem formulation
Problem 4.12. The Max-Flow problem
Given a flow network G — (G, z,s,w), the task is to find a flow f in G from z to s such that the flow size ||/|| is maximized (among all admissible flows in G). c
Where can one find the max-flow problem?
• in transportation (or distribution) networks of goods, electricity, etc.
• in pipe networks (water, gas, oil, sewerage, etc.) □
• in IP packet routing (real-time transmission of large data), □
• in various "matching" or "representatives" problems, □
• in computer vision - as image segmentation (the min-cut).
Petr Hliněný,   Fl MU Brno, 2014
Fl: MAOIO: Cuts and Network Flows
Residual and Augmenting Paths
Definition: Consider a flow network G and an admissible flow / in it.
A residual z-x path (in G w.r.t. / and the source z) is an undirected path in G from the source z to any vertex x, i.e. a sequence of adjacent edges e±, e?, ■ ■ ■, em; □
- such that f(ei) < w(ei) if    is directed away from z,
- and f(ei) > 0 if    is directed towards z ("backwards").
^3/4   ^   1/2   ^   1/1   ^   2/3   ^ 2/4
residual capacities: vfv _|_\~    +1^   ^~*+2        +2^-^   > 0
The quantity w(ei) — /(e^), or /(e^), resp., is called the residual capacity of edge e^.n The background idea is as follows.
• A residual z—s path has strictly positive residual capacity e > 0, and so one can "push" an additional e amount of flow from the source z to the sink s. □
• However, what does "pushing flow against an arc" mean??? □
Actually, we stop a (bit of) "returning" flow, and send new amount of flow instead of it. (Imagine stoppig a crowd of returning people and thus making more room.)
residualpath = ncnasyccna (zßytkffüä) ccsta, residual capacity = zbytkova kapacita
Petr Hliněný,   Fl MU Brno, 2014
Method 4.13. Maximizing flow via residual paths.
The overall idea is really simple; □
one should repeatedly augment (meaning to enlarge) the current flow by adding to it along existing residual paths...
How to augment a residual path:
3/4        1/2        1/1        2/3 2/4
residual capacities: W _|_^ _|_2        +2 > 0
min. residual capacity r — 1 > 0    ~>    augmenting the current flow by +1:
4/4       2/2       0/1        1/3 3/4
Fact: Augmenting (enlarging) an admissible flow by the minimal residual capacity of a residual z—s path results in an admissible flow, again.
auammtatioti = zvětšmí
Petr Hliněný,   Fl MU Brno, 2014
Fl: MA010: Cuts and Network Flows
A simple Residual Path Algorithm
Algorithm 4.14. Ford-Fulkerson's for network flows.
input «—  a flow network G — (G, z,s,w); flow f = 0; repeat {
Search (BFS) the graph G to find the set U of those vertices reachable from the source z along residual paths;
if (seU ) {
P = any residual z-s path in G (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 G;
output —>•   a minimum cut in G from U to V(G) — U.
Petr Hliněný,   Fl MU Brno, 2014
Fl: MAOIO: Cuts and Network Flows
Proof of Algorithm 4.14:
For any flow / and any cut C in G, it holds ||/|| < ||C||. If the algorithm stops with a flow / in G and a cut C such that ||C|| — ||/||, then it is clear that / is a maximum flow in G. (We have, however, not proved yet that the algorithm stops!) □
So to prove that whenever the algorithm stops with /, C, then ||/|| — \\C\\, we use the following schematic picture (in which s does not belong to the reachable set U):
/(e) = w(e)
0
U
0
/(e) = 0
Since no further vertex than U is reachable along residual paths, every arc e leaving U has full flow /(e) — w(e), and every arc e entering U has zero flow /(e) — 0. Therefore;
E /(e) - E /(e) = E /(e) = E w(e) = ii^ii ■
e^U e^rlj e^-U e£C
Finally, by Corollary 4.8, we have ||/|| — Ye^u /(e) — Ye^u /(e) ~ ll^ll' finishing the proof. C
Petr Hliněný,   Fl MU Brno, 2014
Fl: MAOIO: Cuts and Network Flows
Basic Consequences
Algorithm 4.14 and its proof provides several interesting mathematical findings:
• Together with Prop. 4.11, it nearly(l) proves Theorem 4.10 (flow-cut duality); □
- what is missing, is a proof that the algorithm terminates, □
- and the latter is not obvious at all for arbitrary real capacities—there do exist non-terminating (and even non-convergent) real examples. □
• If all the capacities are integers, then every step of Algorithm 4.14 deals with integral residua and flows; □
- consequently, the algorithm must terminate under any circumstances,
- and the resulting flow will be integral as well. □
• For instance, if the edge capacities are all set to 1, one obtains the following.
For a graph and vertices s,t, there exist k edge-disjoint s—t paths iff there is no s—t edge cut of size less than k. □
Compare this to Menger's theorem, and to Section 4.5...
Petr Hliněný,   Fl MU Brno, 2014
Fl: MAOIO: Cuts and Network Flows
More precise formulations ... of the previous findings... Theorem 4.15. (Edmonds-Karp)
If Algorithm 4.14 always chooses an augmenting path among residual paths of the least length (measured by the number of edges), e.g., by the BFS, then the algorithm is guaranteed to terminate after 0(\V(G) \ ■ \E(G)\) iterations.
Consequently, Theorem 4.10 is proved. □
Proposition 4.16. If the edge capacities in a flow network G are integral, then there exists a maximum flow which is integral, too.
Algorithm 4.14 outputs such an integral flow in a finite number of steps.
Petr Hliněný,   Fl MU Brno, 2014
Fl: MAOIO: Cuts and Network Flows
4.5   Further Improvements and Extensions
More officient flow algorithms
• Edmonds-Karp (Theorem 4.15):
BFS is used to search for an augmenting path, runtime 0(|V(G)| • \E(G)\2). c
• Dinitz:
— BFS is used to find all the shortest residual paths in G, creating a "layered" residual network.
- The layered network is then completely saturated in one run.
Only 0(\V(G)\) iterations of the main cycle, runtime 0(\V(G)\2 ■ \E(G)\). □
• MPM "Three Indians":
Similar to [Dinitz], but a layered network is saturated faster, runtime 0(|y(G)|3)o
• An advance note on a special "planar" case:
A minimum cut can be found as a shortest path in the dual graph (see Lecture 8).
Petr Hliněný,   Fl MU Brno, 2014
Fl: MAOIO: Cuts and Network Flows
Networks with lower capacities
In a flow network with lower capacities, in addition to the weight function w, there is another weight function £ : E(G) —>• Jig" giving the lower edge capacities.
A flow / is then admissible if 1(e) < /(e) < w(e) for every edge e of the network. □
Notice that an admissible flow may not exist in such a lower-capacitated network. □
Algorithm 4.17. Max-flow in a lower-capacitated network
The solution in a network G — (G, z,s,w,£) is found in two stages:
• First, an admissible circulation r is found in G + sz, respecting both the lower an upper bounds £, w. This is done by finding a maximum flow in an artificial network modelling the "surplus" of lower capacities at every vertex... □
• Second, a maximum flow h is found in a modified network G' — (G, z,s,w — r) (Alg. 4.14); this network has only upper capacities w(e) — r(e) for an edge e. □
• The resulting flow is the sum f = r + h.
Petr Hliněný,   Fl MU Brno, 2014
Fl: MAOIO: Cuts and Network Flows
Networks with vertex capacities
In a flow network with vertex capacities (retaining edge capacities as well), the capacity function is w : E{G) U V{G)     R+.
The meaning of capacity constraints at the vertices 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... )□
Algorithm 4.18. Max-flow in a vertex-capacitated network
Translate a vertex-capacitated network to an ordinary flow network via "doubling" the capacitated vertices (replacing them with new arcs between the two copies), as follows:
5
a
5
b
5
5
Then solve the ordinary network with Algorithm 4.14.
Petr Hliněný,   Fl MU Brno, 2014
Fl: MAOIO: Cuts and Network Flows
Back to Menger's theorem
Setting capacities of all vertices (except the terminals s,t) to 1, immediately proves:
Theorem 4.4. Let G be a graph and s,t G V(G). There exist k internally disjoint s—t paths in G if, and only if, there is no s—t vertex cut in G of size less than k. □
Systems of distinct representatives (SDR)
Definition: Let Mi, M2,..., M^ be a collection of nonempty sets. A system of distinct representatives (SDR) of the set family {Mi, M2,..., M^} is a sequence of pairwise distinct elements (xi,X2, ■ ■ ., Xk) such that Xj G Mi for i — 1, 2,..., k. □
Theorem 4.19. (Hall) Let {M1,M2,Mk} be a family of nonempty sets. Then there exists a system of its distinct representatives if, and only if,
VJc{l,2,...,k}:\\JjejM.
> \J\
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...
Petr Hliněný,   Fl MU Brno, 2014
Fl: MAOIO: Cuts and Network Flows
Flows in image segmentation
Yet another profitable application of flow networks lies in the computer vision area:
The basic image segmentation problem asks for decomposing a given image into a foreground and a background.
• Let the input consists of a pixel matrix, each pixel carrying two values of likelihood to be in the foreground and in the background. Additionally, separation penalties are assigned to the neighbouring pairs of pixels. □
• The network is constructed by introducing a source z and a sink s such that the arcs from z to the pixels have their capacities equal to the foreground likelihood, and the arcs from the pixels to s have their capacities equal to the background likelihood. Additional bidirectional arcs join the neighbouring pixel pairs.
• A minimal cut in this network then defines the separation between foreground and background parts.
Petr Hliněný,   Fl MU Brno, 2014
Fl: MAOIO: Cuts and Network Flows