Actual responses to actual questions from students of Math 344, Introduction to Combinatorics (Spring 2004).
I am having problems with solving backwards in section 4.3 in getting the maximal flow. For Question #1 I have the algorithm as a a-b-e-z how do you get 13 (which is the answer in the book)?
When doing the augmenting flow algorithm, I too get a-b-e-z. This means I have an a-z chain of slack edges, and I augment the old flow by 1 (this is the number associated with this chain in my algorithm).
How do I know that this new flow is maximal? I don't, so I erase all my old labels and do the augmenting flow algorithm again on the new flow. What happens? I stop labeling after I've labeled vertices a, b, and c. According to the algorithm, this means that P = {a,b,c} gives a saturated a-z cut, and therefore this (new) flow is maximal.
I have done and redone part (a) three or four times to try and get the same answer as in the back of the text, but I still get that the max flow is 11, and P = {a, b, c, f, g, h, k, l, m} (whereas the back of the text says that the max flow is 13, and P = {a, b, c}). However, the text's answer for 5(a) is also the same answer it gives for Ex. 1, so I'm not sure if this is a typo that hasn't been caught yet (it isn't listed among the corrections to the text linked to from your web page). I don't see why the answer I get should be wrong, because with max flow = 11 and P = {a, b, c, f, g, h, k, l, m}, the conditions for Corollary 2a (page 140) are satisfied, so this should be a max flow and a minimal cut. Is this correct?
I've looked into this a little, and think you're right: the maximal flow has value 11.
Regarding the modification to the augmenting flow algorithm for part (c), could you suggest how we are supposed to modify the algorithm to achieve a minimal flow?
That's a good question. Perhaps you could allow negative capacities and flows? Then negate all values: your lower bound for each edge becomes a (negative) upper bound (capacity), and you are looking for the largest (negative) flow. When you find this maximal flow, its negative is a minimal flow.