Índice:
Definição - O que significa Acyclic?
Acíclico é um adjetivo usado para descrever um gráfico 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 links entre vértices), excluindo os vértices inicial e final.
Na ciência da computação, é usado na frase "gráfico acíclico direcionado" (DAG). Tecnicamente, o DAG é um gráfico formado pela conexão de diferentes vértices com arestas que são direcionadas de uma maneira que não permite navegar por uma sequência que pode ter um vértice passando por ele mais de duas vezes; portanto, não há caminho fechado.
Techopedia explica Acyclic
O conceito de DAG é usado para projetar 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, valores relacionados à computação 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 melhoria no desempenho.
Um ciclo é um caminho percorrido através de uma sequência de vértices, de modo que os vértices inicial e final são o mesmo ponto. Se um gráfico não tiver esses ciclos, será chamado de acíclico. Por exemplo, considere os três vértices, X, Y e Z vinculados em um gráfico. Ao percorrer qualquer um dos três vértices através de sua estrutura de diferentes maneiras possíveis, se não for possível retornar ao mesmo vértice inicial sem visitar nenhum vértice (excluindo o vértice ou o ponto inicial) duas vezes, será um gráfico acíclico.
A duração do ciclo mais curto e a circunferência de um gráfico acíclico são definidas como infinito. Exemplos de gráficos acíclicos são Árvores e Florestas. Um gráfico acíclico e não direcionado com dois vértices conectados por apenas um caminho é chamado de árvore. Uma árvore genealógica é um bom exemplo do conceito de uma árvore acíclica direcionada. Uma floresta é um gráfico não direcionado cujos subconjuntos são árvores.
