Un graphe acyclique dirigé (DAG) est un type de graphe dans lequel il est impossible de revenir au même nœud en parcourant les arêtes.

En théorie des graphes, un graphe est une structure composée de nœuds reliés par des arêtes. Vous pouvez considérer les nœuds comme des points et les bords comme des lignes tracées d’un point à l’autre.

‘Dirigé’ signifie que les arêtes du graphique ne se déplacent que dans une direction, où les futures arêtes dépendent des précédentes. Par exemple, si vous deviez représenter graphiquement le processus de cuisson et de consommation d’un repas composé de riz et de poulet, les tâches impliquées devraient être classées topologiquement (ou triées topologiquement). Avant de pouvoir manger le repas, vous devez préparer la nourriture, de sorte que le bord serait nécessairement dirigé de la préparation à la nourriture. Mais avant de pouvoir préparer la nourriture, vous devez acheter les ingrédients, donc encore une fois le bord doit passer de l’événement précédent à l’événement ultérieur. En supposant que le riz ait été acheté dans un événement séparé du poulet, il y aurait deux bords distincts pour les événements d’épicerie qui ne sont pas liés les uns aux autres, mais qui convergent à l’événement de préparation de la nourriture.

‘Acyclique’ signifie qu’il est impossible de commencer à un point du graphique et d’y revenir en suivant les arêtes. Alors qu’un cycle revient à son point de départ d’origine comme un cercle, un graphe acyclique continue de se déplacer dans une direction linéaire et ne revient jamais au point de départ. Pour continuer avec l’exemple précédent de dîner au poulet et au riz, vous ne pouvez pas passer du graphique de l’achat du riz à la préparation de la nourriture à l’achat du poulet, car cela nécessiterait de reculer sur le graphique. Il est impossible de préparer le poulet si vous ne l’avez pas encore acheté.

Les DAG sont des représentations graphiques probabilistes de réseaux bayésiens qui visent à modéliser la dépendance conditionnelle (par exemple, manger le repas dépend de le préparer en premier).

Plusieurs cryptomonnaies utilisent des DAG plutôt que des structures de données blockchain afin de traiter et de valider les transactions. Avec les chaînes de blocs, tous les nœuds d’un réseau reposent sur la même blockchain unique, chaque bloc faisant référence à celui qui l’a précédé. Un inconvénient possible de cette structure est qu’elle limite le débit de transactions du réseau, car il n’y a que tant de transactions pouvant tenir dans un seul bloc et autant de blocs pouvant être validés dans un temps donné. Dans un réseau DAG, les transactions sont directement liées les unes aux autres plutôt que regroupées en blocs, et les transactions peuvent être traitées simultanément avec d’autres. Le résultat est un goulot d’étranglement réduit sur le débit des transactions.