Flows and Connectivity · Flows
Lesson 2
Nikolai Chukhin · Alexander S. Kulikov
Consider another transportation network. Again, we need to deliver as many units of goods per day as possible from the factory \(S\) to the store \(T\), using the remaining vertices as transfer points.
You already have a delivery plan: in the diagram below, the label “8/10” on edge \((S,A)\) means the capacity of this road is ten and you plan to send eight units of goods on it. It is easy to verify that goods do not accumulate at transfer points: each point receives exactly as many units as it sends out. As shown, your plan delivers eleven units of goods daily from \(S\) to \(T\). 
Now you want to convince your boss that your delivery plan is optimal. To do this, you want to find a set of vertices \(L\) such that \(S \in L\), \(T \not \in L\), and it is physically impossible to transport more than eleven units of goods from \(L\) to \(V \setminus L\). For example, if we take \(L=\{S, A, B, C, D\}\), it becomes clear that more than twenty units per day cannot be delivered: the total capacity of all edges from \(L\) to \(V\setminus L\) is twenty. And \(L=\{S\}\) shows that no more than fourteen units can be delivered.Problem. Find a set \(L\) proving that no more than eleven units of goods can be delivered in this network. (Enter the vertices of the set \(L\) separated by spaces.)