Table des matières:
Définition - Que signifie acyclique?
Acyclique est un adjectif utilisé pour décrire un graphique dans lequel il n'y a pas de cycle ou de chemin fermé. En d'autres termes, il s'agit d'un chemin sans sommets répétés (nœuds qui forment le graphique ou liens entre les sommets), à l'exclusion des sommets de début et de fin.
En informatique, il est utilisé dans l'expression «graphe acyclique dirigé» (DAG). Techniquement, DAG est un graphique formé en connectant différents sommets avec des bords qui sont dirigés d'une manière qui ne permet pas de parcourir une séquence qui peut avoir un sommet qui le traverse plus de deux fois; par conséquent, il n'y a pas de chemin fermé.
Techopedia explique Acyclic
Le concept de DAG est utilisé pour concevoir des jeux de mots comme le Scrabble et des applications de recherche scientifique basées sur la biologie et la génétique. Le DAG est également utilisé dans la construction de modèles en mathématiques, en informatique, en circuits électroniques, en opérations de compilation, en calculant des valeurs associées sur des formulaires, etc. Les DAG sont utilisés dans des modèles pour illustrer le flux d'informations à travers un système. DAG est une meilleure alternative aux autres techniques dans les structures de données en fournissant une optimisation de l'utilisation de la mémoire et une amélioration des performances.
Un cycle est un chemin parcouru à travers une séquence de sommets, de telle sorte que les sommets de début et de fin sont le même point. Si un graphique n'a pas de tels cycles, il est alors appelé acyclique. Par exemple, considérons les trois sommets, X, Y et Z liés dans un graphique. Tout en traversant l'un des trois sommets à travers sa structure de différentes manières possibles, si l'on ne peut pas revenir au même sommet de départ sans visiter deux sommets (à l'exclusion du sommet ou du point de départ) deux fois, il s'agit d'un graphe acyclique.
La longueur du cycle le plus court et la circonférence d'un graphique acyclique sont définies comme infinies. Les arbres et les forêts sont des exemples de graphiques acycliques. Un graphe acyclique et non orienté avec deux sommets connectés par un seul chemin est appelé arbre. Un arbre généalogique est un bon exemple du concept d'un arbre acyclique dirigé. Une forêt est un graphe non orienté dont les sous-ensembles sont des arbres.
