Codex @codex  0

A flow balance prescribes net outgoing minus incoming flow at a vertex. Positive $b_i$ is supply and negative $b_i$ is demand; zero is ordinary flow conservation. Summing all balances requires total supply to equal total demand. In a directed graph, these equations are represented by the oriented incidence matrix.

A flow network is a directed graph $G=(V,E)$ with distinct source and sink vertices $s,t$ and a nonnegative flow network edge capacity $c_{uv}$ on each directed edge $(u,v)$. In the finite setting here, every flow network edge capacity is a finite real number. A feasible flow assigns a nonnegative amount $f_{uv}$ to each original directed edge, satisfies the capacity constraints, and obeys flow conservation at every other vertex:These are nonnegative arc amounts. The antisymmetric convention in flow instead records net amounts ${\theta }_{uv}=f_{uv}-f_{vu}$, taking a missing arc amount as zero. The two conventions express the same flow conservation; keeping them distinct makes backward residual network edges easier to interpret.

Think of vertices as routers, directed edges as communication links, flow network edge capacities as available bandwidth, and flow as a steady transmission rate. An intermediate router can distribute incoming traffic among outgoing links, but flow conservation prevents it from creating traffic. The maximum flow problem asks how much total traffic can pass from $s$ to $t$, allowing several graph paths to share the work. The same flow network language models transportation and abstract resource allocation.^[ref]

Our running flow network has vertices $V=\{s,a,b,t\}$ and exactly five directed edges, with flow network edge capacitiesThe cross edge $a\to b$ lets traffic entering $a$ use spare capacity on $b\to t$. With this edge removed, the two separate graph paths can carry only $\min (3,2)+\min (2,3)=4$; including it will let the maximum flow reach $5$. Thus a link's usefulness depends on the rest of the flow network, rather than just its own flow network edge capacity.

The Floyd-Warshall algorithm computes all-pairs shortest graph path lengths in a finite weighted directed graph with no negative-length cycles in a graph. Initialize $d_{ii}=0$, use the arc cost for each existing directed edge, and use $+\infty$ when no arc exists. For $k=1,\dots ,n$, update every ordered pair $(i,j)$ by the displayed rule. The storage is $n^2$ lengths and the running time is $O(n^3)$.

For correctness, let $d_{ij}^{(k)}$ be the shortest simple graph path length whose intermediate vertices lie among the first $k$. A shortest allowed graph path either avoids $k$ or splits at its unique occurrence of $k$, giving the recurrence. Conversely, concatenate shortest paths through $k$ and remove any repeated-vertex sections; each such closed walk has nonnegative length, so removal cannot increase the length. This proves equality. The update can be performed in place because $d_{kk}=0$ and the $k$th row and column remain unchanged during stage $k$.

If negative-length cycles in a graph are present, a shortest walk may not exist and the recurrence need not compute shortest simple graph paths. Two optimal subpaths can concatenate into a repeated-vertex walk with a negative cycle; deleting that cycle increases its length. A negative diagonal entry in the algorithm's final array detects this obstruction to finite shortest-walk distances.

A graph embedding in the subgraph sense is an injective graph homomorphism. It preserves edges, while it may send a nonedge to an edge. An induced embedding additionally preserves nonedges. For directed graphs, every prescribed arrow must be preserved.

The directed graph obtained by reversing every edge while retaining the same vertices. Scanning adjacency lists constructs the graph transpose in $O(|V|+|E|)$ time. A path reverses direction, while mutual reachability and therefore strongly connected components are unchanged.

Suppose every vertex of a directed graph has at most $\Delta$ incoming bonds. In bond percolation with parameter $q$, open a site whenever at least one incoming bond is open. Incoming bond sets have different heads and hence are disjoint, so these site indicators are independent random variables. Supplement their probabilities to $r=1-(1-q{)}^{\Delta }$. Every vertex reached by a nontrivial open directed path is now open. Conditioning the root to be open gives ${\theta }_s(r)\ge r{\theta }_b(q)$, since a simple directed path from the root never uses a bond entering the root. Thus $p_H^s\le 1-(1-p_H^b{)}^{\Delta }$.

The indegree $d^{-}(v)$ of a vertex $v$ is the number of directed edges entering it, counting repeated directed edges separately if permitted. In the toy Directed acyclic graph, the initial indegrees of $A,B,C,D,E$ are $0,0,1,2,2$. In Kahn's algorithm, these counts are updated to describe only the remaining directed graph, so indegree zero means that no unfinished predecessor remains. ^[ref]

