Definición - ¿Qué significa acíclico?
Acíclico es un adjetivo que se usa para describir un gráfico en el que no hay ciclo o camino cerrado. En otras palabras, es un camino sin vértices repetidos (nodos que forman el gráfico, o enlaces entre vértices), excluyendo los vértices inicial y final.
En informática, se utiliza en la frase "gráfico acíclico dirigido" (DAG). Técnicamente, DAG es un gráfico formado por la conexión de diferentes vértices con aristas que se dirigen de una manera que no permite navegar por una secuencia que puede tener un vértice que la atraviese más de dos veces; por tanto, no hay camino cerrado.
Techinfo explica Acyclic
El concepto de DAG se utiliza para diseñar juegos de palabras como Scrabble y aplicaciones de investigación científica basadas en biología y genética. DAG también se utiliza en la construcción de modelos en matemáticas, informática, circuitos electrónicos, operaciones de compilación, cálculo de valores relacionados en formularios, etc. Los DAG se utilizan en modelos para ilustrar el flujo de información a través de un sistema. DAG es una mejor alternativa a otras técnicas en estructuras de datos al proporcionar optimización del uso de la memoria y una mejora en el rendimiento.
Un ciclo es un camino atravesado a través de una secuencia de vértices, de modo que tanto el vértice inicial como el final son el mismo punto. Si un gráfico no tiene tales ciclos, entonces se denomina acíclico. Por ejemplo, considere los tres vértices, X, Y y Z vinculados en un gráfico. Mientras se atraviesa desde cualquiera de los tres vértices a través de su estructura de diferentes maneras posibles, si uno no puede regresar al mismo vértice inicial sin visitar ningún vértice (excluyendo el vértice o punto inicial) dos veces, entonces es un gráfico acíclico.
La longitud del ciclo más corto y la circunferencia de un gráfico acíclico se define como infinito. Ejemplos de gráficos acíclicos son Árboles y Bosques. Un gráfico acíclico y no dirigido con dos vértices cualesquiera conectados por una sola ruta se llama árbol. Un árbol genealógico es un buen ejemplo del concepto de árbol acíclico dirigido. Un bosque es un gráfico no dirigido cuyos subconjuntos son árboles.