En teoría de grafos , el rango de ciclo de un grafo dirigido es una medida de conectividad de dígrafos propuesta por primera vez por Eggan y Büchi (Eggan 1963). Intuitivamente, este concepto mide qué tan cerca está un dígrafo de un grafo acíclico dirigido (DAG), en el sentido de que un DAG tiene rango de ciclo cero, mientras que un dígrafo completo de orden n con un bucle propio en cada vértice tiene rango de ciclo n . El rango de ciclo de un grafo dirigido está estrechamente relacionado con la profundidad de árbol de un grafo no dirigido y con la altura de estrella de un lenguaje regular . También se ha utilizado en cálculos de matrices dispersas (ver Bodlaender et al. 1995) y lógica (Rossman 2008).
El rango de ciclo r ( G ) de un dígrafo G = ( V , E ) se define inductivamente de la siguiente manera:
La profundidad de árbol de un gráfico no dirigido tiene una definición muy similar, utilizando conectividad no dirigida y componentes conectados en lugar de conectividad fuerte y componentes fuertemente conectados.
Eggan (1963) introdujo el rango de ciclo en el contexto de la altura de estrella de los lenguajes regulares . Fue redescubierto por (Eisenstat y Liu 2005) como una generalización de la profundidad de árbol no dirigida , que se había desarrollado a principios de la década de 1980 y se había aplicado a los cálculos de matrices dispersas (Schreiber 1982).
El rango de ciclo de un grafo acíclico dirigido es 0, mientras que un dígrafo completo de orden n con un bucle propio en cada vértice tiene rango de ciclo n . Aparte de estos, se conoce el rango de ciclo de algunos otros dígrafos: el camino no dirigido de orden n , que posee una relación de aristas simétrica y no tiene bucles propios, tiene rango de ciclo (McNaughton 1969). Para el -toro dirigido , es decir, el producto cartesiano de dos circuitos dirigidos de longitudes m y n , tenemos y para m ≠ n (Eggan 1963, Gruber & Holzer 2008).
Calcular el rango del ciclo es computacionalmente difícil: Gruber (2012) demuestra que el problema de decisión correspondiente es NP-completo , incluso para dígrafos dispersos de grado de salida máximo como máximo 2. En el lado positivo, el problema es solucionable en el tiempo en dígrafos de grado de salida máximo como máximo 2, y en el tiempo en dígrafos generales. Existe un algoritmo de aproximación con razón de aproximación .
La primera aplicación del rango de ciclo fue en la teoría de lenguajes formales , para estudiar la altura de estrella de los lenguajes regulares . Eggan (1963) estableció una relación entre las teorías de expresiones regulares, autómatas finitos y grafos dirigidos . En años posteriores, esta relación se conoció como el teorema de Eggan , cf. Sakarovitch (2009). En la teoría de autómatas, un autómata finito no determinista con ε-movimientos (ε-NFA) se define como una 5-tupla , ( Q , Σ, δ , q 0 , F ), que consiste en
Una palabra w ∈ Σ * es aceptada por el ε-NFA si existe un camino dirigido desde el estado inicial q 0 hasta algún estado final en F usando aristas de δ , de modo que la concatenación de todas las etiquetas visitadas a lo largo del camino produce la palabra w . El conjunto de todas las palabras sobre Σ * aceptadas por el autómata es el lenguaje aceptado por el autómata A .
Cuando hablamos de propiedades digráficas de un autómata finito no determinista A con conjunto de estados Q , naturalmente nos referimos al dígrafo con conjunto de vértices Q inducido por su relación de transición. Ahora el teorema se enuncia de la siguiente manera.
Las pruebas de este teorema las dan Eggan (1963) y, más recientemente, Sakarovitch (2009).
Otra aplicación de este concepto se encuentra en los cálculos de matrices dispersas , es decir, para utilizar la disección anidada para calcular la factorización de Cholesky de una matriz (simétrica) en paralelo. Una matriz dispersa dada M puede interpretarse como la matriz de adyacencia de algún dígrafo simétrico G en n vértices, de manera tal que las entradas no nulas de la matriz estén en correspondencia biunívoca con las aristas de G. Si el rango de ciclo del dígrafo G es como máximo k , entonces la factorización de Cholesky de M puede calcularse en como máximo k pasos en una computadora paralela con procesadores (Dereniowski y Kubale 2004).
