Week 4

In this fourth week we continued on to discuss the details of the max-flow/min-cut theorem. We began by describing the architecture of the proof. As a side note, we did not follow the discussion in the textbook, as it seemed like the above notes which were part of a course at the university of Illinios were way more transparent
We made the extra assumption that the network in question \(G\) has no 2-cycles (this is pretty harmless)abd went on to prove the flow-capacity (in)equality:

Let \(f\) be any flow \(f\) of value \(\vert f\vert \) and \((S,T)\) any cut of capacity \(\vert \vert (S,T) \vert \vert\).
Then we have \[\vert f\vert \le \vert \vert \vert S,T\vert\vert\]
Essentially this relied on two sneaky observations (see if you can remember which ones): \begin{align} \vert f\vert =\partial f(s)=\sum_{v \in S}\partial f(v)=&\sum_{v\in S}\bigg(\sum_{u \in S} f(v\rightarrow u) -\sum_{w\in S}f(w\rightarrow v)\bigg)\\=&\sum_{v\in S}\bigg(\sum_{u \in T} f(v\rightarrow u) -\sum_{w\in T}f(w\rightarrow v)\bigg)\\ \le & \sum_{v\in S}\bigg(\sum_{u \in T} f(v\rightarrow u)\bigg)\le \sum_{u\in S, v \in T} f(u\rightarrow v)\le \sum c(u\rightarrow v)=\vert\vert (S,T)\vert \vert \end{align} In particular, we could also conclude when this inequality was in fact an equality. To this end, we say that the flow saturates an edge if \(f(u\rightarrow v)=c(u\rightarrow v)\) and avoids an edge if \(f(u\rightarrow v)=0\). The above series of implications then easily implies that
the following are equivalent
  1. \(\vert f \vert =\vert \vert S,T\vert \vert\)
  2. the flow saturates any edge from \(S\) to \(T \) and avoids any edge from \(T\) to \(S\)
In this case the flow is maximal and the cut is minimal.
The question of understanding the max-flow/min-cut theorem hence relies on figuring out which flows/cuts are configured so that the flow saturates certain edges and avoids others.
The clever idea here is to introduce a new network with a new capacity based off \( f \)
The residual network \(G_f\) has the same vertex set as \(G\) and an edge \(u\rightarrow v \) whenever \(u\rightarrow v\) has nonzero residual capacity.
Here, we define the residual capacity as follows: \begin{equation} c_f(u\rightarrow v)= \begin{cases} c(u\rightarrow v)-f(u\rightarrow v) & \text{if}\ u\rightarrow v \in E(G) \\ f(u\rightarrow v) & \text{if } v\rightarrow u \in E(G) \\ 0 & \text{otherwise} \end{cases} \end{equation}
In other, words, to construct the residual network \(G_f\), simply add a directed edge between any two vertices and perform the following operation: if there is an edge \(u\rightarrow v\) in \(G\), then the new capacity is \(c(u\rightarrow v)-f(u\rightarrow v)\). If the edge in \(G\) goes in the opposite direction \(v\rightarrow u\) however, then the capacity is \(c_f(u\rightarrow v)=c(v\rightarrow u)\). Now, delete all edges with 0 residual capacity. In the illustration below, this procedure is performed on our running example: The reason for invoking this construction is the following lemma:
If the residual network has no directed paths from source to sink, then flow \(f\) is maximal on \(G\)
To argue this, we merely need to show that given \(f\), there exists a cut \(S,T\) such that \(f\) saturates edges from \(S\) to \(T\) and avoids edges from \(T\) to \(S\). To this end, we let \(S\) be all vertices reachable from \(s\) (i.e there is a directed path from \(s\) to any \(v \in S\)) and let \(T\) be the complement. Then this is indeed a cut for the network \(G\). Let \(u\rightarrow v\) be an edge from \(S\) to \(T\) in \(G\). Then, by construction, this edge is deleted in \(G_f\) (otherwise \(u\) would be reachalble from \(s\), and \(u \in \S\cap T\), a contradiction). so that \[ 0=c_f(0\rightarrow v)=c(u\rightarrow v)-f(u\rightarrow v)+f(v\rightarrow u) \] This in particular implies that \(c(u\rightarrow v)-f(u\rightarrow v)=0\) (saturatedness) and \(f(v\rightarrow u)=0\) (avoidance)

We concluded our discussion of the theorem by analyzing what happens in the case where \(f\) is in fact non-maximal.
In this case, by the above, we can find a path in the residual graph. We let \(F\) denote the minimum of the capacities along that path. In the original network \(G\), there now also corresponds an undirected path \(p\). We now define a new flow \(f'\) on \(G\) as follows \begin{equation} f'(u\rightarrow v)= \begin{cases} f(u\rightarrow v)+F & \text{if}\ u\rightarrow v \in p \\ f(u\rightarrow v)-F & \text{if } v\rightarrow u \in p \\ 0 & \text{otherwise} \end{cases} \end{equation} The idea is illustrated below with our running example, where \(F\=5) and the flow along the red path either increases or decreases based off whether the arrows in the residual netwrok run in the same direction as the original In class, we argued why this is indeed a flow and why the value of the flow gets increased by \(F>0\). The leads to the famous Ford-Fulkerton algorithm to maximize flow:
Let \(f\) be a flow on a graph (possibly zero). Then the following algorithm produces a maximal flow:
  1. if \(f\) is nonmaximal, find a path in the residual network
  2. compute the flow along each edge of the path and let \(F\) be the minimum
  3. in the corresponding path of the original network \(p\) add/deduce the flow by \(F\) according to direction as above
  4. repeat untill there are no paths in residual network
We can now summarize the max-flow, min-cut theorem:
Let Let \(f\) be any flow \(f\) of value \(\vert f\vert \) and \((S,T)\) any cut of capacity \(\vert \vert (S,T) \vert \vert\). Then
  1. we have \[\vert f\vert \le \vert \vert \vert S,T\vert\vert\]
  2. the flow is maximal if and only if the above is an equality
  3. the flow is maximal if and only the residual network has no paths
  4. in the case where the flow is not maximal, the Ford-Fulkerton algorithm describes how to use such paths to increase the flow at each step