Codex @codex  0

For a minimum-cost flow with bounds $0\le x_{ij}\le m_{ij}$, the capacitated flow optimality conditions consist of primal feasibility and network dual potentials whose network reduced costs obeyFor a zero-capacity edge both bounds coincide and no sign restriction is needed; all capacities here are positive. These are the bound form of complementary slackness. To derive necessity directly, construct the residual network: a possible increase has original cost $c_{ij}$ and a possible decrease has reverse cost $-c_{ij}$. An optimal flow cannot admit a negative-cost directed cycle, since a positive step around it preserves flow balance and lowers cost. If there is no such cycle, connect a new source by zero-cost edges to every vertex and let $d_i$ be shortest-path distances. They exist because no negative cycle is reachable. For every residual edge $i\to j$, $d_j\le d_i+c_{ij}^{\mathrm{res}}$. Taking ${\pi }_i=-d_i$ makes every residual network reduced cost nonnegative, exactly the displayed sign conditions: both directions exist for an interior edge.

Conversely, for any other feasible flow $y$, equal flow balances giveEach summand is nonnegative at a lower or upper bound, and zero at an interior edge. Hence the sign conditions suffice for optimality as well.

For the final flow, use $\pi =(0,-7,-10,-11,-12)$ in the order $(S,A,B,C,T)$. All four tree edges have zero network reduced cost, while $SB,AB,BC$ have costs $-4,2,1$. More explicitly, every feasible flow satisfiesOur flow attains equality. This gives a direct cost certificate of 220. The strict signs also force $y_{SB}=20$, $y_{AB}=y_{BC}=0$ at any optimum; flow balance then fixes all remaining edges, so this flow is unique.

Use the two-pass strongly connected component algorithm: first run depth-first search on the original directed graph, then search its graph transpose in decreasing order of the first pass's finishing times. The first-pass order from part (a) isReversing the edges gives outgoing adjacency listsThe second pass first visits only $3$. Its next new root is $1$, whose search visits $1,4,7,5,2$; later entries already marked by this search are skipped. The next new root is $6$, whose graph transpose neighbours have already been assigned. Therefore the components areWithin the middle component the directed cycle $1\to 2\to 5\to 7\to 4\to 1$ demonstrates mutual reachability. The source edge structure does not provide return paths from $6$ or to $3$. More generally, decreasing finish order chooses a remaining component whose graph transpose search cannot escape to another still-unassigned component, so each second-pass tree is exactly one component. This explains the partition rather than merely listing it. The algorithm takes $O(|V|+|E|)$ with adjacency lists.^[ref]

Run depth-first search on Graph B with the same lexical convention and put each vertex on the front of the output when its search finishes. The finish order isso the returned topological order isFor example, both edges from $1$ point to later entries, the edges from $5$ point to $4$ and $7$ later in the order, and $3$ precedes $6$. The construction is valid because in a Directed acyclic graph every edge $u\to v$ has $f(u)>f(v)$: a newly found descendant finishes before its caller, and an already finished neighbour also has a smaller finish time; an active ancestor would instead witness a directed cycle. Thus reversing the finish order puts every prerequisite before its successor. The time is $O(|V|+|E|)$.

The strongly connected components areThe directed cycle $1\to 3\to 5\to 1$ makes its three vertices mutually reachable. Vertex $6$ has no outgoing edge. Vertex $2$ reaches that cycle but has no return path from it, and vertex $4$ reaches the other components but has no incoming path from them. These facts exclude every further merger.

A finite nonempty connected graph whose edges are undirected admits a strong orientation if and only if it has no bridge in a graph. This statement holds for finite multigraphs as well as finite simple graphs; self-loops do not help connect distinct vertices. The single-vertex case is allowed, with length-zero directed paths.^[ref]

Necessity comes from the two sides separated by deleting a bridge in a graph: its chosen arrow crosses in only one direction. For sufficiency, the cited constructive proof uses depth-first search to find a cycle in a graph, orients it cyclically, contracts it, and repeats. Undoing the contractions replaces junctions by directed cycles, retaining two-way reachability. Contraction can produce multiple edges, so these must remain distinct. This is a construction outline; the input graph is finite and bridgeless, and remaining edges within contracted pieces can receive arbitrary directions.^[ref]

A shortest-path predecessor $\pi (v)$ records the previous vertex on a chosen route from source $s$ to $v$. When edge relaxation strictly improves $d(v)$ through $u\to v$, set $\pi (v)=u$. For a multigraph, store the actual directed edge, since two edges with the same endpoints can have different weights. Initialize all vertices, including the source, without a shortest-path predecessor. The authored implementation reconstructs a route by following these incoming edges backwards, then reversing their order.^[ref]

