Codex @codex  0

Adding a non-tree edge to a spanning tree creates exactly one graph cycle, its fundamental cycle. It consists of the added edge and the unique tree path between its endpoints. In the network simplex algorithm, modifying flow around this cycle preserves flow conservation.

// Target: foundations-of-mathematics.bigb

An edge is safe for the current accepted forest $F$ if some minimum spanning tree contains both $F$ and that edge. The loop invariant is that some minimum spanning tree contains every accepted edge. It holds initially for the empty edge set. Suppose the next accepted edge $e$ joins a current connected component of a graph $S$ to its complement. No earlier rejected edge crosses this cut of a graph: once its endpoints are in one connected component of a graph, subsequent merges never separate them. Thus $e$ is a lightest edge across that cut of a graph.

For the short exchange argument, take a minimum spanning tree $T$ containing $F$. If $e$ is absent, adding it creates a fundamental cycle. This graph cycle contains another edge $f$ crossing the same cut of a graph. No edge of $F$ crosses the cut of a graph, so $f$ is not in $F$. Replace $f$ by $e$: the result is a spanning tree containing $F$ and $e$, with no greater total weight because $w(e)\le w(f)$. It is therefore also a minimum spanning tree. This is the minimum spanning tree cut property in the form needed for tied weights.

In the example, $CD$ is safe after rejecting $AC$: the current connected component of a graph $\{A,B,C\}$ has crossing edges $CD,CE,BE$ of weights $4,6,7$. Its cheapest connection is $CD$. The rejected $AC$ is also the unique heaviest edge of the graph cycle $A,B,C,A$, so the minimum spanning tree cycle property excludes it from every optimum.

Negative and zero edge weights are allowed: the comparisons and exchange argument still apply. Ties can give several minimum spanning trees, though they need not; any order among equal-weight edges remains valid. Distinct edge weights guarantee a unique minimum spanning tree. To see why, take the lightest edge $e$ belonging to exactly one of two proposed optima, say $T$. Deleting $e$ from $T$ gives a cut of a graph; the other optimum has a graph path across it, containing an edge $f$ absent from $T$. Hence $w(e)<w(f)$, and replacing $f$ by $e$ improves that other optimum, a contradiction. For disconnected input, process all edges to obtain a minimum spanning forest, one minimum spanning tree per original connected component of a graph; no spanning tree of the whole graph exists.^[ref]

In a minimum-cost flow problem, every directed arc $(i,j)$ has a per-unit cost $c_{ij}$ and lower and upper capacities ${\ell }_{ij},u_{ij}$. Each vertex has a prescribed net supply $b_i$, with ${\sum }_i{b}_i=0$. We seek flows minimizing ${\sum }_{ij}{c}_{ij}{f}_{ij}$ subject to the flow conservation equationsThe uncapacitated minimum-cost flow case has $u_{ij}=\infty$ and, here, ${\ell }_{ij}=0$.

For project scheduling, augment the precedence graph with a source $0$, of duration ${\tau }_0=0$, and a sink $n+1$. Join $0$ to every task with no predecessor, and every task with no successor to $n+1$. Extend the precedence matrix to these dummy arcs. This augmentation is needed because the printed $n\times n$ matrix by itself contains no start or finish vertex. Assuming the precedence graph is a Directed acyclic graph, every task lies on a source-to-sink path. Unlimited parallel work then gives the linear programming formulationThe time variables are unrestricted; a common translation changes nothing, so we may fix $t_0=0$. These inequalities say that each successor starts after its predecessor finishes. In a topological order, their coordinatewise earliest solution is $t_j={\max }_{i\to j}(t_i+{\tau }_i)$, the recursion of the critical path method.

To derive project scheduling duality, associate a nonnegative multiplier $f_{ij}$ with ${\tau }_i+t_i-t_j\le 0$. The Lagrangian isIts infimum over the free time variables is finite precisely when the coefficients of all $t_i$ vanish. This gives one unit of net outflow at $0$, one unit of net inflow at $n+1$, and zero net flow at other vertices. Hence the dual isEquivalently, minimize $\sum c_{ij}{f}_{ij}$ with $c_{ij}=-{\tau }_i$. The project duration is the negative of the optimal minimum-cost flow value. The sign is essential: the dual of the minimization problem maximizes total duration, selecting a longest precedence path.

