Tabla de contenido:
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 ni ruta cerrada. En otras palabras, es una ruta sin vértices repetidos (nodos que forman el gráfico o enlaces entre vértices), excluyendo los vértices iniciales y finales.
En informática, se utiliza en la frase "gráfico acíclico dirigido" (DAG). Técnicamente, DAG es un gráfico formado conectando diferentes vértices con bordes que están dirigidos de una manera que no permite navegar a través de una secuencia que puede tener un vértice que lo atraviesa más de dos veces; por lo tanto, no hay camino cerrado.
Techopedia 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 usa en la construcción de modelos en matemáticas, ciencias de la computación, circuitos electrónicos, operaciones de compilación, cálculo de valores relacionados en formularios, etc. Los DAG se usan 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 de uso de memoria y una mejora en el rendimiento.
Un ciclo es un camino atravesado por una secuencia de vértices, de modo que tanto los vértices iniciales como los finales son el mismo punto. Si un gráfico no tiene tales ciclos, se lo denomina acíclico. Por ejemplo, considere los tres vértices, X, Y y Z vinculados en un gráfico. Al atravesar desde cualquiera de los tres vértices a través de su estructura de diferentes formas 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 conectados por un solo camino 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.
