Network simplex tree basis
= 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.