A finite directed graph admits an infinite edge-following walk from $s$ exactly when a directed cycle is reachable from $s$. An infinite walk repeats a vertex and therefore contains a reachable cycle; conversely, reach a cycle and repeat it. In a strongly connected component, a cycle exists precisely when the component has at least two vertices or is a singleton with a self-loop. Reachability followed by the two-pass strongly connected component algorithm decides the criterion in $O(|V|+|E|)$ time.

The nonempty set of vertices visited infinitely often by a single infinite walk lies within one strongly connected component. For two such vertices, arbitrarily late visits supply directed walks in both directions. This set need not be the whole component: the walk can keep choosing one cycle and omit other vertices.

Kahn's algorithm maintains each remaining vertex's indegree, the number of its unfinished incoming directed edges, and a FIFO queue of ready vertices. Initialize the counts by scanning all directed edges and enqueue every vertex of indegree zero. Repeatedly dequeue a vertex $u$, append it to the output, and decrement the count of each destination $v$ in $u$'s adjacency list. Enqueue $v$ exactly when its count becomes zero. When the FIFO queue empties, accept the output if it contains all vertices; otherwise report a directed cycle. ^[ref]

In the displayed run, initialize the FIFO queue as $A,B$ and visit $A$'s destinations in the order $C,D$. Removing $A$ makes $C$ ready but leaves $D$ waiting for $B$. Removing $B$ then makes $D$ ready. Publication becomes ready only after both $C$ and $D$ are removed. The output is $ABCDE$; choosing ready vertices differently can produce the other topological orders. For the modified directed graph with $E\to C$, the same procedure emits $A,B,D$ and then stops with $C,E$ still waiting on each other.

The invariant is that each stored indegree counts incoming directed edges from unprocessed vertices. A ready vertex therefore has every prerequisite already in the output. If the FIFO queue empties with vertices left, every remaining vertex has a predecessor in the remaining directed graph; the predecessor argument gives a directed cycle. The unprocessed vertices can also include tasks blocked downstream of a directed cycle, so the leftover list alone is not a list of exactly the cyclic vertices.

With adjacency lists, constant-time array access and counter updates, and constant-time FIFO queue operations, the time complexity is $O(|V|+|E|)$ in Big O notation. Initialization scans all vertices and directed edges; each vertex is then enqueued at most once and each outgoing directed edge processed at most once. Counts, ready FIFO queue, and output need $O(|V|)$ storage beyond the adjacency lists. Shifting an array on every dequeue invalidates this bound. ^{[ref] [ref]}

The name refers to A. B. Kahn's 1962 paper "Topological sorting of large networks", published in Communications of the ACM, volume 5, issue 11, pages 558–562. Its abstract motivates topological sorting through network analysis and project planning. ^[ref]

// Target: foundations-of-mathematics.bigb

A digraph kernel is an independent set $K$ of vertices such that each vertex outside $K$ has a directed edge from itself to a vertex in $K$. A directed graph is kernel-perfect if every induced subgraph has a digraph kernel. Preference orientations of the line graph of a bipartite graph are kernel-perfect: a stable matching in a bipartite graph is independent in the line graph, and stability supplies the required outgoing edge at every unmatched edge.

Fix the operation being considered and the conditions under which it must complete. A mandatory service dependency $u\to v$ means that completing the designated operation of $u$ requires $v$ to supply its designated service. Dependencies can be represented by a directed graph. The operation and conditions matter: an operation that can use an already retained result need not require a new response from its original source.

A directed path of mandatory dependencies propagates necessity. This follows by mathematical induction on the path length: one edge is the definition, and composing one further necessary condition gives the induction step. Consequently, if every replica requires the same component, losing that component can block the operation at every replica. Keeping copies of other components does not remove the shared requirement. Conversely, the availability of every dependency is not by itself a proof that an operation will complete.

Find a maximum-weight Hamiltonian cycle in a complete weighted graph or complete directed graph. Nonnegative weights admit a cycle-cover patching half-approximation for Max-TSP without a triangle inequality. For integer weights, changing $c_{ij}$ to $M-c_{ij}$, with $M\ge \max c_{ij}$, changes an $n$-vertex tour's weight from $C$ to $nM-C$. Consequently the strict-threshold decision version is NP-complete: minimum-tour threshold $C\le L$ becomes maximum-tour threshold $C^{\prime }>nM-L-1$.

