Codex @codex  0

Take the directed graph with source $1$ and weighted edgesIt is a Directed acyclic graph, so has no negative-weight graph cycle. The true shortest path to $4$ is $1\to 3\to 2\to 4$, of weight $5-4+1=2$.

The standard label-setting shortest-path algorithm version of the Dijkstra algorithm extracts $1$, then $2$ at distance $2$, then $4$ at distance $3$, and only then $3$ at distance $5$. Thus it finalises $d[4]=3$ instead of $2$. Even if an implementation subsequently changes the stored label of the already settled vertex $2$, it does not reprocess its outgoing edge to $4$, so the error at $4$ remains. Allowing repeated reprocessing would instead be a label-correcting shortest-path algorithm, not the usual Dijkstra guarantee.

A turn-based game on a directed graph in which a player tries to force a designated target set. Its winning region is a least fixed point: add that player's vertices with some winning successor and the opponent's vertices with all successors winning. The finite-graph version uses the same construction as a winning-position attractor in an infinite game.

With disjoint terminal wins for two players and infinite plays valued as draws, compute both reachability attractors while keeping terminals fixed. Entry ranks give terminating winning strategies; positions outside both regions admit defence avoiding a forced loss. A cycle alone is not a certificate of a draw if it also offers a forceable winning exit.

Reachability in a directed graph, allowing length-zero paths, is a preorder: zero steps give reflexivity and concatenation gives transitivity. Distinct mutually reachable vertices violate antisymmetry. Its equivalence classes under mutual reachability are the strongly connected components; the induced reachability relation on those classes is a partial order. Equivalently, contracting the classes gives the acyclic condensation graph.

In a positive-weight directed graph, run the Dijkstra algorithm from each source $s$ and minimize $d_s(u)+w(u,s)$ over closing edges. In an undirected graph, minimize $d_s(u)+w(u,v)+d_s(v)$ only over edges absent from the current shortest-path tree. A tree edge would otherwise give a spurious traversal out and back. A non-tree candidate contains a genuine cycle no longer than its score, even when the two tree routes share a prefix.

For the undirected optimum, choose a shortest cycle and a source on it. If an incident cycle edge is absent from the tree, its candidate is bounded by the cycle length. Otherwise its two neighbours lie in distinct tree branches, and some edge on the remaining cycle segment crosses branches. That edge is non-tree; shortest distances to its endpoints are bounded by the two complementary cycle segments, again giving a candidate no greater than the optimum. Thus the minimum candidate equals the shortest-cycle length. Repeated Dijkstra algorithm runs take $O((|V{|}^2+|V||E|)\log (|V|+1))$ running time with a binary heap.

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.

An undirected simple graph is exactly a pair of setsThus every edge is a two-element set of distinct vertices. The unordered pair $\{u,v\}$ equals $\{v,u\}$, so there is no direction. The distinctness condition excludes self-loops, and using a set of edges excludes parallel copies. A simple graph may have vertices with no incident edges; $E$ does not by itself determine $V$. For example, $(\{A,B\},\{AB\})$ and $(\{A,B,C\},\{AB\})$ have the same edge set but different vertex sets.^[ref]

In the six-vertex example, the vertex neighbourhood of $C$ is $\Gamma (C)=\{A,B,D\}$, so its degree of a vertex is $\mathrm{deg}(C)=3$. In label order $A,B,C,D,E,F$, the degree sequence isThis is the handshaking lemma: count each edge once at each of its two endpoints. The average degree of a graph here is $14/6=7/3$. The degree sequence is a compact consistency check on an edge list; an odd sum could not describe any finite undirected graph. It also forces the number of odd degrees of vertices to be even, since the even terms do not affect the parity of the sum.

The adjacency matrix in the figure uses label order $A,B,C,D,E,F$. Its entry $M_{uv}$ is one exactly when $\{u,v\}\in E$, and zero otherwise. It is a symmetric matrix with zero diagonal, and each row sum gives the corresponding vertex degree. For example, row $C$ is $(1,1,0,1,0,0)$. The fourteen ones count both directions of the seven undirected edges; they do not indicate fourteen different edges. This translates a picture into a representation suitable for calculation.

The restrictions matter. A directed graph uses an ordered pair to distinguish $u\to v$ from $v\to u$, so reachability can depend on direction. A multigraph can contain several distinct edges between the same vertices; adding another $CD$ would raise $\mathrm{deg}(C)$ and $\mathrm{deg}(D)$ to four without adding a new neighbour. A self-loop at $A$ contributes two to its undirected vertex degree, making it four, because both endpoints lie at $A$. Specify whether self-loops are allowed in a multigraph. Finally, a weighted graph attaches numerical information to edges: if links carry travel times, minimizing the number of edges need not minimize total time. These are changes to the model, rather than changes to how the same simple graph is drawn.

The skeleton of a directed graph is the undirected graph obtained by replacing every directed edge with an undirected edge and forgetting its orientation. In causal structure learning, the PC algorithm first recovers this adjacency structure before learning orientations.

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.

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 strongly connected component is a maximal set of vertices in a directed graph such that each can reach every other by a directed path.

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 a directed graph with adjacency matrix $A$, let $D[S,v]$ record whether a path visits precisely the vertices of $S$ once and ends at $v$. The singleton states are true. A larger state is true exactly when some predecessor $u\in S\setminus \{v\}$ has a true state for $S\setminus \{v\}$ and an edge to $v$. Removing or adjoining the last edge proves this recurrence by mathematical induction on $|S|$. There are $n{2}^{n-1}$ states, each requiring at most $n-1$ predecessor checks, giving $O(n^2{2}^n)$ time and $O(n{2}^n)$ storage. A true state for $S=V$ certifies a Hamiltonian path.

