Jesus A. Gonzalez

July 17, 2019

- Chapter 26 of Introduction to Algorithms (3rd Edition), Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein.

- We can use a directed graph to model a
**flow network**- A material is produced. It goes from a source to a sink
- The source
*produces the material to a***fix**rate - At the sink, the material is
*consumed at the same rate* - The
*flow*of the material**at any point of the system**is the rate at which that material moves

- When can we use flow networks
- Flow networks can be used to model
- Liquids moving through tubes
- Parts of ensemble lines
- Electricity through power lines
- Information through communication networks, etc.

- Flow networks can be used to model

- Directed edges in the flow network lead the material
- Each duct has a capacity
- The maximum rate to which the material flows
- i.e. 200 galons of liquid per hour in a tube
- i.e. 20 amps of electric current in a cable

- The maximum rate to which the material flows

- Vertices are the joints in the duct, different from the source and sink
- Vertices do not collect material

- The material input rate is equal to the material output rate
- Flow conservation property
- Equivalent to the
*Kirchhoff current law*, when the material is electric current

- Compute the highest rate to which the
**material**can be moved- From a source to a sink
*Without breaking any capacity restriction*

- One of the simplest problems related to flow networks
- Can be solved with efficient algorithms

- Graph-based definition for flow networks
- Flow network
- \(G = (V, E)\) is a directed graph in which each edge \((u, v) \in E\) has a non-negative capacity \(c(u, v) \geq 0\).
- If \((u, v) \notin E\), we assume that \(c(u, v) = 0\).
- We distinghish two types of vertices
- a
**source***s* - a
**sink***t*

- a
- We assume that each vertex is in some path from the source to the sink
- \(\forall v \in V\), there exists a path \(s \rightarrow v \rightarrow t\)
- The graph is connected and \(|E| \geq |V| - 1\)

- Given \(G = (V, E)\) we can represent a flow network with capacity function \(c\)
- Let \(s\) be the source of the network and let \(t\) be the sink
- A
*flow*in \(G\) is a function with real values \(f: V x V \rightarrow R\) that satisfies the following three properties- 1-
**Capacity restriction**: \(\forall u, v \in V\), we require \(0 \leq f(u, v) \leq c(u, v)\) - 2-
**Bias simmetry**: \(\forall u, v \in V\), we require \(f(u, v) = -f(v, u)\)

- 1-

- The third property…
3-

**Flow conservation**: \(\forall u \in V - \{s, t\}\), we require:- \(\sum\limits_{v \in V} f(v, u) = \sum\limits_{v \in V} f(u, v)\)

- The quantity \(f(u, v)\), which can be positive, cero, or negative, is called
*the flow from vertex \(u\) to vertex \(v\)* If \((u, v) \notin E\), there can’t be flow from \(u\) to \(v\), then \(f(u, v) = 0\).

- The value of a
*flow*is defined as:- \(|f| = \sum\limits_{v \in V} f(s, v)\)
- The total flow that comes from the source
- \(| |\) denotes the value of flow, NOT absolute value, nor cardinality

- The Problem of Maximum Flow
- We are given a flow network \(G\) with source \(s\) and sink \(t\) and we want to find a maximum flow value

- The flow from a vertex to another should not exceed the given capacity

- The notation says that:
- The flow from a vertex \(u\) to a vertex \(v\) is the non negative of the flow in opposite direction

- The total flow comming from a vertex, different from the source or sink, is
**0**

- There can be several sources and sinks
- \({s_1, s_2, \dots, s_m}\)
- \({t_1, t_2, \dots, t_n}\)

- This problem is not more difficult than the previous one
- Can be reduced to an ordinal maximum flow problem
*Super-source**Super-sink*

- Summation notation is implicit
- \(\sum\limits_{x \in X}\sum\limits_{y \in Y} f(x, y)\)

- Conservation flow can be expressed as
- \(f(u, V) = 0\) for all \(u \in V - \{s, t\}\)

- In \(f(s, V - s) = f(s, V)\), the term \(V - s\) refers to the set \(V - \{s\}\)

- Three important ideas, relevant for many flow algorithms and problems
- Residual networks
- Augmenting paths
- Cuts

- Different implementations of the algorithm with different execution times

- Iterative method
- Starts with \(f(u, v) = 0\) for all \(u, v \in V\), with an initial flow value of 0
- At each iteration, we increment the flow value when we find an “
**augmenting path**”:*a path from the source \(s\) to the sink \(t\) that we can use to send flow* - We repeat this process until we cannot find any augmenting path

- The theorem of maximum-flow minimum-cut shows that, at the end, the process takes a maximum flow

