Section 7.4 Summary of Chapter 7
We use introduce the notion of networks, a pair \(N=(V, E)\) where \(V\) is a set of vertices and \(E\) is a set of ordered pairs of vertices called edges. We also discuss capacitated networks where each edge \((v_i, v_j)\) has a capacity \(c_{ij}\geq 0\text{.}\) For capacitated networks with designated sources and sinks, we can define a flow, an assignment \(0\leq x_{ij}\leq c_{ij}\) to each edge \((v_i, v_j)\) so that for any non source/sink vertex \(v_i\) we have that
\begin{equation*}
\sum_{v_j\in V} x_{ji} - \sum x_{ij} =0.
\end{equation*}
We focus on capacitated networks with a unique source and sink, with no edges going into the source or out of the sink.
Finding a maximum flow on such a network may be solved as a linear optimization problem:
\begin{align*}
\textbf{Maximize: } \displaystyle \sum_{i} x_{id}\\
\textbf{subject to: } \sum_{v_i\in V}x_{ij} - \sum_{v_i\in V} x_{ji} \amp = 0, \text{for each non source/sink vertex }v_j\\
x_{ij}\amp \leq c_{ij}, \text{for each edge} (v_i, v_j)\\
x_{ij}\amp \geq 0, \text{for each edge} (v_i, v_j).
\end{align*}
Another problem on such a network is the minimum cut, a cut is a pair \((V_1, V_2)\) so the \(V\) is the disjoint union on \(V_1, V_2\text{,}\) \(v_s\in V_1\) and \(v_d\in V_2\text{.}\) The capacity of a cut is the sum
\begin{equation*}
\sum_{v_i\in V_1, v_j\in V_2}x_{ij}.\text{.}
\end{equation*}
Careful analysis of the dual problem to the maximum flow problem shows that the capacity of any cut is an upper bound for the value of any flow.
The Ford-Fulkerson Algorithm Definition 7.2.10 which identifies a maximum flow. Then, starting with \(V_1=\{v_s\}\text{,}\) we recursively add vertices \(v_i\) to \(V_1\) if there is an edge from \(V_1\) to \(v_i\) which is not at maximum capacity, or a backwards edge from \(v_i\) to \(V_1\text{.}\) When this is done, we let \(V_2=V\backslash V_1\) and this forms a cut who by construction, has the same capacity as the maximum flow. So by the Weak Duality Theorem, both are optimal.
Another type of network is a weighted network, where each edge \((v_i, v_j)\) has a potentially negative weight \(w_{ij}\text{.}\) Dijkstra’s Shortest Path Algorithm Definition 7.3.7 describes an algorithm which identifies the distance (sum of weights) from a starting source \(v_s\) to any other vertex \(v_i\) in the network, by labeling each vertex with the current shortest distance from \(v_s\) to \(v_i\) and relabeling and readjusting as shorter distances are found.
The shortest path algorithm has a useful application in the Minimum Cost Flow Algorithm Definition 7.3.14. In this problem, we try to find a flow of value \(F\) from \(v_s\) to \(v_d\) on a weighted capacitated network that minimizes the cost to do so. One can identify shortest paths from \(v_s\) to \(v_d\) and increase flows along this path, and repeat recursively. However, doing so greedily may result in non-optimal solutions. We construct a second network \(N'\) where backwards edges with negative weight are added for flows on \(N\) to represent the ability to reduce flow along edges, and the shortest paths are found on \(N'\text{.}\) Doing so repeatedly results in the actual minimum cost flow.
