13.7: Exercises

1. 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 \(ϕ\) in the network. However, the flow suggested is not valid

a. Identify the reason(s) \(ϕ\) is not valid.

b. Without changing any of the edge capacities, modify \(ϕ\) into a valid flow \(\hat{ϕ}\). Try to use as few modifications as possible.

Figure 13.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. Who's right and why?

Figure 13.15. A network

3. Find an augmenting path \(P\) with at least one backward edge for the flow \(ϕ\) in the network shown in Figure 13.16. What is the value of \(δ\) for \(P\)? Carry out an update of \(ϕ\) using \(P\) to obtain a new flow \(\hat{ϕ}\). What is the value of \(\hat{ϕ}\)?

Figure 13.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.

5. Find the capacity of the cut \((L,U)\) with

\(L=\{S,F,H,C,B,G,I\}\) and \(U=\{A,D,E,T\}\)

in the network shown in Figure 13.16.

6. Find the capacity of the cut \((L,U)\) with

\(L=\{S,F,D,B,A\}\) and \(U=\{H,C,I,G,E,T\}\)

in the network shown in Figure 13.16.

7. For each of the augmenting paths \(P_1, P_2, P_3\), 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.

Figure 13.17. A network with flow

10. Figure 13.18 shows a network. Starting from the zero flow, i.e., the flow with \(ϕ(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.

Figure 13.18. A network

11. Consider a network in which the source S has precisely three neighbors: \(B, E\), and \(F\). Suppose also that \(c(S,B)=30, c(S,E)=20\), and \(c(S,F)=25\). You know that there is a flow \(ϕ\) 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 \(ϕ\), the first two vertices labeled are \(S\) with label \((∗,+,∞)\) and \(F\) with label \((S,+,15)\). Use this information to determine the value of the flow \(ϕ\) and explain how you do so.