Cycle rank
In graph theory, the cycle rank of a directed graph is a digraph connectivity measure proposed first by Eggan and Büchi (Eggan 1963).
Intuitively, this concept measures how close a digraph is to a directed acyclic graph (DAG), in the sense that a DAG has cycle rank zero, while a complete digraph of order n with a self-loop at each vertex has cycle rank n. The cycle rank of a directed graph is closely related to the tree-depth of an undirected graph and to the star height of a regular language.
It has also found use in sparse matrix computations (see Bodlaender et al. 1995) and logic (Rossman 2008).
Cycle rank was introduced by Eggan (1963) in the context of star height of regular languages.
It was rediscovered by (Eisenstat & Liu 2005) as a generalization of undirected tree-depth, which had been developed beginning in the 1980s and applied to sparse matrix computations (Schreiber 1982).
of order n, which possesses a symmetric edge relation and no self-loops, has cycle rank
Computing the cycle rank is computationally hard: Gruber (2012) proves that the corresponding decision problem is NP-complete, even for sparse digraphs of maximum outdegree at most 2.
Eggan (1963) established a relation between the theories of regular expressions, finite automata, and of directed graphs.
In subsequent years, this relation became known as Eggan's theorem, cf.
In automata theory, a nondeterministic finite automaton with ε-moves (ε-NFA) is defined as a 5-tuple, (Q, Σ, δ, q0, F), consisting of A word w ∈ Σ* is accepted by the ε-NFA if there exists a directed path from the initial state q0 to some final state in F using edges from δ, such that the concatenation of all labels visited along the path yields the word w. The set of all words over Σ* accepted by the automaton is the language accepted by the automaton A.
When speaking of digraph properties of a nondeterministic finite automaton A with state set Q, we naturally address the digraph with vertex set Q induced by its transition relation.
Another application of this concept lies in sparse matrix computations, namely for using nested dissection to compute the Cholesky factorization of a (symmetric) matrix in parallel.
-matrix M may be interpreted as the adjacency matrix of some symmetric digraph G on n vertices, in a way such that the non-zero entries of the matrix are in one-to-one correspondence with the edges of G. If the cycle rank of the digraph G is at most k, then the Cholesky factorization of M can be computed in at most k steps on a parallel computer with
The fourth has cycle rank 2; it is strongly connected , and it takes the removal of 1 vertex to make it not so. After that, each strongly connected component remaining has cycle rank 1, so the 1 vertex removed initially plus the max rank among the components. The fifth looks similar to the fourth, but since it is not strongly connected, and the maximum cycle rank of its components is 1, it has the same cycle rank as the second and third graphs.