En el área matemática de la teoría de grafos , se dice que un grafo dirigido es aperiódico si no hay un entero k > 1 que divida la longitud de cada ciclo del grafo. De manera equivalente, una gráfica es aperiódica si el máximo común divisor de las longitudes de sus ciclos es uno; este máximo común divisor para un gráfico de G se llama el periodo de G .
Gráficos que no pueden ser aperiódicos
En cualquier gráfico bipartito dirigido , todos los ciclos tienen una longitud que es divisible por dos. Por lo tanto, ningún gráfico bipartito dirigido puede ser aperiódico. En cualquier gráfico acíclico dirigido , es una verdad vacía que cada k divide todos los ciclos (porque no hay ciclos dirigidos para dividir) por lo que ningún gráfico acíclico dirigido puede ser aperiódico. Y en cualquier gráfico de ciclo dirigido , solo hay un ciclo, por lo que la duración de cada ciclo es divisible por n , la duración de ese ciclo.
Prueba de aperiodicidad
Supongamos que G está fuertemente conectada y que k divide las longitudes de todos los ciclos en G . Considere los resultados de realizar una búsqueda en profundidad de G , comenzando en cualquier vértice, y asignando cada vértice v a un conjunto V i donde i es la longitud (tomada mod k ) de la ruta en el árbol de búsqueda en profundidad primero de la raíz a v . Se puede demostrar ( Jarvis y Shier 1996 ) que esta partición en conjuntos V i tiene la propiedad de que cada borde del gráfico va de un conjunto V i a otro conjunto V ( i + 1) mod k . A la inversa, si existe una partición con esta propiedad para un gráfico fuertemente conectada G , k debe dividir las longitudes de todos los ciclos en G .
Por lo tanto, podemos encontrar el período de un gráfico G fuertemente conectado mediante los siguientes pasos:
- Realice una búsqueda en profundidad de G
- Para cada e en G que conecta un vértice en el nivel i del árbol de búsqueda en profundidad con un vértice en el nivel j , sea k e = j - i - 1.
- Calcule el máximo común divisor del conjunto de números k e .
El gráfico es aperiódico si y solo si el período calculado de esta manera es 1.
Si G no está fuertemente conectado, podemos realizar un cálculo similar en cada componente fuertemente conectado de G , ignorando los bordes que pasan de un componente fuertemente conectado a otro.
Jarvis y Shier describen un algoritmo muy similar que utiliza la búsqueda primero en amplitud en lugar de la búsqueda en profundidad; la ventaja de la búsqueda en profundidad es que el análisis de conectividad sólido se puede incorporar en la misma búsqueda.
Aplicaciones
En un grafo fuertemente conectado , si se define una cadena de Markov en los vértices, en la que la probabilidad de pasar de v a w es distinta de cero si y solo si hay una arista de v a w , entonces esta cadena es aperiódica si y solo si el gráfico es aperiódico. Una cadena de Markov en la que todos los estados son recurrentes tiene un gráfico de transición de estado fuertemente conectado, y la cadena de Markov es aperiódica si y solo si este gráfico es aperiódico. Por tanto, la aperiodicidad de los gráficos es un concepto útil para analizar la aperiodicidad de las cadenas de Markov.
La aperiodicidad también es una condición necesaria importante para resolver el problema de la coloración de la carretera . De acuerdo con la solución de este problema ( Trahtman 2009 ), un grafo dirigido fuertemente conectado en el que todos los vértices tienen el mismo grado externo tiene un color de borde sincronizable si y solo si es aperiódico.
Referencias
- Jarvis, JP; Shier, DR (1996), "Análisis teórico de grafos de cadenas finitas de Markov", en Shier, DR; Wallenius, KT (eds.), Modelado matemático aplicado: un enfoque multidisciplinario (PDF) , CRC Press.
- Trahtman, Avraham N. (2009), "The road coloring problem", Israel Journal of Mathematics , 172 (1): 51–60, arXiv : 0709.0099 , doi : 10.1007 / s11856-009-0062-5.