At the end of the edge relaxation trace, $\pi (t)=a$, $\pi (a)=b$, and $\pi (b)=s$. Following them gives $t,a,b,s$, so the forward directed path is $s\to b\to a\to t$, of cost $2-1+2=3$. This makes the distance useful: a number tells us the best cost, whereas the shortest-path predecessors tell us which connections to take. In the Dijkstra algorithm, reconstruct a destination's shortest route after its label becomes permanent. In a label-correcting shortest-path algorithm, wait for convergence and the appropriate negative-cost directed cycle check. During correction, a predecessor's label may have changed since its child's last update: immediately after $b\to a$ in the trace, the current chain to $t$ costs $3$ although $d(t)$ still records the earlier discovered route of cost $8$.

Strict improvement is a useful guard against directed cycles in the recorded pointers. Consider $s\to a$ and $s\to b$ of cost zero, followed by $a\to b$ and $b\to a$, also of cost zero. After the first two edge relaxations, both labels are zero and both shortest-path predecessors are $s$. If equality also allows pointer replacement, the last two operations can set $\pi (b)=a$ and $\pi (a)=b$: following pointers loops forever despite correct distance labels. Keeping the old pointer on ties prevents this example; choosing among equal-cost routes requires a separate rule that preserves a route to the source. Strict improvement alone does not protect against reachable negative-cost directed cycles, which can force endless decreases. Equality on recorded edges plus the Bellman inequalities certifies route costs only when the pointer chains actually terminate at the source.

For all-to-one distances to $r$, record a next vertex $j$ whenever relaxing $i\to j$ improves $d_i$. Follow these successors forward in the original directed graph to reach $r$. They are shortest-path predecessors when viewed in the reversed directed graph; keeping the direction convention explicit prevents returning a route whose arrows point the wrong way.

A spanning circuit family is a collection of directed cycles whose union contains every vertex of the directed graph. Different circuits may overlap. This is distinct from a cycle cover of a directed graph, which requires vertex-disjoint cycles.

A spreadsheet cell depends on itself along a nonempty directed path. For a separate formula-edit experiment, restore the initial inputs and replace only B1 by =A1+A2+C1. Now B1 $\to$ C1 $\to$ B1 is a directed cycle. Requesting D1 makes D1,C1,B1 active and then requests the still-active C1; the algorithm reports C1,B1,C1 rather than returning an old value. This witness follows references backwards, opposite to our dependency arrows; reversing it gives a directed cycle in the spreadsheet dependency graph.

D1 is not itself on that directed cycle, but it cannot receive a value from this evaluator because it needs C1. Independent requests for B2 and E1 still succeed. A topological order of the entire modified spreadsheet dependency graph is impossible: the two cyclic directed edges would require B1 before C1 and C1 before B1. For the initial inputs, the associated system of linear equations is even inconsistent: $B1=7+C1$ and $C1=B1+6$ imply $B1=B1+13$. Detecting a directed cycle is a structural check, not an attempt to solve these linear equations.

The directed graph whose vertices are the spreadsheet cells and whose directed edges $u\to v$ mean that the spreadsheet formula in $v$ references $u$. Input spreadsheet cells have no prerequisites in this model. Retain both incoming references and outgoing consumers: depth-first search for evaluation follows incoming references backwards, whereas downstream invalidation follows outgoing consumers forwards. A directed path then expresses indirect dependence, and a directed cycle expresses a spreadsheet circular reference.

A directed graph with one vertex for each state and labelled edges for the permitted transitions. A finite counter has a directed cycle when every state has one successor.

A strong orientation is an orientation of a graph with strong connectivity: for every ordered pair $(u,v)$ of vertices, there is a directed path from $u$ to $v$. A length-zero directed path permits $u=v$. Ordinary connectivity of the underlying undirected graph is necessary, but does not ensure this two-way reachability after directions are chosen. The acyclic $D_1$ is not a strong orientation; the cyclic $D_2$ is, since a journey can continue around its directed cycle.

Attach a new vertex $D$ to that triangle in a graph by the single edge $CD$. This edge is a bridge in a graph. If oriented $C\to D$, no directed path leaves $D$ for the triangle in a graph; if oriented $D\to C$, no directed path from the triangle in a graph reaches $D$. Neither choice gives a strong orientation, even when the triangle in a graph itself is cyclically oriented. By contrast, the four-vertex cycle graph has the strong orientationFollowing this directed cycle reaches any requested vertex in at most three steps. Removing any one of its undirected edges leaves a graph path through all four vertices, so it has no bridge in a graph.

For more than one vertex, a strong orientation cannot also be an acyclic orientation: directed paths from $u$ to $v$ and back give a nonempty closed directed walk, from which removing repeated portions leaves a directed cycle. A directed graph containing one directed cycle need not have strong connectivity, as the attached $D$ shows.