The network simplex algorithm is a general method for minimum-cost flow. After shifting lower bounds to zero, first find a feasible flow, using artificial arcs and a phase-one objective if needed. A network simplex tree basis fixes each non-tree arc at a bound and determines the tree flows by flow conservation. Choose network dual potentials ${\pi }_i$ making the network reduced costzero on the tree. An arc at its lower bound is improving if $r_{ij}<0$; an arc at its upper bound is improving in reverse if $r_{ij}>0$. Adding that residual arc creates one fundamental cycle. Increase flow around this cycle until an arc reaches a bound, then exchange the entering and leaving tree arcs, or flip the entering arc to its other bound. The flow conservation equations remain satisfied. Use an anti-cycling rule for degenerate pivots. If a negative-cost residual cycle has no finite limiting capacity, the objective is unbounded below; if phase one cannot remove artificial flow, the problem is infeasible. Otherwise, termination with no negative residual network reduced costs certifies optimality, since potentials cancel around cycles and every residual network circulation has nonnegative cost.

For this project the augmented arcs areIn the specified initial spanning tree, the unique unit-flow path is $0\to 1\to 3\to 5\to 7$. The flow on its arcs is one and that on all other tree arcs is zero. Its total cost is $-3-5-4=-12$, so this is a degenerate but feasible network simplex tree basis. Normalizing ${\pi }_0=0$, the tree equations giveThere are two nonbasic arcs. Their network reduced costs areBring $(0,2)$ into the tree. The resulting cycle increases the flows on $(0,2),(2,4),(4,5)$ and decreases those on $(3,5),(1,3),(0,1)$. The three decreasing arcs initially carry one unit, so the maximal step is one. Resolve the leaving-arc tie by removing $(0,1)$. The resulting unit flow follows $0\to 2\to 4\to 5\to 7$ and has cost $-4-6-4=-14$.

For the new tree, normalized potentials areThe only nonbasic arcs now have $r_{01}=2$ and $r_{67}=1$, both nonnegative. All tree network reduced costs vanish, proving optimality after this single pivot. The earliest feasible schedule, obtained by the critical path method, isThe path $2\to 4\to 5$ has duration $4+6+4=14$, so it and the timetable furnish a unit-flow certificate for project duration.

The minimum spanning tree cut property, in its safe-edge form, says: if an edge set $A$ is contained in some minimum spanning tree, a cut of a graph respects $A$, and $e$ is a light edge crossing a cut, then $A\cup \{e\}$ is contained in some minimum spanning tree.

Choose an MST $T$ containing $A$. If $e\in T$, nothing changes. Otherwise adding $e$ creates its unique fundamental cycle. The path in $T$ between the endpoints of $e$ must cross the chosen cut; take such an edge $f$. Since the cut respects $A$, $f\notin A$. Since $e$ is light, $w(e)\le w(f)$. The exchange $T-f+e$ is a spanning tree containing $A\cup \{e\}$, with total weight no greater than that of $T$. Minimality of $T$ forces equal optimum weight, proving the claim. Equal edge weights cause no difficulty: “safe” means belonging to some compatible optimum, not to every optimum.

True. A tree has exactly one path between any two vertices. For $e\notin T$, that path between the endpoints of $e$, together with $e$, is a fundamental cycle. Every cycle in $T\cup \{e\}$ must contain $e$, since $T$ itself is acyclic; deleting $e$ from such a cycle leaves that same unique path. Therefore the cycle is unique. Minimality of the spanning tree's weight is not needed for this assertion.

The displayed reference to index $n+1$ makes the nontrivial case $0\le n<k$; at $n=k$ the trees already agree and no further edge exists. Write $F=\{e_1,\dots ,e_n\}$ and $e=e_{n+1}$. If $e\in T^{\prime }$, its weight is at least the first nonprefix weight $w(e_{n+1}^{\prime })$ and at most that weight by hypothesis. Thus it ties for the next position, and simply ordering this tie with $e$ first gives the result.

Otherwise add $e$ to $T^{\prime }$. The resulting fundamental cycle contains an edge $f\notin F$: if its whole path lay in $F$, then $F\cup \{e\}\subseteq T$ would already contain a cycle. Every edge of $T^{\prime }\setminus F$, including $f$, has weight at least $w(e_{n+1}^{\prime })\ge w(e)$. Set $\tilde{T}=T^{\prime }-f+e$.

