A flow algorithm must preserve every node balance while changing individual arc flows. A spanning tree makes this bookkeeping particularly transparent: once the non-tree flows have been fixed, the tree flows are forced. Adding one non-tree arc creates one cycle, so a whole feasible direction can be found by tracing a single path. This section gives exact-arithmetic pivot rules for a connected finite network.
The tree representation
Let be a finite connected directed multigraph without self-loops. Parallel and oppositely directed arcs are separately labeled. Write for its node-arc incidence matrix, with at the tail and at the head. A feasible flow satisfies and for finite bounds . Thus is outflow minus inflow; necessarily . The cost is .
Definition 26.1.1
(Tree solution)
Choose a spanning tree of the underlying undirected graph. A tree solution for fixes each non-tree arc at one of its bounds, or , and solves the node balances for the tree arcs. It is feasible if the resulting tree flows obey their bounds.
A tree arc may itself be at a bound: that is a degenerate tree solution, not a reason to discard the tree. A non-tree arc with equal bounds is fixed and cannot enter.
Theorem 26.1.2
(Tree balances have a unique solution)
For any choices of the non-tree flows and any with zero total, there is exactly one real assignment to the tree arcs satisfying .
Proof
(Leaf elimination)
Subtract the non-tree contributions from to obtain a residual balance with zero total. At a leaf of the tree, its only incident tree flow is uniquely determined by the leaf balance, with a sign depending on the arc orientation. Remove the leaf and update its neighbor's residual balance by the contribution of that flow. The residual balances still sum to zero. Repeat until one vertex remains; its balance then holds automatically. This constructs a solution and each leaf equation forces the value chosen, proving uniqueness. The solution is feasible only if each calculated value lies in its interval.
Concept lensAlgebraic
Spanning trees are bases of the incidence matrix
Every column of has one and one , so the rows of sum to zero and every column lies in the subspace of dimension . The theorem says that the tree columns map onto bijectively: they form a basis of , which is therefore the column space of . Conversely, a set of arcs containing an undirected cycle has dependent columns, because the signed sum of the columns around the cycle is zero. Hence the bases of are exactly the arc sets of spanning trees, and a tree solution is a basic solution of the bounded linear program: tree arcs are the basic variables, and non-tree arcs are nonbasic variables held at a bound.
Prices, directions and the ratio test
Choose node prices with for each tree arc . One price may be fixed arbitrarily and the others propagated along the tree. Define for every arc. For a non-tree arc at its lower bound, the only possible initial direction is forward and its cost slope is . For one at its upper bound the initial direction is backward and the slope is . Therefore a candidate improving arc has at its lower bound, or at its upper bound.
Common mistake
(Reading the improving sign without the bound status)
It is tempting to enter only arcs with . That rule is correct only for a non-tree arc at its lower bound. An arc at its upper bound can only decrease, so its slope is and it improves when . In the second worked example below, is positive and yet is the right entering arc.
To find the accompanying tree changes, add the entering arc to . It creates one undirected cycle. Give the entering arc coefficient if increasing from its lower bound and if decreasing from its upper bound. Assign coefficients or to the tree arcs on the cycle so that ; other coefficients are zero. Equivalently, follow the entering arc in its chosen direction and return along the unique tree path, recording when travel agrees with an original orientation and otherwise.
Proposition 26.1.3
(The cycle slope is the entering reduced cost)
Let be prices with for every tree arc , let be a non-tree arc, and let be its cycle direction: , , and for every arc off the cycle. Then
Proof
(Rewrite costs as reduced costs minus a potential difference)
For every arc , the definition of gives , and is the -th entry of . Hence
because . In the remaining sum, off the cycle and on the tree arcs of the cycle. Only the entering arc survives, so .
The proof uses two different cancellations, and it is worth keeping them apart.
Proof X-ray
Why the reduced cost is the whole slope
Assumptions and where they enter: the condition removes the potential term, and the tree prices remove every other cycle arc. The first cancellation does not use the tree at all: for any circulation direction and any prices, , because a circulation cannot detect a potential difference. The tree is used only to make the reduced costs vanish on the other arcs of this particular cycle.
Key move: replacing by , which changes every arc cost but no cycle cost.
What would break: prices left over from an earlier tree need not vanish on the current tree arcs. The single-arc test would then misreport the slope; after the first worked example's pivot, the old prices give the new tree arc the reduced cost .
How it closes: the proposition gives the sign of the slope, not a decrease of cost. If the step length below is zero, the cost does not move at all.
The largest feasible step is the minimum of over cycle arcs with and over those with . Include the entering arc in this minimum. Set . If a tree arc reaches a bound, it can leave; replacing it by the entering arc yields another spanning tree because the removed edge lies on the new cycle. Other tied tree arcs can remain in the tree at their bounds. If only the entering arc reaches its opposite bound, keep the old tree and treat the arc as non-tree at that opposite bound: this is a bound flip. If both types tie, either a suitable tree exchange or a bound flip is possible.
Common mistake
(Removing every tied tree arc)
When several tree arcs reach a bound at the same time, exactly one of them leaves. A spanning tree on nodes has arcs, and one arc enters, so removing two would leave too few arcs to connect all nodes. In the first worked example both tree arcs reach zero; removing both would leave the single arc on three nodes. The other tied arcs stay in the tree with flow at a bound, which is exactly a degenerate tree solution.
A zero bottleneck changes the basis without changing the flow or cost. Thus a negative slope alone does not establish that the present flow is suboptimal. A practical finite algorithm needs a precise tie-breaking or anti-cycling rule; this local step description alone does not prove termination. Costs and bounds here are exact, not tolerance-based floating-point tests.
A pivot and a certificate
Worked example 26.1.4
(A negative reduced cost replaces a tree arc)
On nodes , use arcs , , with costs , lower bounds zero and upper bounds three. Balances are . Take the first two arcs as tree and , at cost . With , tree equations give and . The non-tree reduced cost is .
Increase and return along the tree path . Hence , and . The new flow costs , a decrease of . Both tree arcs hit zero. Remove and keep as a zero tree arc. The new tree prices are and the only non-tree reduced cost is .
For any feasible , . All tree reduced costs vanish and while . Therefore . The new flow attains this bound and is optimal. The retained zero tree flow is essential to that particular tree representation.
Worked example 26.1.5
(An upper-bound arc can enter backwards and flip)
Keep the same balances and tree, but use costs , upper bounds and start at , cost . Tree prices give . Since is at its upper bound, decrease it: and the cost slope is . The capacity minimum is . Only the entering arc reaches a bound, so the tree stays in place and flips to its lower bound. The result costs ; the unchanged prices certify optimality because at its lower bound.
Worked example 26.1.6
(A degenerate pivot with step zero)
Use the network of the first example (costs , bounds ) but with all balances zero, so the problem asks for a cheapest circulation. Take the tree and ; both tree arcs are at their lower bound. The prices are again , and at its lower bound, so the slope of the direction is .
The ratio test gives : the tree arcs cannot decrease. Let leave and enter at flow zero. The flow and the cost are unchanged. The new tree has prices and at its lower bound, so the new representation certifies optimality.
Directly, the balance at reads with , so the only feasible flow is zero. The first tree therefore represented an optimal flow while failing the sign test: the failure of the certificate showed a basis change was needed, not that the flow could be improved.
Counterexample mode
Do not omit the entering arc from the ratio test
In the second example, looking only at the tree arcs gives a step of , but that would send from to , violating its lower bound. The entering arc's own remaining interval limits the legal step to .
The sign pattern found at the end of each example is a general certificate.
Theorem 26.1.7
(Reduced-cost optimality certificate)
Let be a feasible tree solution for a spanning tree , with prices satisfying on every tree arc. Suppose every non-tree arc with satisfies if and if . Then minimizes over all feasible flows.
Proof
(Compare any feasible flow arc by arc)
Let be feasible. As in the slope proposition, , and . Hence
Tree terms vanish. For a non-tree arc at its lower bound, and ; at its upper bound, and . A fixed arc has , so it contributes zero regardless of its reduced cost. Every term is nonnegative, so .
The signs are a certificate for the current feasible flow, and the theorem has no converse for a fixed tree: the degenerate example shows an optimal flow whose tree representation fails the test.
Exercises and solutions
Quick check
(In the first example, remove instead of . Find the new prices and check optimality.)
The new tree consists of and .
Solution · Answer
The tree arcs are and . Set ; then , . The non-tree reduced cost is at its lower bound. The same cost is optimal.
Quick check
(In the second example, change the direct arc’s upper bound from to while retaining the flow . Is it still a tree solution with the same tree?)
Compare the non-tree flow with its bounds.
Solution · Answer
No. The direct non-tree flow is strictly between its new bounds and . Although the flow remains feasible, this chosen tree and bound-status assignment no longer represent a tree solution.
Quick check
(A cycle direction has coefficients , current flows and bounds . Find the step and all arcs reaching a bound.)
Use where and where .
Solution · Answer
The three allowable changes are , , and , so . Only the third arc reaches a bound, its upper bound.
Quick check
(Suppose a non-tree arc has and reduced cost . Does it invalidate the price certificate?)
Ask what values this arc can take in a feasible flow.
Solution · Answer
No. Every feasible flow has the same value on this fixed arc, so its contribution to the cost difference is zero. It has no feasible entering direction.