Solution. From node \(1\), the labels are \(2\) for node \(2\) and \(3\) for node \(3\); node \(2\) is made permanent with \(d_2 = 2\). Then node \(3\) is added with \(d_3 = 3\), and the arc \((3, 2)\) would give \(3 - 2 = 1 < 2\), but node \(2\) is already final. The true distance to \(2\) is \(1\). The proof of Theorem 8.2.1 used non-negative lengths to say that a path leaving \(P\) cannot get shorter afterwards.

Solution. Primal: minimise \(\sum c_{ij}x_{ij}\) subject to \(Nx = e_1 - e_5\), \(x \geq 0\). Dual: maximise \(\pi _1 - \pi _5\) subject to \(\pi _i - \pi _j \leq c_{ij}\) for each arc. Take \(\pi _i = 20 - d_i\) with the distances \(d = (0, 7, 9, 20, 20, 11)\): then \(\pi _i - \pi _j = d_j - d_i \leq c_{ij}\) by Bellman’s equations, and \(\pi _1 - \pi _5 = 20\), equal to the primal optimum.

Solution. \(S = \{1\}\) has outgoing arcs \((1, 2)\), \((1, 3)\), \((1, 6)\) with capacity \(10 + 5 + 15 = 30\). Every cut’s capacity is at least the value of every flow, and a flow of \(25\) exists, so no cut has capacity below \(25\); the cut \(\{1, 2, 3, 4, 6\}\) attains it.

Solution. \(\Phi \bigl ((20 - 19.5)/1.28\bigr ) = \Phi (0.39) = 0.652\). For probability \(0.95\), \(D = 19.5 + 1.645 \times 1.28 = 21.6\). By the simulation the true probabilities are somewhat lower, so a cautious planner would add a margin.

Solution. Both lie on the critical path, and the other paths have lengths \(B \to E \to G\): \(15.67\) and \(A \to D \to F\): \(14.83\), far shorter, so crashing \(G\) by one unit (cost \(80\)) gives \(18.5\). To reach \(17.5\) crash both \(G\) and \(C\) (cost \(180\)); \(B \to E \to G\) becomes \(14.67\) and \(A \to D \to F\) stays \(14.83\), so \(A \to C \to E \to G\), at \(17.5\), is still critical and the target is met.

Solution. For an undirected graph each edge column has two \(+1\)s, and Theorem 7.4.3 needs its rows split so that the two ends of every edge fall in different groups, a two-colouring, which exists exactly when the graph is bipartite; the triangle’s matrix has determinant \(2\). For a directed graph each column has \(+1\) and \(-1\), and the single group of all rows works, whatever the cycles.