- Intuitivelly
- Given a flow network and a flow, the residual network consists of edges that can admit more flow

- Formally
- Given a flow network \(G = (V, E)\) with source \(s\) and sink \(t\)
- Let \(f\) be a flow in \(G\), and considering a pair of vertices \(u, v \in V\)
- The amount of additional flow that we can take from \(u\) to \(v\) without exceding capacity \(c(u, v)\) is the
of \((u, v)\) given by \(c_f(u, v) = c(u, v) - f(u, v)\)*residual capacity*

- Given a flow network \(G = (V, E)\) and a flow \(f\), the
**residual network**of \(G\) induced by \(f\) is \(G_f = (V, E_f)\), where- \(E_f = \{(u, v) \in V x V : c_f(u, v) > 0\}\)

- Given a flow network \(G = (V, E)\) and a flow \(f\)
- An
\(p\) is a path from \(s\) to \(t\)*augmenting path*\(G_f\)*in the residual network* - Figure 26.4b
- We can increase the flow in 4 units, \(c_f(v_2, v_3) = 4\)
- The
is 4 without violating the capacity restriction, the lowest residual capacity is 4:*residual capacity of the path**\(c_f(p) = min\{c_f(u, v) : (u, v) \in p\}\)*

- The

- An

- Given \(G = (V, E)\), a flow network
- Let \(f\) be a flow in \(G\)
- Given \(p\) an augmenting path in \(G_f\)
- Define a flow \(f_p\) in \(G_f\) as the function \(f_p : V x V \rightarrow R\) by:

\(f_p(u, v) = \begin{cases} c_f(p) &\mbox{if } (u, v) \in p\\ -c_f(p) &\mbox {if } (v, u) \in p\\ 0 &\mbox{any other way}\\ \end{cases}\)

- Then \(f_p\) is a flow in \(G_f\) with value \(|f_p| = c_f(p) > 0\)

- Corolary 26.4 tells us that, if we add \(f_p\) to \(f\), we obtain another flow in \(G\) with a value closer to the maximum
- Let \(G = (V, E)\) be a flow network
- Let \(f\) be a flow in \(G\)
- Let \(p\) be an augmenting path in \(G_f\)
- Let \(f_p\) be defined as previous (previous page)
- We define a function \(f': V x V \rightarrow R\) by \(f'=f + f_p\)
- Then, \(f'\) is a flow in \(G\) with value \(|f'| = |f| + |f_p| > |f|\)

- The flow is maximum
its residual network does not contain an augmenting path*iff* - To show this we need the cut notion
- A
\((S, T)\) of a flow network \(G = (V, E)\) is a partition of \(V\) in \(S\) and \(T = V - S\) such that \(s \in S\) and \(t \in T\)*cut* - The
through the \(cut(S, T)\) is defined as \(f(S, T)\)*Net Flow* - The
of \(cut(S, T)\) is \(c(S, T)\)*Capacity* - A
of a network is a cut with minimum capacity over all cuts in the network*minimum cut*

- Net flow

\(f(v_1,V_3) + f(v_2,v_4) - f(v_3,v_2) = 12 + 11 - 4\)

\(= 19\) - Capacity

\(c(v_1,v_3) + c(v_2,v_4) = 12 + 14\)

\(=26\)

- The net flow through any cut is the same and equal to the value of the flow
- Given \(f\), the flow in a flow network \(G\) with source \(s\) and sink \(t\), and let \((S, T)\) be a cut of \(G\)
- Then the net flow through \((S, T)\) is \(f(S, T) = |f|\)

- The value of any flow \(f\) in a flow network \(G\) is bounded from above by the capacity of any cut of \(G\)

- The value of a maximum flow is equal to the capacity of a minimum cut
- If \(f\) is a flow in a network flow \(G = (V, E)\) with source \(s\) and sink \(t\), then the following conditions are equivalent:
- \(f\) is a maximum flow in \(G\)
- The residual network \(G_f\) does not contain augmenting paths
- \(|f| = c(S, T)\) for any cut \((S, T)\) of \(G\)

- Depends on a method to find the augmenting path
- Use breadth First Search
- Edmonds-Karp algorithm
- The augmenting path is the shortest one from \(s\) to \(t\)

- Theorem 26.9
- The total number of augmentings is \(O(VE)\), \(O(E)\) per augmenting. Then, the algorithm has an execution time of \(O(VE^2)\)

- Other methods to compute maximum flow
- Generic-Push-Relabel takes \(O(V^2E)\)
- Relabel-to-Front takes \(O(V^3)\)