Consider the network diagram in Figure 13.14. For each directed edge, the first number is the capacity and the second value is intended to give a flow \(\phi\) in the network. However, the flow suggested is not valid.
Identify the reason(s) \(\phi\) is not valid.
Without changing any of the edge capacities, modify \(\phi\) into a valid flow \(\widehat{\phi}\text{.}\) Try to use as few modifications as possible.
Figure13.14.An invalid flow in a network
2.
Alice claims to have found a (valid) network flow of value \(20\) in the network shown in Figure 13.15. Bob tells her that there’s no way she’s right, since no flow has value greater than \(18\text{.}\) Who’s right and why?
Figure13.15.A network
3.
Find an augmenting path \(P\) with at least one backward edge for the flow \(\phi\) in the network shown in Figure 13.16. What is the value of \(\delta\) for \(P\text{?}\) Carry out an update of \(\phi\) using \(P\) to obtain a new flow \(\hat{\phi}\text{.}\) What is the value of \(\hat{\phi}\text{?}\)
Figure13.16.A network with flow
4.
Prove Proposition 13.7. You will need to verify that the flow conservation laws hold at each vertex along an augmenting path (other than \(S\) and \(T\)). There are four cases to consider depending on the forward/backward status of the two edges on the augmenting path that are incident with the vertex.
For each of the augmenting paths \(P_1\text{,}\)\(P_2\text{,}\)\(P_3\text{,}\) and \(P_4\) in Example 13.8, update the flow in Figure 13.2. (Note that your solution to this exercise should consist of four network flows. Do not attempt to use the four paths in sequence to create one updated network flow.)
8.
Continue running the Ford-Fulkerson labeling algorithm on the network flow in Figure 13.12 until the algorithm halts without labeling the sink. Find the value of the maximum flow as well as a cut of minimum capacity.
9.
Use the Ford-Fulkerson labeling algorithm to find a maximum flow and a minimum cut in the network shown in Figure 13.17 by starting from the current flow shown there.
Figure13.17.A network with flow
10.
Figure 13.18 shows a network. Starting from the zero flow, i.e., the flow with \(\phi(e)=0\) for every directed edge \(e\) in the network, use the Ford-Fulkerson labeling algorithm to find a maximum flow and a minimum cut in this network.
Figure13.18.A network
11.
Consider a network in which the source \(S\) has precisely three neighbors: \(B\text{,}\)\(E\text{,}\) and \(F\text{.}\) Suppose also that \(c(S,B)=30\text{,}\)\(c(S,E)=20\text{,}\) and \(c(S,F)=25\text{.}\) You know that there is a flow \(\phi\) on the network but you do not know how much flow is on any edge. You do know, however, that when the Ford-Fulkerson labeling algorithm is run on the network with current flow \(\phi\text{,}\) the first two vertices labeled are \(S\) with label \((*,+,\infty)\) and \(F\) with label \((S,+,15)\text{.}\) Use this information to determine the value of the flow \(\phi\) and explain how you do so.