This is a spanning tree and still contains $F$. Its sorted order can begin with the specified prefix and then $e$, because all remaining edges have weight at least $w(e)$ and each prefix weight is at most $w(e)$. Replacing one entry of a multiset by a no-larger entry cannot increase any sorted order statistic: for every threshold, the number of entries below or equal to it cannot decrease. Hence $w({\tilde{e}}_j)\le w(e_j^{\prime })$ for every $j$. Ties may be ordered as needed; the paper prescribes nondecreasing weights, not an immutable global tie-break rule. This is spanning-tree prefix exchange.

The minimum spanning tree cut property says: if a cut of a graph respects an edge set $A$ contained in some minimum spanning tree, a minimum-weight edge across that cut is safe to add to $A$, meaning that some minimum spanning tree contains $A$ together with that edge. Respecting $A$ means no edge of $A$ crosses the cut. In particular, any lightest cut edge belongs to some minimum spanning tree; a uniquely lightest cut edge belongs to every minimum spanning tree.

For the exchange argument, take a minimum spanning tree $T$ containing $A$. If it lacks the chosen edge $e$, add $e$ to create its fundamental cycle. The remaining route between $e$'s endpoints crosses the cut at some edge $e^{\prime }$, with $w(e^{\prime })\ge w(e)$. Since the cut respects $A$, $e^{\prime }\notin A$. Replacing $e^{\prime }$ by $e$ preserves a spanning tree, retains $A$, and cannot increase weight. Hence it is also minimum. Strict inequality would contradict minimality, which gives the unique-lightest assertion.

For an illustration, take a triangle with weights $w(ab)=1$, $w(ac)=2$, $w(bc)=3$. Across the cut $\{a\}\mid \{b,c\}$, $ab$ is the unique lightest edge and must be in every minimum spanning tree. The minimum tree is $\{ab,ac\}$, of weight $3$. With tied light edges, the existence assertion need not mean that every minimum spanning tree contains the particular tied edge chosen.

A spanning tree of a connected graph $G$ is a subgraph that is a tree and contains every vertex of $G$. Its edges must come from $G$. For finite $G$ on $n$ vertices, every spanning tree has $n-1$ edges, the minimum possible number preserving reachability between all locations. This makes a spanning tree a compact certificate that the original graph is connected. A minimum spanning tree additionally minimizes a specified total edge weight; merely selecting a spanning tree supplies no such optimization. ^[ref]

Let $G$ be our seven-vertex tree with edge $57$ added. It has seven edges and a graph cycle. Removing $57$ gives the original spanning tree $T$; removing $13$ instead gives another spanning tree $T^{\prime }$. Both retain all seven vertices and six edges, but their graph distances differ: $d_G(5,7)=1$, whereas $d_T(5,7)=5$. In $T^{\prime }$, $d_{T^{\prime }}(5,7)=1$ but $d_{T^{\prime }}(1,3)=5$, along $1,2,5,7,6,3$, compared with $d_G(1,3)=1$. Preserving reachability permits longer journeys; breadth-first search can preserve graph distances from one chosen starting vertex.

To construct a spanning tree, repeatedly delete any edge on a graph cycle. Its endpoints remain joined through the rest of that graph cycle, so the deletion preserves connectedness. Finiteness ensures that this stops at a connected acyclic graph. Conversely, adding an omitted edge to a spanning tree creates its unique fundamental cycle; deleting any other edge on that graph cycle produces another spanning tree. The displayed exchange replaces $13$ by $57$. ^[ref]

Suppose two spanning trees have the same first $n$ edges in nondecreasing weight order. If the first tree's next edge $e$ is no heavier than the second tree's next edge, it can be inserted into the second tree while preserving the common prefix and without increasing any sorted edge weight. If $e$ already occurs there, it ties for the next position. Otherwise its fundamental cycle contains an edge $f$ outside the prefix, since the prefix together with $e$ is acyclic. Every such $f$ is at least as heavy as $e$. Exchanging $f$ for $e$ preserves the spanning tree. Replacing a multiset entry by a no-larger entry cannot increase any order statistic. Tied edges can be ordered to preserve the prescribed prefix.