Recall Exploration 7.1.1. Suppose that we wish to install a toll booth on these bridges so that each person going to \(v_5\) pays a toll at least once. The cost of installing a toll booth on a bridge is proportional to it’s capacity. Find three different ways to install these booths, and find what you believe is the cheapest way to do so.
Given a capacitated network \(N\text{,}\) a cut of \(N\) is a partition of the vertex set into nonempty subsets \(C=(V_1, V_2)\text{,}\) where \(V=V_1\sqcup V_2, v_s\in V_1, v_d\in V_2\text{.}\)
Consider the dual problem for this maximization problem where \(\mu_{j}\) is the unconstrained dual variable for the vertex equality constraint and the \(y_{ij}\) is the dual variable for the capacity constraint. Verify that this problem may be written as
Suppose \(\mu_j=-1\text{.}\) What could \(\mu_i, y_{ij}\) be? What value for \(\mu_i\) would minimize the dual objective function? What happens if \(\mu_i\) is huge? How would the resulting \(\mu_i\) that affect the inequality \(-\mu_k+\mu_i+y_{ki}\geq 0\text{?}\)
We explore a way of generating potential minimum cuts using a maximum flow. Again recall Exploration 7.1.1 and your proposed maximum flow \(f'\text{.}\)
Show that for any \(v_k\) in \(V'_1\text{,}\) there is an \(\alpha\)-path \(P\text{:}\) a sequence of vertices starting \(v_s\) to \(v_k\text{,}\) where between \(v_{i}\) and \(v_j\) either \((v_i, v_j)\) or \((v_j, v_i)\in E\text{.}\)
We define a new flow \(f''\) as follows: for each forward edge of \(P\text{,}\)\((v_i, v_j)\text{,}\) we add \(x_{ij}''=q+x'_{ij}\text{.}\) For each backwards edge \((v_j, v_i)\) we subtract \(x_{ji}'' = x'_{ji}-q\text{.}\)
(Not necessary for this proof, but to tie things in, if \(x_{ij}''=c_{ij}\text{,}\) what does that say about \(y_{ij}\) from the dual problem in Activity 7.2.4? If \(x_{ij}'\lt c_{ij}\text{,}\) what does that say about \(y_{ij}\text{?}\) )
Going back to Activity 7.2.4 if we let \(\mu_i=0\) for \(v_i\in V_1'\) and \(\mu_j=-1\) for \(v_j\in V_2'\text{,}\) what is the value of the dual min objective?
Let \(N = (V, E)\) be a capacitated directed network with unique fixed source and unique fixed sink, no edges into the source, and no edges out of the sink. Then the value of the maximal flow from \(v_s\) to \(v_d\) is equal to the minimal cut capacity in \(N\text{.}\)
Define a new flow \(f'\) as follows: for each forward edge of \(P\text{,}\)\((v_i, v_j)\text{,}\) we add \(x_{ij}'=q+x_{ij}\text{.}\) For each backwards edge \((v_j, v_i)\) we subtract \(x_{ji}' = x_{ji}-q\text{.}\)