Source code online books for professionals by professionals

Figure 10-3.  An edge capacity simulated by dummy nodes

---

ChApTeR 10 
■
 MATChINgs, CuTs, ANd Flows 
216
Let’s walk through the technicalities. Just like in the zero-one case, we have two rules for how our flow interacts 
with edges and nodes. As you can see, they parallel the disjoint path rules closely:
The amount of flow going 
•
into any node except s or t must equal the amount of flow going out 
of that node.
At most 
•
c(e) units of flow can go through any given edge.
Here, c(e) is the capacity of edge e. Just like for the disjoint paths, we are required to follow the edge direction,  
so the flow back along an edge is always zero. A flow that respects our two rules is said to be feasible.
This is where you may need to take a breath and focus, though. What I’m about to say isn’t really complicated, but 
it can get a bit confusing. I am allowed to push flow against the direction of an edge, as long as there’s already some 
flow going in the right direction. Do you see how that would work? I hope the previous two sections have prepared you 
for this—it’s all a matter of canceling flow. If I have one unit of flow going from a to b, I can cancel that unit, in effect 
pushing one unit in the other direction. The net result is zero, so there is no actual flow in the wrong direction  
(which is totally forbidden).
This idea lets us create augmenting paths, just like before: If you add k units of flow along an incoming edge or 
cancel k units on an outgoing one at some node u, that node will be overflowing. It will have more flow entering than 
leaving, which isn’t allowed. You can fix this either by adding k units of flow along an outgoing edge or by canceling k 
units on an incoming one. This is exactly what you did in the zero-one case, except there k was always 1.
In Figure 
10-4
 two states of the same flow network are shown. In the first state, flow has been pushed along the 
path s-c-b-t, giving a total flow value of 2. This flow is blocking any further improvements along the forward edges. As 
you can see, though, the augmenting path includes a backward edge. By canceling one of the units of flow going from 
c to b, we can send one additional unit from c via d to t, reaching the maximum.