Definition Was ist ein Directed Acyclic Graph (DAG)?

Ein Directed Acyclic Graph (DAG) ist eine abstrakte Struktur, die aus Knoten und Kanten besteht. Die Kanten bilden die Verbindungen zwischen den Knoten und besitzen eine Richtung. Schleifen sind in der Struktur ausgeschlossen. Folgt man der Richtung der Kanten, gelangt man von einem Startpunkt (Startknoten) zu einem Zielknoten und niemals zurück an den Ausgangsknoten. Es entsteht eine topologische Ordnung. Mit DAGs lassen sich beispielsweise kausale Zusammenhänge gut darstellen.

Anbieter zum Thema

Fujitsu Technology Solutions GmbH

Disy Informationssysteme GmbH

Fivetran Germany GmbH

Die deutsche Übersetzung von Directed Acyclic Graph, abgekürzt DAG, lautet gerichteter azyklischer Graph. Es handelt sich um eine besondere Form eines Graphen, basierend auf der Graphentheorie. Er ist dadurch gekennzeichnet, dass die Verbindungen zwischen den Knoten, als Kanten bezeichnet, eine Richtung besitzen und Schleifen ausgeschlossen sind. Folgt man den gerichteten Kanten, gelangt man niemals an den Ausgangspunkt zurück. Grafisch lässt sich der DAG mit über Linien und Pfeilrichtungen verbundene Punkte darstellen.

Gerichtete azyklische Graphen kommen in zahlreichen Bereichen zum Einsatz und sind Bestandteil in vielen mathematischen oder computerwissenschaftlichen Anwendungen und Konzepten. Aufgrund der gerichteten Kanten und der schleifenfreien Struktur eignen sie sich gut zur Abbildung von kausalen Zusammenhängen. Mithilfe der Graphen lassen sich beispielsweise Routen in Computernetzwerken finden, darstellen und optimieren, Abstammungsverhältnisse visualisieren oder Prozessabläufe beschreiben. Wie Blockchains zählen auch die gerichteten azyklischen Graphen zu den sogenannten Distributed-Ledger-Technologien (DLTs). Sie sind als Alternative zur Blockchain-Technologie für die Registrierung der Transaktionen von Kryptowährungen einsetzbar.

Die Graphentheorie und typische Merkmale eines gerichteten azyklischen Graphen

Bevor näher auf den gerichteten azyklischen Graphen eingegangen wird, zunächst einige grundlegenden Informationen zur Graphentheorie. Allgemein handelt es sich bei einem Graphen um eine abstrakte Struktur von miteinander verknüpften Objekten. Die Objekte werden als Knoten und die Verbindungen zwischen den Objekten als Kanten bezeichnet. Je nach Art des Graphen können die Kanten gerichtet oder ungerichtet sein. Visualisieren lassen sich die Graphen mit Punkten, die mit Linien, mit oder ohne Pfeilrichtung miteinander verbunden sind.

Die besonderen Merkmale eins gerichteten azyklischen Graphen sind, dass alle Verbindungen (Kanten) zwischen den Knoten eine Richtung besitzen und dass Schleifen grundsätzlich ausgeschlossen sind. Startet man an einem bestimmten Knoten, gelangt man niemals an den Ausgangsknoten zurück. Mithilfe der gerichteten Verbindungen lassen sich beispielsweise kausale Zusammenhänge darstellen. Die Wurzel eines DAGs bildet der sogenannte Stammknoten. Von ihm gehen die Verbindungen aus. Er besitzt keine Vorgängerknoten. Knoten, an denen Verbindungen enden und die selbst keine ausgehenden Verbindungen mehr haben, werden als Blattknoten oder Blätter bezeichnet. Eine alternative Bezeichnung für den DAG-Algorithmus ist topologische Ordnung. Jeder Knoten einer topologischen Sortierung befindet sich in einer bestimmten Reihenfolge.

Unterschiede zur Blockchain

Der Directed Acyclic Graph und die Blockchain sind beides sogenannte Distributed-Ledger-Technologien (DLTs). Obwohl sie für ähnliche Anwendungen einsetzbar sind, lassen sich DAGs und Blockchains deutlich voneinander unterscheiden. Beide Technologien registrieren und verwalten Transaktionsdaten oder andere Daten in einem verteilten digitalen Ledger (Register oder Konto). Sie sind beispielsweise für die Registrierung der Transaktionen von Kryptowährungen einsetzbar. Während Blockchains die Daten oder Transaktionen bündeln, auf Blöcke verteilen und sie in einer Kette aus Blöcken organisieren, sind sie bei den DAGs in Graphen organisiert. Ein Directed Acyclic Graph bildet keine in Ketten verbundene Blöcke von Transaktionen und benötigt kein Mining für die Bestätigung von Transaktionen. Vorteile der DAGs sind die hohe Transaktionsgeschwindigkeit und die gute Skalierbarkeit.

Einige typische Anwendungen des gerichteten azyklischen Graphen

Da der DAG-Algorithmus eine topologische Ordnung der Objekte erzeugt, lassen sich die verbundenen Knoten in lineare Sequenzen mit einer geregelten Abfolge und mit Anfangs- und Endpunkt überführen. Diese gerichteten azyklischen Graphen mit ihren linearen Sequenzen eignen sich sehr gut zur Darstellung von kausalen Zusammenhängen, von Abstammungsverhältnissen oder von Prozessabläufen. Die DAGs lassen sich in vielen verschiedenen Anwendungen sinnvoll einsetzen. In der Telekommunikationstechnik werden sie verwendet, um beispielsweise optimale Routen oder alternative Verbindungen in Netzwerken zu finden und gleichzeitig Rooting-Loops zu vermeiden. Zahlreiche Routingprotokolle und -algorithmen nutzen die Graphentheorie und den Directed Acyclic Graph. Eine weitere Anwendung ist das Projektmanagement. DAGs lassen sich verwenden, um komplexe Aufgaben zu planen, zu optimieren und zu verwalten. Ebenfalls Anwendungen des gerichteten azyklischen Graphen sind:

• das Workflowmanagement

• Kryptowährungen

• klinische und medizinische Studien

• das Prozessmanagement

• die Ahnenforschung und Abstammungsbäume

• die Evolutionsforschung

• die Künstliche Intelligenz (KI) und neuronale Netzwerke

• Software-Repositorys und Versionsverwaltung

• Quellen- und Belegverzeichnisse

• die Kompression von Daten

• Entscheidungsdiagramme

(ID:47808693)