Definição – o que significa acíclico?
Acíclico é um adjetivo usado para descrever um grafo no qual não há ciclo, ou caminho fechado. Em outras palavras, é um caminho sem vértices repetidos (nós que formam o gráfico, ou ligações entre vértices), excluindo os vértices inicial e final.
Em ciência da computação, é usado na frase “gráfico acíclico dirigido” (DAG). Tecnicamente, DAG é um grafo formado pela conexão de diferentes vértices com arestas que são direcionadas de forma que não permite navegar por uma sequência que pode ter um vértice passando por ela mais de duas vezes; portanto, não há caminho fechado.
Definirtec explica Acyclic
O conceito de DAG é usado para criar jogos de palavras como Scrabble e aplicativos de pesquisa científica baseados em biologia e genética. O DAG também é usado na construção de modelos em matemática, ciência da computação, circuitos eletrônicos, operações de compilação, computação de valores relacionados em formulários, etc. Os DAGs são usados em modelos para ilustrar o fluxo de informações através de um sistema. O DAG é uma alternativa melhor a outras técnicas em estruturas de dados, fornecendo otimização do uso de memória e uma melhoria no desempenho.
Um ciclo é um caminho percorrido por uma sequência de vértices, de forma que os vértices inicial e final sejam o mesmo ponto. Se um gráfico não tiver tais ciclos, ele será denominado acíclico. Por exemplo, considere os três vértices, X, Y e Z vinculados em um gráfico. Enquanto atravessa qualquer um dos três vértices através de sua estrutura de diferentes maneiras possíveis, se alguém não puder retornar ao mesmo vértice inicial sem visitar qualquer vértice (excluindo o vértice ou ponto inicial) duas vezes, então é um grafo acíclico.
O comprimento do ciclo mais curto e a circunferência de um gráfico acíclico é definido como infinito. Exemplos de gráficos acíclicos são Árvores e Florestas. Um grafo acíclico e não direcionado com quaisquer dois vértices conectados por apenas um caminho é chamado de árvore. Uma árvore genealógica é um bom exemplo do conceito de árvore acíclica dirigida. Uma floresta é um gráfico não direcionado cujos subconjuntos são árvores.