 |
Suppose arc DF with flow
is added to the feasible spanning tree. The unique undirected cycle in
this case is DF-FC-CB-BD. The above network shows next to each arc the
resulting incremental flow (in parentheses) and the cost per unit flow
(to the left of the parentheses). |
When ,
the resulting overall increment in total cost ( )
is |
= 4(1) + 2(-1) + 2(-1) + 3(1) = 3. |
Hence, the rate of change of
as
is increased is 3. |