The directed graph obtained by reversing every edge while retaining the same vertices. Scanning adjacency lists constructs the graph transpose in time. A path reverses direction, while mutual reachability and therefore strongly connected components are unchanged.
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 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.
A finite directed graph admits an infinite edge-following walk from exactly when a directed cycle is reachable from . 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 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.
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 time.
Contract each strongly connected component of a directed graph to one vertex, retaining edges between different components. A directed cycle between contracted vertices would make those components mutually reachable, contradicting their distinctness; thus the condensation graph is a Directed acyclic graph. Parallel edges can be retained by algorithms that count them consistently.
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 with constant-cost label comparisons. Store a representative vertex as well when a witness is required.
A positive-integer labeling with and exists exactly when the condensation graph is totally ordered by reachability. Mutual paths force equal labels, and equal labels force mutual paths. Two incomparable components would require strict inequalities in both directions. Conversely number the components in topological order; total comparability forces every earlier component to reach every later one, proving both conditions. Compute the labeling in linear time. Reachability here includes length-zero paths.
A functional graph has exactly one outgoing edge of a graph at every vertex of a graph, representing a function from its vertex of a graph set to itself. In a finite functional graph, each weakly connected component contains one directed cycle, with directed trees feeding into it. Iterating the represented function eventually reaches that directed cycle.
A digraph kernel is an independent set of vertices such that each vertex outside has a directed edge from itself to a vertex in . 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.
In a kernel-perfect directed graph, lists of size at least admit a proper graph coloring. Choose a color and a digraph kernel in the subgraph on vertices whose lists contain . Color that kernel , delete it, and remove from the remaining lists. Every vertex losing a color also loses an outgoing neighbour; hence the inequality persists. Induction on the vertex count finishes the proof.
A digraph kernel is an independent set such that each vertex outside has a directed edge to a vertex in . A directed cycle of even length has a kernel, obtained by taking alternate vertices; a directed triangle has none. The kernel-perfect directed graph property requires existence of such a set in every induced subgraph.
A finite directed graph with layers and edges only to the next layer is a Plünnecke graph when every edge permits both commutation matchings. The successors of inject into the successors of through edges to the original successors; the predecessors of inject into those of through edges from the original predecessors. These conditions formalize interchanging adjacent summands in an additive graph. They persist on channels consisting of paths between prescribed endpoint sets.
A minimum-weight set meeting every bottom-to-top path can be chosen entirely in the endpoint layers. The local step is a three-layer channel whose middle layer is a minimum cut. Replacing middle subsets by their successors or predecessors gives expansion inequalities. Sorting middle vertices by incoming degree and top vertices by their largest predecessor degree gives one edge-count inequality; reversing the graph gives the opposite inequality. Equality forces the bottom layer to have the same weight as the middle cut. Replacing the highest intermediate portion of a minimum cut by this bottom layer repeatedly proves the assertion.
This is the smallest ratio of the size of a -step image to the size of its nonempty starting set in the bottom layer. For a Plünnecke graph, the roots are nonincreasing. The minimum, rather than just the image of the whole layer, is essential.
A cyclic ordering of a directed graph is considered unchanged by rotations or swaps of consecutive nonadjacent vertices. A representative is coherent when every backward edge has a forward directed path from to . Equivalently every edge is on a directed circuit that winds exactly once around the order. The number of backward edges on a circuit is invariant under the allowed changes. Every nontrivial strongly connected directed graph admits such an order.
The cyclic stability is the largest size of an independent set appearing consecutively in a representative of a coherent cyclic order of a digraph. It is at most the ordinary independence number. A set with no forward path between its distinct vertices can be moved into a consecutive block by swapping nonadjacent vertices. Choose a representative minimizing the span of the set; a vertex in a gap can be moved left or right past the block, contradicting minimality unless there are no gaps.
A tournament is an orientation of a complete graph: between each pair of distinct vertices there is exactly one directed edge.
A median order maximizes the number of forward directed edges in a linear ordering of the vertices of a tournament. Every interval inherits a median order. Moving the first vertex of an interval to its end proves that it has at least as many outgoing as incoming edges in that interval; otherwise the move would increase the number of forward edges. Reversing all edges and the order gives the dual assertion for the last vertex.
A graph embedding into an ordered tournament is half-sparse when the displayed inequality holds for every proper final interval . Reserving two extra tournament vertices allows extension at any outward-oriented leaf: the median order of a tournament supplies at least half of the later vertices as outneighbours of the parent's image, while half-sparsity leaves at least one of them unused. Adding one image while extending every old final interval by two preserves the inequality.
A regular tournament has equal outdegree and indegree at every vertex. On vertices, label by residues modulo and direct when . This gives an explicit regular tournament. It contains no outward-oriented star with more than leaves.
A closed directed path whose vertices are distinct except for the common start and endpoint is a directed cycle. In a residual network, augmenting around a directed cycle preserves flow balance. A negative total cost on such a cycle gives an improving displacement for a minimum-cost flow.
A directed cycle in an edge-weighted graph whose total weight is negative. Repeating it makes walk costs arbitrarily small. For a particular shortest-path distance to be affected, the cycle must be reachable from and must have a route to ; an unrelated component does not change that distance.
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.
For a nontrivial strongly connected directed graph, a coherent cyclic order of a digraph and the Dilworth theorem produce a spanning circuit family with at most its independence number circuits. Put a largest consecutive stable block first and duplicate its vertices as sinks. Use forward edges and edges into the sink copies to form an acyclic auxiliary graph. Its reachability order has width equal to the block size. Expand a chain partition to paths, then exchange intersecting path suffixes until the permutation of source-to-sink labels has as many cycles as possible. Paths in the same permutation cycle are disjoint, so identifying copied endpoints produces simple directed circuits. A windmill of directed triangles sharing one vertex shows that the bound is sharp.
A rooted directed graph has a distinguished root. Root-connectedness means each vertex can be reached by a finite directed path from that root. This is directed reachability, rather than connectedness of the underlying undirected graph.
A bisimulation relates the roots of two rooted directed graphs and matches every successor move in either graph with a successor move in the other leading to related vertices. Multiple successors may be related to the same vertex. This local matching is weaker than graph isomorphism.
A relation on states of labelled transition systems matching every transition with a transition of the same label in either direction, with successor states again related. In particular, transitions are matched individually, rather than silently skipped. For CSP processes this preserves CSP traces, CSP stable failures and CSP divergences.
The Spoiler takes one successor step from the current vertex of either rooted directed graph; the Duplicator must take a matching successor step in the other. The Duplicator wins by never failing at a finite stage, including when the Spoiler cannot move. A winning strategy gives a bisimulation by collecting endpoint pairs of all finite plays consistent with it.
Two rooted directed graphs are bisimilar if some bisimulation relates their roots. A root with one terminal successor is bisimilar to a root with two terminal successors, although the graphs have different sizes.
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 cycle cover of a finite directed graph is a collection of vertex-disjoint directed cycles containing every vertex exactly once. Cycle covers of the weighted directed graph with adjacency matrix are the terms in the permanent of a matrix .
This is a vertex cycle cover with the additional requirements of directed cycles and vertex disjointness.
A directed walk is a sequence of vertices in which each consecutive pair is joined by a directed edge in the direction traversed.
A directed graph is strongly connected when every vertex is reachable from every other vertex by a directed path.
The adjacency matrix of a finite directed graph has entry equal to the number of directed edges from vertex to vertex . The entry counts length- directed walks from to , so counts pointed closed directed walks of length .
