Clasificación del ciclo

En teoría de grafos , el rango cíclico de un grafo dirigido es una medida de conectividad de digrafos propuesta inicialmente por Eggan y Büchi ( Eggan 1963 ) . Intuitivamente, este concepto mide la proximidad de un digrafo a un grafo acíclico dirigido (DAG), en el sentido de que un DAG tiene rango cíclico cero, mientras que un digrafo completo de orden n con un bucle en cada vértice tiene rango cíclico n . El rango cíclico de un grafo dirigido está estrechamente relacionado con la profundidad de árbol de un grafo no dirigido y con la altura estrella de un lenguaje regular . También se ha utilizado en cálculos con matrices dispersas (véase Bodlaender et al. 1995 ) y en lógica ( Rossman 2008 ) .

Definición

El rango cíclico r ( G ) de un digrafo $G = (V, E)$ se define inductivamente de la siguiente manera:

Si G es acíclico, entonces $r (G) = 0$ .
Si G es fuertemente conexo y E no es vacío, entonces

r(G)=1+\min _ {v\in V}r(Gv),\,

donde

Gv

⁠ es el digrafo resultante de la eliminación del vértice

v

y todas las aristas que comienzan o terminan en

v

.

Si G no está fuertemente conectado, entonces r ( G ) es igual al rango de ciclo máximo entre todos los componentes fuertemente conectados de G .

La profundidad de árbol de un grafo no dirigido tiene una definición muy similar, utilizando conectividad no dirigida y componentes conexas en lugar de conectividad fuerte y componentes fuertemente conexas.

Historia

El rango cíclico fue introducido por Eggan (1963) en el contexto de la altura 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 partir de la década de 1980 y se aplicó a los cálculos de matrices dispersas ( Schreiber 1982 ) .

Ejemplos

El rango de ciclo de un DAG es 0, mientras que un digrafo completo de orden n con un bucle en cada vértice tiene rango de ciclo n . Aparte de estos, se conoce el rango de ciclo de algunos otros digrafos: el camino no dirigido $P_{n}$ de orden n , que posee una relación de arista simétrica y no tiene bucles propios, tiene rango de ciclo. $\lfloor \log n\rfloor$ ( McNaughton 1969 ) . Para la dirección $(m\times n)$ -toro $T_{m,n}$ , es decir, el producto cartesiano de dos circuitos dirigidos de longitudes m y n , tenemos $r(T_{n,n})=n$ y $r(T_{m,n})=\min\{m,n\}+1$ para m ≠ n ( Eggan 1963 , Gruber y Holzer 2008 ).

Cálculo del rango del ciclo

Calcular el rango del ciclo es computacionalmente difícil: Gruber (2012) demuestra que el problema de decisión correspondiente es NP-completo , incluso para digrafos dispersos con un grado de salida máximo de como máximo 2. Por otro lado, el problema es resoluble en tiempo $O(1.9129^{n})$ en digrafos de grado de salida máximo como máximo 2, y en tiempo $O^{*}(2^{n})$ en digrafos generales. Existe un algoritmo de aproximación con razón de aproximación $O((\log n)^{\frac {3}{2}})$ .

Aplicaciones

Altura estelar de los idiomas regulares

La primera aplicación del rango cíclico fue en la teoría de lenguajes formales , para estudiar la altura 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 ₀ , F ), que consta de

un conjunto finito de estados Q
un conjunto finito de símbolos de entrada Σ
un conjunto de aristas etiquetadas δ , denominadas relación de transición : Q × (Σ ∪{ε}) × Q. Aquí ε denota la palabra vacía .
un estado inicial q ₀ ∈ Q
un conjunto de estados F distinguidos como estados de aceptación F ⊆ Q .

Una palabra w ∈ Σ ^* es aceptada por el ε-NFA si existe un camino dirigido desde el estado inicial q ₀ hasta algún estado final en F usando aristas desde δ , de tal manera 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 las propiedades de digrafos de un autómata finito no determinista A con conjunto de estados Q , naturalmente nos referimos al digrafo con conjunto de vértices Q inducido por su relación de transición. Ahora el teorema se enuncia de la siguiente manera.

