Английская Википедия:Cycle rank
Шаблон:Short description Шаблон:For Шаблон:Graph connectivity sidebar In graph theory, the cycle rank of a directed graph is a digraph connectivity measure proposed first by Eggan and Büchi Шаблон:Harv. 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 Шаблон:Harvnb) and logic Шаблон:Harv.
Definition
The cycle rank r(G) of a digraph Шаблон:Math is inductively defined as follows:
- If G is acyclic, then Шаблон:Math.
- If G is strongly connected and E is nonempty, then
- <math>r(G) = 1 + \min_{v\in V} r(G-v),\,</math> where Шаблон:Tmath is the digraph resulting from deletion of vertex Шаблон:Mvar and all edges beginning or ending at Шаблон:Mvar.
- If G is not strongly connected, then r(G) is equal to the maximum cycle rank among all strongly connected components of G.
The tree-depth of an undirected graph has a very similar definition, using undirected connectivity and connected components in place of strong connectivity and strongly connected components.
History
Cycle rank was introduced by Шаблон:Harvtxt in the context of star height of regular languages. It was rediscovered by Шаблон:Harv as a generalization of undirected tree-depth, which had been developed beginning in the 1980s and applied to sparse matrix computations Шаблон:Harv.
Examples
The cycle rank of a directed acyclic graph is 0, while a complete digraph of order n with a self-loop at each vertex has cycle rank n. Apart from these, the cycle rank of a few other digraphs is known: the undirected path <math>P_n</math> of order n, which possesses a symmetric edge relation and no self-loops, has cycle rank <math>\lfloor \log n\rfloor</math> Шаблон:Harv. For the directed <math>(m\times n)</math>-torus <math>T_{m,n}</math>, i.e., the cartesian product of two directed circuits of lengths m and n, we have <math>r(T_{n,n}) = n</math> and <math>r(T_{m,n}) = \min\{m,n\} + 1</math> for m ≠ n (Шаблон:Harvnb, Шаблон:Harvnb).
Computing the cycle rank
Computing the cycle rank is computationally hard: Шаблон:Harvtxt proves that the corresponding decision problem is NP-complete, even for sparse digraphs of maximum outdegree at most 2. On the positive side, the problem is solvable in time <math>O(1.9129^n)</math> on digraphs of maximum outdegree at most 2, and in time <math>O^*(2^n)</math> on general digraphs. There is an approximation algorithm with approximation ratio <math>O((\log n)^\frac32)</math>.
Applications
Star height of regular languages
The first application of cycle rank was in formal language theory, for studying the star height of regular languages. Шаблон:Harvtxt 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. Шаблон:Harvtxt. In automata theory, a nondeterministic finite automaton with ε-moves (ε-NFA) is defined as a 5-tuple, (Q, Σ, δ, q0, F), consisting of
- a finite set of states Q
- a finite set of input symbols Σ
- a set of labeled edges δ, referred to as transition relation: Q × (Σ ∪{ε}) × Q. Here ε denotes the empty word.
- an initial state q0 ∈ Q
- a set of states F distinguished as accepting states F ⊆ Q.
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. Now the theorem is stated as follows.
- Eggan's Theorem: The star height of a regular language L equals the minimum cycle rank among all nondeterministic finite automata with ε-moves accepting L.
Proofs of this theorem are given by Шаблон:Harvtxt, and more recently by Шаблон:Harvtxt.
Cholesky factorization in sparse matrix computations
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. A given sparse <math>(n\times n)</math>-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 <math>n</math> processors Шаблон:Harv.
See also
References
- Шаблон:Citation.
- Шаблон:Citation.
- Шаблон:Citation.
- Шаблон:Citation.
- Шаблон:Citation.
- Шаблон:Citation.
- Шаблон:Citation.
- Шаблон:Citation.
- Шаблон:Citation
- Шаблон:Citation.
