En teoría de grafos , el rango cíclico de un grafo dirigido es una medida de conectividad de dígrafo propuesta por primera vez por Eggan y Büchi ( Eggan 1963 ). Intuitivamente, este concepto mide qué tan cerca está un dígrafo de un gráfico 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 gráfico dirigido está estrechamente relacionado con la profundidad del árbol de un gráfico no dirigido y con la altura de estrella de un idioma regular . También ha encontrado uso en cálculos matriciales dispersos (ver Bodlaender et al. 1995 ) y lógica ( Rossman 2008 ).
Definición
El rango de ciclo r ( G ) de un dígrafo G = ( V , E ) se define inductivamente de la siguiente manera:
- Si G es acíclico, entonces r ( G ) = 0 .
- Si G está fuertemente conectado y E no está vacío, entonces
- dónde es el dígrafo resultante de la eliminación del vértice v y todos los bordes que comienzan o terminan en v .
- Si G no está conectado firmemente, a continuación, r ( G ) es igual al rango de ciclo máximo entre todos los componentes fuertemente conectados de G .
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 una fuerte conectividad y componentes fuertemente conectados.
Historia
El rango de ciclo fue introducido por Eggan (1963) en el contexto de la altura de las estrellas de los lenguajes regulares . Fue redescubierto por ( Eisenstat y Liu 2005 ) como una generalización de la profundidad del árbol no dirigida , que se había desarrollado a partir de la década de 1980 y se aplicó a cálculos matriciales dispersos ( Schreiber 1982 ).
Ejemplos de
El rango de ciclo de un gráfico acíclico dirigido es 0, mientras que un dígrafo completo de orden n con un bucle propio en cada vértice tiene un rango de ciclo n . Aparte de estos, se conoce el rango de ciclo de algunos otros dígrafos: el camino no dirigidode orden n , que posee una relación de borde simétrica y no auto-bucles, tiene rango de ciclo( McNaughton 1969 ). Para los dirigidos-toro , Es decir, el producto cartesiano de dos circuitos dirigidos de longitudes m y n , tenemos y para m ≠ n ( Eggan 1963 , Gruber y Holzer 2008 ).
Calcular el 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 dígrafos dispersos de máximo grado superior como máximo 2. En el lado positivo, el problema se puede resolver en el tiempoen dígrafos de máximo grado superior como máximo 2, y en el tiempoen dígrafos generales. Existe un algoritmo de aproximación con relación de aproximación.
Aplicaciones
Altura de estrella de los idiomas regulares
La primera aplicación del rango cíclico fue en la teoría del lenguaje formal , para estudiar la altura de las estrellas de los lenguajes regulares . Eggan (1963) estableció una relación entre las teorías de expresiones regulares, autómatas finitos y grafos dirigidos . En los años siguientes, esta relación se conoció como el teorema de Eggan , cf. Sakarovitch (2009) . En la teoría de los autómatas, un autómata finito no determinista con movimientos ε (ε-NFA) se define como una tupla de 5 , ( Q , Σ, δ , q 0 , F ), que consta de
- un conjunto finito de estados Q
- un conjunto finito de símbolos de entrada Σ
- un conjunto de marcado bordes delta , denominado relación de transición : Q × (Σ ∪ {ε}) x Q . Aquí ε denota la palabra vacía .
- un estado inicial q 0 ∈ Q
- un conjunto de estados F distinguido como estados de aceptación F ⊆ Q .
Una palabra w ∈ Σ * es aceptada por el ε-NFA si existe una ruta dirigida desde el estado inicial q 0 a algún estado final en F usando aristas de δ , de modo que la concatenación de todas las etiquetas visitadas a lo largo de la ruta produce la palabra w . El conjunto de todas las palabras más de Σ * aceptadas por el autómata es el lenguaje aceptado por el autómata A .
Cuando hablamos de las propiedades del dígrafo de un autómata finito no determinista A con el conjunto de estados Q , naturalmente nos dirigimos al dígrafo con el conjunto de vértices Q inducido por su relación de transición. Ahora, el teorema se establece de la siguiente manera.
- Eggan del Teorema : La altura estrella de un lenguaje regular L es igual al rango de ciclo mínimo entre todos los autómatas finitos no determinista con varepsilon mueve aceptar L .
Eggan (1963) y más recientemente Sakarovitch (2009) dan pruebas de este teorema .
Factorización de Cholesky en cálculos matriciales dispersos
Otra aplicación de este concepto radica 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. Un escaso dado-matrix M puede ser interpretado como la matriz de adyacencia de algunos dígrafo simétrica G en n vértices, de tal manera que los no-cero entradas de la matriz están en correspondencia uno-a-uno con los bordes de G . Si el rango de ciclo del dígrafo G es como máximo k , entonces la factorización Cholesky de M puede calcularse en como máximo k pasos en una computadora paralela conprocesadores ( Dereniowski & Kubale 2004 ).
Ver también
- Rango de circuito
Referencias
- Bodlaender, Hans L .; Gilbert, John R .; Hafsteinsson, Hjálmtýr; Kloks, Ton (1995), "Aproximación del ancho del árbol, el ancho del camino, 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[ enlace muerto permanente ] .
- Dereniowski, Dariusz; Kubale, Marek (2004), "Factorización Cholesky de matrices en paralelo y clasificación de gráficos", 5a Conferencia internacional sobre procesamiento paralelo y matemáticas aplicadas (PDF) , Lecture Notes on Computer Science, 3019 , Springer-Verlag, págs. 985–992 , doi : 10.1007 / 978-3-540-24669-5_127 , Zbl 1128.68544 , archivado desde el original (PDF) en 2011-07-16.
- Eggan, Lawrence C. (1963), "Gráficos de transición y la altura de las estrellas 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 los dígrafos 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 dígrafos y tamaño de expresión regular" (PDF) , Proc. 35 ° Coloquio Internacional sobre Autómatas, Lenguajes y Programación , Lecture Notes on Computer Science, 5126 , Springer-Verlag, págs. 39–50, doi : 10.1007 / 978-3-540-70583-3_4.
- McNaughton, Robert (1969), "La complejidad del bucle de los eventos regulares", Ciencias de la información , 1 (3): 305–328, doi : 10.1016 / S0020-0255 (69) 80016-2.
- Rossman, Benjamin (2008), "Teoremas de preservación del homomorfismo", Journal of the ACM , 55 (3): Artículo 15, doi : 10.1145 / 1379759.1379763.
- Sakarovitch, Jacques (2009), Elementos de la teoría de los autómatas , Cambridge University Press, ISBN 0-521-84425-8
- Schreiber, Robert (1982), "Una nueva implementación de eliminación gaussiana dispersa" (PDF) , ACM Transactions on Mathematical Software , 8 (3): 256–276, doi : 10.1145 / 356004.356006 , archivado desde el original (PDF) en 2011 -06-07 , recuperado 2010-01-04.