Teorema de Eggan : La altura de estrella de un lenguaje regular L es igual al rango de ciclo mínimo entre todos los autómatas finitos no deterministas con ε-movimientos que aceptan L.

Las demostraciones de este teorema fueron dadas por Eggan (1963) y, más recientemente, por Sakarovitch (2009) .

Factorización de Cholesky en cálculos con matrices dispersas

Otra aplicación de este concepto reside en los cálculos con matrices dispersas , concretamente en el uso de la disección anidada para calcular la factorización de Cholesky de una matriz (simétrica) en paralelo. Una matriz dispersa dada $(n\times n)$ La matriz M puede interpretarse como la matriz de adyacencia de algún digrafo simétrico G con n vértices, de tal manera que las entradas no nulas de la matriz estén en correspondencia biunívoca con las aristas de G. Si el rango cíclico del digrafo 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 $n$ procesadores ( Dereniowski y Kubale 2004 ) .

Véase también

Clasificación del circuito

Referencias

Bodlaender, Hans L .; Gilbert, John R.; Hafsteinsson, Hjálmtýr; Kloks, Ton (1995), "Aproximación del ancho del árbol, el ancho de la ruta, el tamaño del frente y el árbol de eliminación más corto", Journal of Algorithms , 18 (2): 238– 255, doi : 10.1006/jagm.1995.1009 , Zbl 0818.68118 .
Dereniowski, Dariusz; Kubale, Marek (2004), "Factorización de Cholesky de matrices en paralelo y clasificación de grafos", 5.ª Conferencia Internacional sobre Procesamiento Paralelo y Matemáticas Aplicadas (PDF) , Lecture Notes on Computer Science, vol. 3019, Springer-Verlag, pp. 985–992 , doi : 10.1007/978-3-540-24669-5_127 , ISBN 978-3-540-21946-0, Zbl 1128.68544 , archivado del original (PDF) el 16-07-2011 .
Eggan, Lawrence C. (1963), "Grafos de transición y la altura estelar de eventos regulares", Michigan Mathematical Journal , 10 (4): 385–397 , doi : 10.1307/mmj/1028998975 , Zbl 0173.01504 .
Eisenstat, Stanley C.; Liu, Joseph WH (2005), "La teoría de los árboles de eliminación para matrices asimétricas dispersas", SIAM Journal on Matrix Analysis and Applications , 26 (3): 686–705 , doi : 10.1137/S089547980240563X.
Gruber, Hermann (2012), "Medidas de complejidad de digrafos y aplicaciones en la teoría del lenguaje formal" (PDF) , Matemáticas discretas e informática teórica , 14 ( 2): 189–204.
Gruber, Hermann; Holzer, Markus (2008), "Autómatas finitos, conectividad de digrafos y tamaño de expresiones regulares" (PDF) , Actas del 35.º Coloquio Internacional sobre Autómatas, Lenguajes y Programación , Lecture Notes on Computer Science, vol. 5126, Springer-Verlag, pp. 39–50 , doi : 10.1007/978-3-540-70583-3_4 , ISBN 978-3-540-70582-6.
McNaughton, Robert (1969), "La complejidad de bucles de eventos regulares", Information Sciences , 1 (3): 305– 328, doi : 10.1016/S0020-0255(69)80016-2.
Rossman, Benjamin (2008), "Teoremas de preservación de homomorfismos", Journal of the ACM , 55 (3): Artículo 15, doi : 10.1145/1379759.1379763.
Sakarovitch, Jacques (2009), Elementos de la teoría de autómatas , Cambridge University Press, ISBN 978-0-521-84425-3
Schreiber, Robert (1982), "Una nueva implementación de la eliminación gaussiana dispersa" (PDF) , ACM Transactions on Mathematical Software , 8 (3): 256–276 , doi : 10.1145/356004.356006 , archivado del original (PDF) el 7 de junio de 2011 , consultado el 4 de enero de 2010..