
7.2. PRELIMINARIES 233
(3,1)
(4,1) (1,1)
(2,2) (3,3)
(2,2)
(3,0)
(a)
s t
3 (3)
3 (3) 1 (1)
0 (0) 3 (9)
2 (4)
1 (0)
(b)
3 (3)
3 (3) 1 (1)
2 (4) 1 (3)
2 (4)
3 (0)
(c)
Figure 7. 8 (a) A (single-source single-sink) flow network N with arcs labeled with the
pair (c(e), w(e)) (capacity, cost ). (b) A maximum flow of value 6 for flow network N . Each
arc of N is labelled with its flow and, in pare ntheses, the cost of the flow on that arc. The
total cost of t hi s flow is 20. (c) A minimum-cost maximum flow for N. Note , the value of
this flow is still 6 but the cost is now 18.
• Conservation rule: The flow coming in to a non-terminal node is th e same as the
flow going out of the