 Network simplex tree basis

For a connected capacitated minimum-cost flow network, a spanning tree supplies basic flow variables. Every non-tree edge is fixed at its lower or upper bound. Flow balance determines the tree flows; these must also obey capacity constraints. An entering edge creates one cycle, and adjusting flow on that cycle preserves balance until a bound is hit and an edge leaves the tree.