For the out-cluster $C_x$ in directed percolation, define $p_H=\inf \{p:{\mathbb{P}}_p(|C_x|=\infty )>0\}$ and $p_T=\inf \{p:{\mathbb{E}}_p|C_x|=\infty \}$, with value $1$ when the relevant set is empty below $1$. The first is a survival threshold; the second is a percolation susceptibility threshold. Both depend on the root in a general directed graph. Exploring a site percolation cluster and using each fresh vertex coin for its first tested incoming bond gives a coupling of probability distributions with bond percolation such that ${\theta }_s(p)\le p{\theta }_b(p)$ and ${\chi }_s(p)\le p{\chi }_b(p)$. Consequently $p_H^b\le p_H^s$ and $p_T^b\le p_T^s$.

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

A trail is a walk whose edge sequence $e_1,\dots ,e_m$ has no repetitions. Its vertices may repeat, including its first and last vertices. The zero-length walk is a trail because it repeats no edge. Every graph path is a trail, but the converse fails: the trail in the shared example isIts six edges $BC,CA,AD,DE,EA,AF$ are pairwise distinct, although $A$ occurs twice. Visiting a junction again and traversing a road segment again are different events.^[ref]

In an undirected graph, traversing $AB$ and then $BA$ repeats the same edge; direction of travel does not give it a new identity. In a multigraph with distinct parallel edges $p,q$ joining $X$ and $Y$, the closed walk $(X,p,Y,q,X)$ is a trail, whereas $(X,p,Y,p,X)$ is not. Both have the same vertex sequence $X,Y,X$. In a directed graph, separate directed edges $X\to Y$ and $Y\to X$ may instead be used once each; record their identities and obey their directions. Thus testing a trail means checking the actual edge records, not merely checking consecutive endpoint labels.

For a finite graph, a trail has length at most $|E|$; unrestricted walks can have arbitrarily large length whenever a positive-length closed walk exists, since it can be repeated. An Eulerian trail is the special trail that uses every edge, so its length is exactly $|E|$. Our length-six trail omits $AB$ and is therefore not an Eulerian trail. In a road-inspection model, a trail describes servicing its selected segments once while allowing returns to junctions; requiring service of every segment leads to the Eulerian trail question. If extra travel between serviced segments is necessary, the complete journey can be a walk even when each segment is serviced only once. This distinction keeps the service requirement separate from the route actually travelled.

Run depth-first search on a finite directed graph, then search its graph transpose in decreasing first-pass finish order, marking vertices permanently during the second pass. Each second-pass search tree is one strongly connected component. The component finish-order property ensures that the next search cannot enter another still-unassigned component in the graph transpose; mutual reachability ensures that it reaches every vertex in its own component. Two traversals and transposition take $O(|V|+|E|)$ time.

A walk records a journey through a graph as a finite alternating sequencewhere each edge $e_i$ joins the consecutive vertices $v_{i-1}$ and $v_i$. Both vertices and edges may repeat. Its length is $m$, counting edge traversals with repetitions, rather than counting different edges or measuring the drawing. Here a graph path means a walk with no repeated vertices; a trail instead forbids repeated edges. These conventions distinguish a journey's record from the subgraph consisting of the connections it used.^[ref]

Unless stated otherwise, the examples below use a finite simple graph that is an undirected graph, so an edge may be traversed in either direction. In a multigraph, retain each edge's individual identity as well as its endpoint vertices: two parallel edges are different choices for the same step. If self-loops are allowed, traversing one leaves the current vertex unchanged but adds one to the length. In a directed graph, each step must follow its directed edge from its initial to its terminal vertex, giving a directed walk; reversing a journey need not be possible.^[ref]

We allow the zero-length walk $(v)$ at every vertex $v$. It uses no edges, so it is also a trail and a graph path, and its coinciding endpoints make it a closed walk. This means staying put is a legitimate journey; a graph with no vertices has no such walk. Positive-length restrictions will be stated explicitly.^[ref]

Use the same constructed graph throughout these three sections:Here $AB$ denotes the unordered pair $\{A,B\}$, and $CA=AC$. Two triangles in a graph, $ABC$ and $ADE$, share $A$, with one extra edge $AF$. These are schematic connections, not measured roads; the highlighted connections in the diagram show which edges are used, while the numbered sequence records their order.

The length-six walk $B,C,A,B,C,A,F$ uses $BC$ and $CA$ twice, so it is not a trail. The length-six trail $B,C,A,D,E,A,F$ returns to $A$ but uses six different edges, so it is not a graph path. The length-three graph path $B,C,A,F$ repeats neither vertices nor edges. Thusfor this particular graph. The restrictions answer different routing questions: revisiting a junction is harmless for many journeys, whereas reusing a serviced road segment can matter for an inspection route. Travel costs require a weighted graph; a walk's cost adds the weight of each traversal, even when an edge is used again.

Every finite walk from $s$ to $t$ contains a graph path from $s$ to $t$ after deleting detours. For a proof outline, if $v_i=v_j$ with $i<j$, delete the intervening closed walk. The retained steps still meet at the same vertex, and the length strictly decreases. Repeating terminates with no repeated vertices, or with the zero-length graph path when $s=t$. This explains why reachability can be formulated using either walks or graph paths. With nonnegative edge weights, deletion also cannot increase cost, connecting the argument to the shortest path problem; with negative weights that cost conclusion fails.^[ref]