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 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.
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 .
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 .