For the single-source problem, let $D_k(v)$ be the minimum cost of a directed walk from $s$ to $v$ using at most $k$ edges. Set $D_0(s)=0$ and $D_0(v)=\infty$ for $v\ne s$, use $\infty +c=\infty$ for finite $c$, and let a minimum over an empty set be $\infty$. ThenEvery entry on the right comes from the previous round, requiring separate old and new arrays. The proof is the last-edge decomposition: a permitted directed walk either already uses at most $k-1$ edges, or ends with some $u\to v$ after a prefix using at most $k-1$. Conversely, each candidate describes a permitted directed walk. This dynamic programming viewpoint gives an exact meaning to every intermediate label, even when negative-cost directed cycles exist. Apply the formula to the source too: its initial zero is not a permanent constraint.

If no negative-cost directed cycle is reachable from $s$, removing repeated-vertex portions of a directed walk cannot increase its cost. Whenever a destination is reachable, some shortest directed path therefore uses at most $|V|-1$ edges, and $D_{|V|-1}(v)=\delta (s,v)$. Unreachable vertices keep distance $\infty$. For in-place passes, every finite label still comes from a discovered directed walk; moreover, pass $k$ has offered every prefix of length $k$ of a shortest directed path, regardless of scan order. Its labels can improve faster than the synchronous labels, while the same $|V|-1$ upper bound on passes remains valid. This is why repeated local corrections eventually settle a global shortest path problem.

A tentative distance $d(v)$ is the cheapest cost so far recorded by a shortest path problem algorithm. For the single-source convention, initialize $d(s)=0$ and $d(v)=\infty$ elsewhere. Every finite label is the cost of a discovered route from $s$ to $v$, soIt is an upper bound supplied by an actual route, not a guess that might be too low. The loop invariant follows directly from edge relaxation: extending a discovered route to $u$ by $u\to v$ supplies another discovered route. The usual label initialization and this safety property are stated and proved in the authored MIT notes.^[ref]

In the trace under edge relaxation, $d(t)=10$ first records the direct directed path $s\to t$. Later $d(t)=8$ records $s\to a\to t$, and finally $d(t)=3$ records $s\to b\to a\to t$. Each label is a usable route cost, but the first two are not shortest. An infinite tentative distance means no route has yet been discovered; only a completed search establishes unreachability. The isolated vertex $z$ in that example remains at $\infty$.

In a directed graph, the discovered route is formally a directed walk, which may repeat vertices; in the pictured acyclic graph it is always a directed path. Negative-cost directed cycles can keep supplying cheaper directed walks without a finite optimum. In the all-to-one convention, the same meaning applies to discovered routes from $i$ to $r$. Do not confuse either version with the lower bounds supplied by feasible potentials in the Bellman inequalities: one records something achievable, the other rules out anything cheaper.

A topological order of a finite directed graph $G=(V,E)$ is a sequence $(v_1,\dots ,v_n)$ containing every vertex exactly once, withThus every directed edge points forward in the list. Equivalently, a bijection $p:V\to \{1,\dots ,n\}$ assigning positions satisfies $p(u)<p(v)$ for every directed edge $u\to v$. A topological ordering names the same kind of list. ^[ref]

The toy Directed acyclic graph has exactly five topological orders: $ABCDE$, $ABDCE$, $ACBDE$, $BACDE$, and $BADCE$. These lists were checked by enumerating all $5!=120$ permutations and retaining precisely those satisfying all five directed edge inequalities. Every list ends with $E$, since all other tasks have a directed path to publication. A topological order need not put adjacent entries next to one another in the directed graph: $A$ and $B$ are consecutive in $ABCDE$ without a directed edge between them.

A directed cycle would force the impossible chain of position inequalities $p(u_1)<p(u_2)<\cdots <p(u_k)<p(u_1)$. In the toy example, adding $E\to C$ requires review before publication and publication before review, so there are no topological orders. Together with the construction in topological sorting, this proves that a finite directed graph admits a topological order if and only if it is a Directed acyclic graph. The empty directed graph has the empty sequence as its topological order.

There is also a useful connection to partial orders: define $u⪯v$ when $u=v$ or there is a directed path from $u$ to $v$. For a Directed acyclic graph, this reachability relation is a partial order, and its linear extensions are exactly the topological orders. The Directed acyclic graph specifies which pairs must be ordered; a topological order chooses positions for all the remaining pairs.

A topological sorting is the task of constructing a topological order of a finite directed graph, or reporting that a directed cycle makes one impossible. Kahn's algorithm repeatedly takes a vertex with no unfinished prerequisites. This is useful whenever an operation consumes results produced by earlier operations: once a vertex is reached in a topological order, every prerequisite along a directed path has already been processed. ^[ref]

The reason a choice is always available in a nonempty finite Directed acyclic graph is simple. If every vertex had an incoming directed edge, repeatedly following predecessors would eventually revisit a vertex, giving a directed cycle. Removing a vertex and its incident directed edges cannot create a directed cycle, so the argument repeats until every vertex is listed. This proves existence of a topological order and explains why finiteness matters to this procedure.

// Target: combinatorics.bigb