The problem is to find a set of flows along directed edges with a capacity constraint that maximizes flow between two nodes. Assume integer capacities, no edges entering source or leaving sink, and connected. The sum of flows out of a node must equal the sum of flows in; since all flow must pass somewhere, any cut separating the source and sink bounds the capacity above. Cannot use any obvious greedy algorithm, as a misdirected flow can cut off future paths. Thus we use a form of backtracking; create a residual graph that includes reverse edges for those that have flows (corresponding to the ability to decrease that flow) and add flow in that graph (updating it each time) until there is no augmenting path. Since capacity is finite and each iteration increases capacity, this process terminates, with no more than C loops (the capacity of the cut between the source and the rest of the graph) each taking m time (time proportional to length of the augmenting path), giving O(Cm).

Why can we not use the true capacity, since it is well-defined for a graph? I understand that it is not conveniently computable, but it is a constant.

No insights.

No complaints.

If we take a cut separating the source and sink, the total flow equals the flow across the cut minus the backflow across it. Thus the capacity of a cut bounds the capacity of the graph. More powerfully, the maximum flow equals the capacity for some cut (the minimum cut) (if all cuts are under capacity, there must be an augmenting path). Since the FFA terminates at this point, it returns a maximal flow. Moreover, this means that for any graph with integer capacities, there is an integer-valued flow (not necessarily unique, and not all maximal flows need have this property). The requirement of rational capacities is necessary as for some choices of augmenting paths, FFA on real capacities can run infinitely.

No questions.

No insights.

I would have liked to see an explanation of why rational numbers are permissible (which is, I believe, because in any finite graph with rational capacities there is a lcm of the capacities, and if all capacities are multiplied by that we get an integer graph). In any event, unless I miss something they say that the requirement that the flows be integers is necessary, state the problems with irrational capacities, and then state that real problems might have rational capacities, without showing that the rational capacities are workable.