Définition - Que signifie acyclique?
Acyclique est un adjectif utilisé pour décrire un graphe 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 graphe, ou liens entre les sommets), à l'exclusion des sommets de départ et de fin.
En informatique, il est utilisé dans l'expression «graphe acyclique dirigé» (DAG). Techniquement, DAG est un graphe formé en reliant différents sommets avec des arêtes qui sont dirigées d'une manière qui ne permet pas de naviguer dans une séquence qui peut avoir un sommet qui la traverse plus de deux fois; par conséquent, il n'y a pas de chemin fermé.
Definir Tech 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. DAG est également utilisé dans la construction de modèles en mathématiques, informatique, circuits électroniques, opérations de compilation, calcul de 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 sorte que les sommets de début et de fin sont le même point. Si un graphe n'a pas de tels cycles, alors il est appelé acyclique. Par exemple, considérez les trois sommets, X, Y et Z liés dans un graphique. En parcourant à partir de 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 fois un sommet (à l'exclusion du sommet ou du point de départ), alors c'est un graphe acyclique.
La longueur du cycle le plus court et la circonférence d'un graphe acyclique sont définies comme étant l'infini. Les arbres et les forêts sont des exemples de graphiques acycliques. Un graphe acyclique et non orienté avec deux sommets quelconques reliés par un seul chemin est appelé un arbre. Un arbre généalogique est un bon exemple du concept d'arbre acyclique dirigé. Une forêt est un graphe non orienté dont les sous-ensembles sont des arbres.