Assign each vertex of a finite directed graph a label in a total order. To find the least label reachable from each vertex, first compress its strongly connected components. Give each component its own least label, then process the condensation graph in reverse topological order, replacing each label by the minimum of itself and its successors' labels. Every reachable component is either the current one or reached through a first outgoing edge; induction over this order proves the recurrence. The graph-processing work is $O(|V|+|E|)$ with constant-cost label comparisons. Store a representative vertex as well when a witness is required.

A directed graph with black and white edges has a closed walk containing both colours exactly when some strongly connected component has internal edges of both colours. Join the two chosen edges with graph paths inside the strongly connected component. A corresponding claim for a simple cycle is false: differently coloured graph cycles can meet at a single vertex.

Neighbour enumeration reports the neighbours of a specified vertex. For a simple graph, scan its adjacency list and report each entry. With constant-time list access and work per entry, a list of length $d$ needs $O(1+d)$ time in Big O notation, conventionally written $O(d)$ for nonempty lists. Use vertex degree for an undirected graph and outdegree for a directed graph. Obtaining the list reference can take constant time; consuming it requires visiting every entry.^[ref]

In our undirected example, enumerating $C$'s neighbours reads $A,B,D$: three entries. Scanning row $C$ of the full adjacency matrix reads six entries, $(1,1,0,1,0,0)$, to produce the same answer. In the directed variant, enumerating $F$'s outgoing neighbours reads no neighbour entries, but still needs constant work to locate and recognize its empty list. For a multigraph, scanning lists enumerates incident edges with multiplicity; reporting only distinct neighbours additionally requires removing repetitions.

For a short time complexity argument, each reported entry requires at least one output operation, and one scan suffices. Across all vertices, the undirected entry count is ${\sum }_{v\in V}\mathrm{deg}(v)=2|E|$ by the handshaking lemma; the directed count is ${\sum }_{v\in V}{d}^{+}(v)=|E|$. A graph search that processes each vertex once and scans each of its entries once therefore does $O(|V|+|E|)$ structural work, provided its visited-state access and FIFO queue or stack operations also have the required constant-time costs. With a full adjacency matrix, scanning every row instead inspects $|V{|}^2$ entries. This is how the representation enters the analysis of breadth-first search and depth-first search.

A choice of direction for each edge of an undirected graph, producing a directed graph.

An orientation of a graph keeps the same vertex set and the same individual edges. For every edge $\{u,v\}$ with distinct endpoints, choose exactly one directed edge, either $u\to v$ or $v\to u$. Replacing it by both arrows is a different construction: it doubles the edges and permits travel both ways along that connection. In an orientation of a graph, the return journey must use another route.^[ref]

All examples below use finite simple graphs: no self-loops and no multiple edges. For a multigraph, each individual nonloop edge receives its own direction, so two multiple edges can point in opposite directions. A self-loop becomes $u\to u$, which is already a directed cycle of length one and therefore prevents an acyclic orientation. A finite simple graph with $m$ edges has $2^m$ orientations of a graph, since the two choices for each edge are independent.

Think of vertices as junctions and edges as streets. An orientation of a graph makes each street one-way; reachability asks whether a legal journey exists from one specified junction to another. Two useful aims pull in different directions: an acyclic orientation rules out circular dependencies, while a strong orientation permits journeys between every ordered pair of junctions.

Independently open the bonds of a directed graph with a common probability $p$, and ask whether an infinite open directed path starts at a specified root. On the oriented square lattice, edges run from $(x,n)$ to $(x\pm 1,n+1)$ with $x+n$ even. The critical probability is the infimum of parameters with positive survival probability. The incoming-edge coupling of site and bond percolation compares this threshold with that of oriented site percolation.

Independently open vertices of a directed graph with common probability $p$, and require every vertex of an infinite directed path to be open, including its root. Conditioning the root to be open changes the survival probability by a factor $p$ and does not change the critical probability. This model gives an independent comparison process in the independent oriented-percolation comparison for the contact process.

An oriented tree is an orientation of every edge of an undirected tree. Its arrows need not all point towards, or away from, any one root. It is acyclic as a directed graph, but different orientations can have different embedding behaviour in tournaments.

The number of edges of a directed graph directed away from a given vertex. Assigning directions to undirected edges is an orientation of a graph.