Regie acyclische Graphen

Beispiel eines gerichteten acyclischen Graphen

Im Mathematik, im Speziellen Graphentheorie, und Informatik, a Regie acyclische Graphen (Dag /ˈdæɡ/ (Hören)) ist ein gerichteter Graph ohne gerichtete Zyklen. Das heißt, es besteht aus Eckpunkte und Kanten (auch genannt Bögen) mit jeder Kante von einem Scheitelpunkt zum anderen, so dass das Befolgen dieser Richtungen niemals eine geschlossene Schleife bilden wird. Ein gerichteter Diagramm ist eine DAG, wenn und nur wenn dies sein kann topologisch geordnetdurch Anordnung der Eckpunkte als lineare Bestellung, die mit allen Kantenrichtungen übereinstimmt. DAGs haben zahlreiche wissenschaftliche und rechnerische Anwendungen, die von Biologie (Evolution, Stammbäumen, Epidemiologie) bis hin zu Informationswissenschaft (Zitiernetzwerke) bis zur Berechnung (Planung) reichen.

Gerichtete acyclische Graphen werden manchmal stattdessen genannt Acyclic -gerichtete Diagramme[1] oder Akyklische Digraphen.[2]

Definitionen

A Graph wird gebildet von Eckpunkte und von Kanten Verbindungspaare von Scheitelpunkten, bei denen die Scheitelpunkte jede Art von Objekt sein können, die paarweise mit Kanten verbunden sind. Im Fall von a gerichteter GraphJede Kante hat eine Ausrichtung, von einem Scheitelpunkt bis zu einem anderen Scheitelpunkt. EIN Weg In einem gerichteten Diagramm befindet sich eine Sequenz von Kanten mit der Eigenschaft, dass der Endscheitel jeder Kante in der Sequenz mit dem Startscheitel der nächsten Kante in der Sequenz übereinstimmt. Ein Pfad bildet einen Zyklus, wenn der Startscheitel seiner ersten Kante dem Endscheitel seiner letzten Kante entspricht. Ein gerichteter acyclischer Diagramm ist ein gerichteter Diagramm mit keinen Zyklen.[1][2][3]

Ein Scheitelpunkt v eines gerichteten Diagramms soll sein erreichbar von einem anderen Scheitelpunkt u Wenn es einen Pfad gibt, der mit beginnt u und endet bei v. Als Sonderfall wird jeder Scheitelpunkt von sich selbst als erreichbar angesehen (durch einen Pfad mit Nullkanten). Wenn sich ein Scheitelpunkt über einen nicht trivialen Pfad (ein Pfad mit einem oder mehreren Kanten) selbst erreichen kann, ist dieser Pfad ein Zyklus. Eine andere Möglichkeit, gerichtete acyclische Graphen zu definieren Nichttrivialweg.[4]

Mathematische Eigenschaften

Erreichbarkeitsbeziehung, transitives Schließen und transitive Reduktion

Eine Dag
Seine transitive Reduktion

Das Erreichbarkeitsbeziehung einer DAG kann als formalisiert werden Teilreihenfolge auf den Eckpunkten der DAG. In dieser teilweisen Reihenfolge zwei Scheitelpunkte u und v werden bestellt wie uv genau dann, wenn es einen gerichteten Weg von existiert u zu v in der Dag; das ist wenn u kann erreichen v (oder v ist erreichbar von u).[5] Unterschiedliche DAGs können jedoch zu der gleichen Erreichbarkeitsbeziehung und der gleichen teilweisen Reihenfolge führen.[6] Zum Beispiel eine DAG mit zwei Kanten uv und vw hat die gleiche Erreichbarkeitsbeziehung wie die DAG mit drei Kanten uv, vw, und uw. Beide DAGs erzeugen die gleiche Teilreihenfolge, in der die Eckpunkte bestellt werden wie uvw.

Das Transitive Schließung einer DAG ist die Grafik mit den meisten Kanten, die die gleiche Erreichbarkeitsbeziehung wie die DAG aufweist. Es hat eine Kante uv für jedes Paar Eckpunkte (u, v) in der Erreichbarkeitsbeziehung der DAG und kann daher als direkte Übersetzung der Erreichbarkeitsbeziehung betrachtet werden in graphentheoretische Begriffe. Die gleiche Methode zur Übersetzung von Teilaufträgen in DAGs funktioniert allgemeiner: Für jede endlich teilweise bestellte Menge (S, ≤), die Grafik, die einen Scheitelpunkt für jedes Element von hat S und eine Kante für jedes Elementpaar in ist automatisch eine transitiv geschlossene Dag und hat (S, ≤) als Erreichbarkeitsbeziehung. Auf diese Weise kann jede endliche teilweise geordnete Menge als DAG dargestellt werden.

A Hasse -Diagramm Darstellung der teilweisen Reihenfolge der festgelegten Inklusion (⊆) zwischen den Untergruppen eines Drei-Element-Satzes

Das Transitive Reduktion einer DAG ist die Grafik mit den wenigsten Kanten, die die gleiche Erreichbarkeitsbeziehung wie die DAG aufweist. Es hat eine Kante uv für jedes Paar Eckpunkte (u, v) in dem covering relation der Erreichbarkeitsbeziehung der Dag. Es ist ein Untergraphen der DAG, gebildet durch Abwerfen der Kanten uv wofür die DAG auch einen länger gerichteten Weg enthält u zu v. Wie der transitive Verschluss ist die transitive Reduktion für DAGs einzigartig definiert. Im Gegensatz dazu kann für ein nicht acyclisch gerichteter Diagramm mehr als ein minimaler Untergraph mit der gleichen Erreichbarkeitsbeziehung vorhanden sein.[7] Transitive Reduktionen sind nützlich bei der Visualisierung der von ihnen dargestellten teilweisen Bestellungen, da sie weniger Kanten haben als andere Diagramme, die dieselben Ordnungen darstellen und daher zu einfacherem führen können Diagrammzeichnungen. EIN Hasse -Diagramm einer Teilreihenfolge ist eine Zeichnung der transitiven Reduktion, bei der die Ausrichtung jeder Kante gezeigt wird, indem der Startscheitel der Kante in einer niedrigeren Position platziert wird als der Endscheitel.[8]

Topologische Ordnung

A Topologische Ordnung eines gerichteten acyclischen Diagramms: jeder Kante geht von früher in der Bestellung (oben links) bis später in der Bestellung (unten rechts). Ein gerichteter Diagramm ist nur dann acyclisch, wenn es eine topologische Bestellung hat.
Das Hinzufügen der roten Kanten zum blau gerichteten acyclischen Diagramm erzeugt eine weitere DAG, die Transitive Schließung der blauen Grafik. Für jede rote oder blaue Kante uv, v ist erreichbar aus u: Es gibt einen blauen Pfad, der mit u und enden bei v.

A Topologische Ordnung eines gerichteten Diagramms ist eine Reihenfolge seiner Eckpunkte in eine Sequenz, so dass für jeden Rand der Startscheitel der Kante früher in der Sequenz auftritt als der Endscheitel der Kante. Ein Diagramm mit einer topologischen Bestellung kann keine Zyklen haben, da der Rand in den frühesten Scheitelpunkt eines Zyklus falsch ausgerichtet sein müsste. Daher ist jede Grafik mit einer topologischen Ordnung acyclisch. Umgekehrt hat jede gerichtete acyclische Grafik mindestens eine topologische Reihenfolge. Die Existenz einer topologischen Ordnung kann daher als äquivalente Definition einer gerichteten acyclischen Graphen verwendet werden: Sie sind genau die Grafiken mit topologischen Ordnung.[2] Im Allgemeinen ist diese Ordnung nicht einzigartig; Eine DAG hat eine einzigartige topologische Ordnung, wenn sie nur dann über einen gerichteten Pfad verfügt, der alle Scheitelpunkte enthält. In diesem Fall ist die Bestellung mit der Reihenfolge, in der die Eckpunkte im Pfad erscheinen.[9]

Die Familie der topologischen Ordnung einer DAG ist die gleiche wie die Familie von lineare Erweiterungen der Erreichbarkeitsbeziehung für die DAG,[10] So haben zwei Diagramme, die dieselbe Teilreihenfolge darstellen, dieselben topologischen Ordnungen.

Kombinatorische Aufzählung

Das Graph -Aufzählung Das Problem der Zählung gerichteter acyclischer Graphen wurde von untersucht Robinson (1973).[11] Die Anzahl der DAGs auf n beschriftete Scheitelpunkte, für n= 0, 1, 2, 3,… (ohne Einschränkungen der Reihenfolge, in der diese Zahlen in einer topologischen Reihenfolge der DAG erscheinen) ist

1, 1, 3, 25, 543, 29281, 3781503,… (Sequenz A003024 in dem Oeis).

Diese Zahlen können von der berechnet werden Rezidivbeziehung

[11]

Eric W. Weisstein vermutet,[12] und McKay et al. (2004) bewiesen, dass die gleichen Zahlen die zählen (0,1) Matrizen für was alles Eigenwerte sind positiv reale Nummern. Der Beweis ist Bijektiv: Eine Matrix A ist ein Adjazenzmatrix einer Dag, wenn und nur wenn A+I ist eine (0,1) Matrix mit allen Eigenwerten positiv, wo I bezeichnet die Identitätsmatrix. Weil eine DAG nicht haben kann Selbstschleifen, seine Adjazenzmatrix muss eine Null -Diagonale haben, sodass hinzugefügt wird I Bewahrt die Eigenschaft, dass alle Matrixkoeffizienten 0 oder 1 betragen.[13]

Verwandte Familien von Grafiken

A Multitree, eine DAG, in der der von jedem Scheitelpunkt erreichbare Untergraphen einen ungerichteten Baum induziert (z. B. in Rot)
A Polytree, eine DAG, die gebildet wird, indem die Kanten eines ungerichteten Baums orientiert werden

A Multitree (auch a genannt stark eindeutige Grafik oder ein Mangrove) ist eine DAG, in der es höchstens einen gerichteten Pfad zwischen zwei beliebigen Scheitelpunkten gibt. Äquivalent ist es eine DAG ungerichteter Baum.[14]

A Polytree (auch a genannt Regieer Baum) ist ein Multitree, das durch Ausrichtung der Ränder eines ungerichteten Baumes gebildet wird.[15]

Ein Arboreszenz ist ein Polytree, das von gebildet wurde von Orientierung die Kanten eines ungerichteten Baumes von einem bestimmten Scheitelpunkt weg, genannt die Wurzel der Laube.

Rechenprobleme

Topologische Sortierung und Anerkennung

Topologische Sortierung ist das algorithmische Problem, eine topologische Reihenfolge einer bestimmten DAG zu finden. Es kann gelöst werden lineare Zeit.[16] Kahns Algorithmus für die topologische Sortierung baut die Scheitelpunktbestellung direkt auf. Es unterhält eine Liste von Eckpunkten, die keine eingehenden Kanten von anderen Scheitelpunkten haben, die noch nicht in der teilweise konstruierten topologischen Reihenfolge aufgenommen wurden. Zunächst besteht diese Liste aus den Eckpunkten ohne eingehende Kanten. Dann fügt es wiederholt einen Scheitelpunkt aus dieser Liste zum Ende der teilweise konstruierten topologischen Ordnung hinzu und prüft, ob seine Nachbarn der Liste hinzugefügt werden sollten. Der Algorithmus endet, wenn alle Scheitelpunkte auf diese Weise verarbeitet wurden.[17] Alternativ kann eine topologische Reihenfolge durch Umkehrung a konstruiert werden Postorder Nummerierung von a Tiefe-First-Suche Graph Traversal.[16]

Es ist auch möglich zu überprüfen[18] Oder alternativ für einige topologische Sortieralgorithmen, indem Sie überprüfen, ob der Algorithmus alle Scheitelpunkte erfolgreich bestellt, ohne eine Fehlerbedingung zu erfüllen.[17]

Konstruktion aus zyklischen Graphen

Jede ungerichtete Grafik kann durch Auswahl a ein DAG gemacht werden Gesamtbestellung für seine Eckpunkte und jede Kante vom früheren Endpunkt in der Reihenfolge zum späteren Endpunkt. Das resultierende Orientierung der Kanten heißt ein Akyklische Orientierung. Unterschiedliche Gesamtaufträge können zu der gleichen acyclischen Ausrichtung führen, also eine n-Vertex -Diagramm kann weniger haben als n! Akyklische Orientierungen. Die Anzahl der acyclischen Orientierungen ist gleich |χ(–1) |, wo χ ist der chromatisches Polynom der angegebenen Grafik.[19]

Das gelb gerichtete acyclische Diagramm ist die Kondensation des blau gerichteten Diagramms. Es wird von gebildet von Vertrag jeder stark verbundene Komponente der blauen Grafik in einen einzelnen gelben Scheitelpunkt.

Jede gerichtete Grafik kann durch Entfernen von a in eine DAG gemacht werden Feedback -Scheitelpunkt -Set oder ein Feedback -Bogen eingestellt, eine Reihe von Eckpunkten oder Kanten (jeweils), die alle Zyklen berühren. Das kleinste solche Set ist jedoch Np-harte finden.[20] Ein willkürlich gerichtetes Diagramm kann auch in eine DAG umgewandelt werden, die als seine genannt wird Kondensation, durch Vertrag jedes seiner stark verbundene Komponenten in einen einzigen Supervertex.[21] Wenn der Diagramm bereits acyclisch ist, sind die kleinsten Rückkopplungsscheibensätze und Feedback -Bogensätze leerund seine Kondensation ist die Grafik selbst.

Transitivverschluss und transitive Reduktion

Die transitive Schließung einer bestimmten DAG mit n Eckpunkte und m Kanten können rechtzeitig konstruiert werden O(mn) durch Verwendung von beiden Breite-First-Suche oder Tiefe-First-Suche Erreichbarkeit von jedem Scheitelpunkt zu testen.[22] Alternativ kann es in der Zeit gelöst werden O(nω) wo ω<2.373 ist der Exponent für Matrix -Multiplikationsalgorithmen; Dies ist eine theoretische Verbesserung gegenüber dem O(mn) gebunden für dichte Grafiken.[23]

In all diesen transitiven Verschlussalgorithmen ist es möglich, Paare von Scheitelpunkten zu unterscheiden, die um mindestens einen Pfad mit zwei oder mehr von Paaren erreichbar sind, die nur durch einen Länge-One-Pfad verbunden werden können. Die transitive Reduktion besteht aus den Kanten, die länge-eins-Pfade bilden, die die einzigen Pfade sind, die ihre Endpunkte verbinden. Daher kann die transsitive Reduktion in denselben asymptotischen Zeitgrenzen wie der transitive Verschluss konstruiert werden.[24]

Schließungsproblem

Das Schließungsproblem nimmt als Eingabe einen scheidungsgewichteten acyclischen Diagramm ein und sucht das minimale (oder maximale) Gewicht eines Verschlusses-ein Satz von Scheitelpunkten C, so dass keine Kanten abreisen C. Das Problem kann für gerichtete Graphen ohne Annahme von Akyklizität formuliert werden, jedoch ohne größere Allgemeinheit, da es in diesem Fall dem gleichen Problem bei der Kondensation des Diagramms entspricht. Es kann in der Polynomzeit unter Verwendung einer Reduktion an der gelöst werden Maximales Durchflussproblem.[25]

Pfadalgorithmen

Einige Algorithmen werden einfacher, wenn sie auf DAGs anstelle von allgemeinen Graphen verwendet werden, basierend auf dem Prinzip der topologischen Reihenfolge. Zum Beispiel ist es möglich zu finden kürzeste Wege und längste Wege von einem gegebenen Startscheitel in DAGs in linearer Zeit von Verarbeitung der Eckpunkte in topologischer Reihenfolgeund Berechnung der Pfadlänge für jeden Scheitelpunkt als die minimale oder maximale Länge, die über einen seiner eingehenden Kanten erhalten wird.[26] Im Gegensatz dazu kann für willkürliche Graphen der kürzeste Weg möglicherweise langsamere Algorithmen wie z. Dijkstra -Algorithmus oder der Bellman -.ford -Algorithmus,[27] und längste Wege in willkürlichen Grafiken sind Np-harte finden.[28]

Anwendungen

Planung

Geführte acyclische Graphendarstellungen von Teilauftragungen haben viele Anwendungen in Planung Für Aufgaben mit Aufgaben mit Bestellbeschränkungen.[29] Eine wichtige Klasse von Problemen dieses Typs betreffende Sammlungen von Objekten, die aktualisiert werden müssen, wie z. B. die Zellen von a Kalkulationstabelle Nachdem einer der Zellen geändert wurde oder die Objektdateien einer Computersoftware nach seiner Quellcode wurde geändert. In diesem Zusammenhang a Abhängigkeitsgrafik ist ein Diagramm, das einen Scheitelpunkt für jedes Objekt hat, das aktualisiert werden muss, und eine Kante, die zwei Objekte verbindet, wenn einer von ihnen früher als der andere aktualisiert werden muss. Ein Zyklus in dieser Grafik wird als a genannt Zirkularabhängigkeitund ist im Allgemeinen nicht erlaubt, da es keine Möglichkeit gibt, die im Zyklus verbundenen Aufgaben konsequent zu planen. Abhängigkeitsdiagramme ohne kreisförmige Abhängigkeiten bilden DAGs.[30]

Zum Beispiel, wenn eine Zelle von a Kalkulationstabelle Änderungen müssen die Werte anderer Zellen neu berechnen, die direkt oder indirekt von der veränderten Zelle abhängen. Für dieses Problem sind die zu geplanten Aufgaben die Neuberechnung der Werte einzelner Zellen der Tabelle. Abhängigkeiten entstehen, wenn eine Expression in einer Zelle einen Wert aus einer anderen Zelle verwendet. In einem solchen Fall muss der verwendete Wert früher als der aus dem verwendete Ausdruck neu berechnet werden. Topologisch bestellt das Abhängigkeitsdiagramm und die Verwendung dieser topologischen Reihenfolge, um die Zellaktualisierungen zu planen, ermöglicht es, dass die gesamte Tabelle nur mit einer einzelnen Bewertung pro Zelle aktualisiert wird.[31] Ähnliche Probleme der Aufgabenbestellung ergeben sich in Makefiles Für Programmkompilierung[31] und Anweisungsplanung Für die Optimierung des Computerprogramms auf niedrigem Niveau.[32]

PERT -Diagramm für ein Projekt mit fünf Meilensteinen (mit 10–50 bezeichnet) und sechs Aufgaben (mit A - F bezeichnet). Es gibt zwei kritische Wege, ADF und BC.

Eine etwas andere dag-basierte Formulierung von Planungsbeschränkungen wird von der verwendet Programmbewertung und Überprüfungstechnik (PERT), eine Methode zum Management großer menschlicher Projekte, die eine der ersten Anwendungen von DAGs war. Bei dieser Methode repräsentieren die Eckpunkte einer DAG Meilensteine eines Projekts anstelle spezifischer Aufgaben, die ausgeführt werden sollen. Stattdessen wird eine Aufgabe oder Aktivität durch einen Rand einer DAG dargestellt, die zwei Meilensteine ​​verbindet, die den Beginn und die Fertigstellung der Aufgabe markieren. Jede solche Kante ist mit einer Schätzung für die Zeit gekennzeichnet, in der ein Team von Arbeitnehmern die Aufgabe erfüllt wird. Das längster Weg in dieser DAG repräsentiert die kritischer Weg des Projekts, der die Gesamtzeit für das Projekt steuert. Einzelne Meilensteine ​​können gemäß den Längen der längsten Wege geplant werden, die an ihren Eckpunkten enden.[33]

Datenverarbeitungsnetzwerke

Eine gerichtete acyclische Grafik kann verwendet werden, um ein Netzwerk von Verarbeitungselementen darzustellen. In dieser Darstellung treten Daten über seine eingehenden Kanten in ein Verarbeitungselement ein und lassen das Element an seinen ausgehenden Kanten.

Zum Beispiel im elektronischen Schaltungsdesign statisch Kombinationslogik Blöcke können als acyclisches System von dargestellt werden Logik -Tore Das berechnet eine Funktion einer Eingabe, wobei die Eingabe und Ausgabe der Funktion als individuell dargestellt werden Bits. Im Allgemeinen kann die Ausgabe dieser Blöcke nur als Eingabe verwendet werden, es sei denn, sie wird von einem Register- oder Statuselement erfasst, das seine acyclischen Eigenschaften beibehält.[34] Elektronische Schaltungsschematiker entweder auf Papier oder in einer Datenbank sind eine Form von gerichteten acyclischen Graphen, die Instanzen oder Komponenten verwenden, um eine gerichtete Referenz auf eine Komponente auf niedrigerer Ebene zu bilden. Elektronische Schaltungen selbst sind nicht unbedingt acyclisch oder gerichtet.

Datenflow -Programmierung Sprachen beschreiben Operationssysteme auf Datenströmeund die Verbindungen zwischen den Ausgängen einiger Operationen und den Eingaben anderer. Diese Sprachen können bequem für die Beschreibung von Aufgaben der sich wiederholenden Datenverarbeitungsaufgaben sein, bei denen dieselbe acyclisch verbundene Erfassung von Operationen auf viele Datenelemente angewendet wird. Sie können als ausgeführt werden Parallelalgorithmus in dem jede Operation durch einen parallelen Prozess ausgeführt wird, sobald ein weiterer Satz von Eingängen ihm zur Verfügung steht.[35]

Im Compiler, Gerade Liniencode (dh Sequenzen von Anweisungen ohne Schleifen oder bedingten Zweige) können durch eine DAG dargestellt werden, die die Eingaben und Ausgänge jeder der im Code ausgeführten arithmetischen Operationen beschreibt. Diese Darstellung ermöglicht es dem Compiler, durchzuführen gemeinsame Eliminierung der Subtonpression effizient.[36] Auf einer höheren Ebene der Codeorganisation die Acyclic -Abhängigkeitsprinzip Gibt an, dass die Abhängigkeiten zwischen Modulen oder Komponenten eines großen Softwaresystems ein gerichtetes acyclisches Diagramm bilden sollten.[37]

Feedforward Neural Networks sind ein anderes Beispiel.

Kausalstrukturen

Diagramme, in denen Scheitelpunkte Ereignisse darstellen, die zu einem bestimmten Zeitpunkt auftreten und in denen die Kanten immer vom frühen Zeitscheitel bis zu einem späten Scheitelpunkt der Kante zeigen, sind notwendigerweise gerichtet und acyclisch. Das Fehlen eines Zyklus folgt, da die mit einem Scheitelpunkt verbundene Zeit immer zunimmt, wenn Sie jedem folgen Weg In der Grafik, damit Sie niemals auf einen Pfad zu einem Scheitelpunkt zurückkehren können. Dies spiegelt unsere natürliche Intuition wider, dass Kausalität bedeutet, dass Ereignisse nur die Zukunft beeinflussen können, sie niemals die Vergangenheit beeinflussen, und daher haben wir keine Kausalschleifen. Ein Beispiel für diese Art von gerichteten acyclischen Diagramm Kausaler -Ansatz zur Quantengrärzen In diesem Fall sind die angenommenen Grafiken jedoch transitiv vollständig. In dem folgenden Beispiel für Versionsverlauf ist jede Version der Software mit einer eindeutigen Zeit verknüpft, in der Regel die Zeit, in der die Version gespeichert, festgelegt oder veröffentlicht wurde. In den folgenden Beispielen für Zitiergrafiken werden die Dokumente gleichzeitig veröffentlicht und können nur auf ältere Dokumente verweisen.

Manchmal sind Ereignisse nicht mit einer bestimmten physischen Zeit verbunden. Vorausgesetzt, dass Ereignispaare eine rein kausale Beziehung haben, sind die Kanten dargestellt kausale Beziehungen Zwischen den Ereignissen haben wir ein gerichtetes acyclisches Diagramm.[38] Zum Beispiel a Bayesianes Netzwerk repräsentiert ein System probabilistischer Ereignisse als Eckpunkte in einem gerichteten acyclischen Graphen, bei dem die Wahrscheinlichkeit seiner Vorgänger in der DAG aus den Wahrscheinlichkeiten seiner Vorgänger berechnet werden kann.[39] In diesem Zusammenhang die Moralische Grafik einer DAG ist das ungerichtete Diagramm, das durch Hinzufügen einer (ungerichteten) Kante zwischen allen Eltern desselben Scheitelpunkts erstellt wurde (manchmal genannt heiraten) und dann alle gerichteten Kanten durch ungerichtete Kanten ersetzen.[40] Eine andere Art von Grafik mit einer ähnlichen Kausalstruktur ist eine Einfluss von Diagramm, der Eckpunkte, deren Entscheidungen oder unbekannte Informationen und die Kanten kausale Einflüsse von einem Scheitelpunkt zum anderen darstellen.[41] Im EpidemiologieZum Beispiel werden diese Diagramme häufig verwendet, um den erwarteten Wert verschiedener Auswahlmöglichkeiten für die Intervention abzuschätzen.[42][43]

Das Gegenteil ist auch wahr. In jeder Anwendung, die durch eine gerichtete acyclische Grafik dargestellt wird, gibt es eine kausale Struktur, entweder eine explizite Reihenfolge oder eine Zeit in der Beispiel oder eine Reihenfolge, die aus der Diagrammstruktur abgeleitet werden kann. Dies folgt, weil alle gerichteten acyclischen Graphen a haben Topologische Ordnung, d. H. Es gibt mindestens eine Möglichkeit, die Eckpunkte in eine Reihenfolge zu setzen, so dass alle Kanten entlang dieser Reihenfolge in die gleiche Richtung zeigen.

Genealogie und Versionsgeschichte

Stammbaum der Ptolemäische Dynastiemit vielen Ehen zwischen nahe Verwandte Ursache Stammbaum Zusammenbruch.

Stammbäume kann als gerichtete acyclische Graphen mit einem Scheitelpunkt für jedes Familienmitglied und eine Kante für jede Eltern-Kind-Beziehung angesehen werden.[44] Trotz des Namen Stammbaum Zusammenbruch.[45] Die Grafiken von Matrilineal Abstieg (Mutter-Tochter-Beziehungen) und patrilineal Abstieg (Vater-Sohn-Beziehungen) sind Bäume in dieser Grafik. Weil niemand sein eigener Vorfahr werden kann, sind Stammbäume acyclisch.[46]

Die Versionsgeschichte von a Distributed Revision Control System, wie z. Git, hat im Allgemeinen die Struktur eines gerichteten acyclischen Diagramms, in dem ein Scheitelpunkt für jede Revision und eine Kantepaare von Überarbeitungen vorhanden sind, die direkt voneinander abgeleitet wurden. Dies sind keine Bäume im Allgemeinen aufgrund von Zusammenführungen.[47]

In vielen zufällig Algorithmen in Computergeometrie, der Algorithmus beibehält a Geschichte Dag Darstellung der Versionsgeschichte einer geometrischen Struktur im Verlauf einer Abfolge von Änderungen an der Struktur. Zum Beispiel in a Randomisierte inkrementelle Algorithmus für Delaunay -TriangulationDie Triangulation ändert sich, indem ein Dreieck durch drei kleinere Dreiecke ersetzt wird, wenn jeder Punkt hinzugefügt wird, und durch "Flip" -Operationen, die Dreieckpaare durch ein anderes Dreieckpaar ersetzen. Die Geschichte der Geschichte für diesen Algorithmus hat einen Scheitelpunkt für jedes als Teil des Algorithmus konstruierte Dreiecks und Kanten von jedem Dreieck zu den beiden oder drei anderen Dreiecken, die sie ersetzen. Diese Struktur erlaubt Punktstandort Anfragen, die effizient beantwortet werden sollen: den Ort eines Abfragestells zu finden q Folgen Sie in der Delaunay -Triangulation einen Weg in der Geschichte, bei jedem Schritt, der sich zum Ersatzdreieck befindet, das enthält q. Das in diesem Weg erreichte letzte Dreieck muss das Delaunay -Dreieck sein, das enthält q.[48]

Zitierdiagramme

In einem Zitierdiagramm Die Scheitelpunkte sind Dokumente mit einem einzigen Veröffentlichungsdatum. Die Kanten stellen die Zitate aus der Bibliographie eines Dokuments auf andere frühere Dokumente dar. Das klassische Beispiel stammt aus den Zitaten zwischen akademischen Papieren, wie im Artikel "Networks of Scientific Papers" von 1965 hervorgehoben wird.[49] durch Derek J. de Solla Preis Wer fuhr fort, das erste Modell eines Zitiernetzwerks zu produzieren, das Preismodell.[50] In diesem Fall der Zitat eines Papiers ist nur der Grad des entsprechenden Scheitelpunkts des Zitiernetzwerks. Dies ist eine wichtige Maßnahme in Zitieranalyse. Gerichtsurteile Geben Sie ein weiteres Beispiel an, da die Richter ihre Schlussfolgerungen in einem Fall unterstützen, indem sie andere frühere Entscheidungen in früheren Fällen abrufen. Ein letztes Beispiel wird durch Patente bereitgestellt, auf die sich früher beziehen müssen vorherige Kunstfrühere Patente, die für den aktuellen Patentanspruch relevant sind. Unter Berücksichtigung der speziellen Eigenschaften von gerichteten acyclischen Graphen kann man Zitiernetzwerke mit Techniken analysieren, die bei der Analyse der allgemeinen Graphen, die in vielen Studien verwendet wurden, nicht verfügbar sind Netzwerkanalyse. Zum Beispiel Transitive Reduktion gibt neue Einblicke in die Zitierverteilungen in verschiedenen Anwendungen, die klare Unterschiede in den Mechanismen hervorheben, die Zitate -Netzwerke in verschiedenen Kontexten erstellen.[51] Eine andere Technik ist Hauptpfadanalyse, was die Zitierverbindungen verfolgt und die bedeutendsten Zitierketten in einem gegebenen vorschlägt Zitierdiagramm.

Das Preismodell ist zu einfach, um ein realistisches Modell von a zu sein Zitiernetzwerk Es ist jedoch einfach genug, um analytische Lösungen für einige seiner Eigenschaften zu ermöglichen. Viele davon können unter Verwendung von Ergebnissen gefunden werden, die aus der ungerichteten Version der abgeleitet wurden Preismodell, das Barabási -Albert -Modell. Aber seit Preismodell Gibt ein gerichtetes acyclisches Diagramm, es ist ein nützliches Modell bei der Suche nach analytischen Berechnungen von Eigenschaften, die für gerichtete acyclische Graphen einzigartig sind. Zum Beispiel skaliert die Länge des längsten Pfades vom N-ten Knoten zum Netzwerk zum ersten Knoten im Netzwerk als[52] .

Datenkompression

Dokumentierte acyclische Graphen können auch als verwendet werden Kompakte Darstellung einer Sammlung von Sequenzen. In dieser Art von Anwendung findet man eine DAG, in der die Pfade die angegebenen Sequenzen bilden. Wenn viele der Sequenzen dieselben Subsequenzen teilen, können diese gemeinsam genutzten Subsequenzen durch einen gemeinsam genutzten Teil der DAG dargestellt werden, sodass die Darstellung weniger Platz verwenden kann, als alle Sequenzen getrennt aufzulisten. Zum Beispiel die Regie acyclische Wortdiagramme ist ein Datenstruktur in Informatik gebildet durch eine gerichtete acyclische Grafik mit einer einzelnen Quelle und mit Kanten, die durch Buchstaben oder Symbole gekennzeichnet sind; Die Pfade von der Quelle zu den Senkeln in diesem Diagramm stellen einen Satz von dar Saitenwie englische Wörter.[53] Jeder Satz von Sequenzen kann als Pfade in einem Baum dargestellt werden, indem für jedes Präfix einer Sequenz ein Baumscheiben gebildet wird und das Elternteil einer dieser Scheitelpunkte die Sequenz mit einem Element weniger darstellt. Der auf diese Weise gebildete Baum für eine Reihe von Saiten wird als a genannt Trie. Ein gerichteter acyclischer Wortdiagramm spart Platz über einem Tries, indem er sich den Pfaden abwehren und wieder anschließen kann, so dass eine Reihe von Wörtern mit den gleichen möglichen Suffixen durch einen einzelnen Baumscheitelpunkt dargestellt werden kann.[54]

Die gleiche Idee, eine DAG zur Darstellung einer Pfadfamilie zu verwenden, tritt in der Binärentscheidungsdiagramm,[55][56] Eine dag-basierte Datenstruktur zur Darstellung von Binärfunktionen. In einem binären Entscheidungsdiagramm wird jeder Nicht-Sink-Scheitelpunkt mit dem Namen einer binären Variablen gekennzeichnet, und jede Spüle und jede Kante wird durch einen 0 oder 1. der Funktionswert für beliebig gekennzeichnet Wahrheitsaufgabe Zu den Variablen ist der Wert an der Spüle, die durch die Befolgung eines Pfades gefunden wird, beginnend mit dem einzelnen Quellscheitelpunkt, der an jedem nicht-sinke Scheitelpunkt der mit dem Wert der Variablen dieses Scheitelpunkts gekennzeichneten ausgehenden Kante folgt. So wie gerichtete acyclische Wortdiagramme als komprimierte Form von Versuchen angesehen werden können, können binäre Entscheidungsdiagramme als komprimierte Formen von betrachtet werden Entscheidungsbäume Dieser Speicherplatz spart, indem sie sich den Wegen zurückziehen lassen, wenn sie sich über die Ergebnisse aller verbleibenden Entscheidungen einig sind.[57]

Verweise

  1. ^ a b Thulasiraman, K.; Swamy, M. N. S. (1992), "5,7 Acyclic Cirected Graphs", Grafiken: Theorie und AlgorithmenJohn Wiley und Sohn, p. 118, ISBN 978-0-471-51356-8.
  2. ^ a b c Bang-Jensen, Jørgen (2008), "2,1 acyclische Digraphs", Digraphen: Theorie, Algorithmen und Anwendungen, Springer-Monographien in Mathematik (2. Aufl.), Springer-Verlag, S. 32–34, ISBN 978-1-84800-997-4.
  3. ^ Christofides, Nicos (1975), Graphentheorie: Ein algorithmischer Ansatz, Academic Press, S. 170–174.
  4. ^ Mitrani, I. (1982), Simulationstechniken für diskrete Ereignissysteme, Cambridge Informatik Texte, Vol. 14, Cambridge University Press, p. 27, ISBN 9780521282826.
  5. ^ Kozen, Dexter (1992), Das Design und die Analyse von Algorithmen, Monographien in Informatik, Springer, p. 9,, ISBN 978-0-387-97687-7.
  6. ^ Banerjee, Utpal (1993), "Übung 2 (c)", Schleifentransformationen für Umstrukturierungs Compiler: Die Grundlagen, Springer, p. 19, Bibcode:1993ltfr.book ..... b, ISBN 978-0-7923-9318-4.
  7. ^ Bang-Jensen, Jørgen; Gutin, Gregory Z. (2008), "2,3 transitive Digraphen, transitive Verschlüsse und Reduktionen", Digraphen: Theorie, Algorithmen und Anwendungen, Springer -Monographien in Mathematik, Springer, S. 36–39, ISBN 978-1-84800-998-1.
  8. ^ Jungnickel, Dieter (2012), Grafiken, Netzwerke und Algorithmen, Algorithmen und Berechnungen in Mathematik, Vol. 5, Springer, S. 92–93, ISBN 978-3-642-32278-5.
  9. ^ Sedgewick, Robert; Wayne, Kevin (2011), "4,2,25 einzigartige topologische Ordnung", Algorithmen (4. Aufl.), Addison-Wesley, S. 598–599, ISBN 978-0-13-276256-4.
  10. ^ Bender, Edward A.; Williamson, S. Gill (2005), "Beispiel 26 (lineare Erweiterungen - Topologische Sorten)", " Ein kurzer Kurs in diskreten Mathematik, Dover Bücher über Informatik, Kurier Dover Publications, p. 142, ISBN 978-0-486-43946-4.
  11. ^ a b Robinson, R. W. (1973), "Zählung mit markierten acyclischen Digraphen", IN in Harary, F. (ed.), Neue Richtungen in der Theorie der Graphen, Academic Press, S. 239–273. Siehe auch Harary, Frank; Palmer, Edgar M. (1973), Grafische Aufzählung, Akademische Presse, p. 19, ISBN 978-0-12-324245-7.
  12. ^ Weisstein, Eric W., "Weissteins Vermutung", Mathord
  13. ^ McKay, B. D.; Royle, G. F.; Wanless, I. M.; Oggier, F. E.; Sloane, N. J. A.; Wilf, H. (2004), "Akyklische Digraphen und Eigenwerte von (0,1) -Matrizen", Journal of Integer Sequenzen, 7: 33, Arxiv:Math/0310423, Bibcode:2004Jints ... 7 ... 33m, Artikel 04.3.3.
  14. ^ Furnas, George W.; Zacks, Jeff (1994), "Multitrees: Anreicherung und Wiederverwendung hierarchischer Struktur", Proc. Sigchi -Konferenz über menschliche Faktoren in Computersystemen (Chi '94), S. 330–336, doi:10.1145/191666.191778, ISBN 978-0897916509, S2CID 18710118.
  15. ^ Rebane, George; Perle, Judäa (1987), "Die Wiederherstellung von kausalen Polybäumen aus statistischen Daten", In Proc. 3. Jahreskonferenz über Unsicherheit in der künstlichen Intelligenz (UAI 1987), Seattle, WA, USA, Juli 1987 (PDF), S. 222–228.
  16. ^ a b Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001) [1990], Einführung in Algorithmen (2. Aufl.), MIT Press und McGraw-Hill, ISBN 0-262-03293-7 Abschnitt 22.4, Topologische Sortierung, S. 549–552.
  17. ^ a b Jungnickel (2012), S. 50–51.
  18. ^ Zum Tiefe-First-Suche Basierend topologischer Sortieralgorithmus kann diese Gültigkeitsprüfung mit dem topologischen Sortieralgorithmus selbst verschachtelt werden. Siehe z. Skiena, Steven S. (2009), Das Algorithmus -Designhandbuch, Springer, S. 179–181, ISBN 978-1-84800-070-4.
  19. ^ Stanley, Richard P. (1973), "Acyclische Orientierungen von Graphen" (PDF), Diskrete Mathematik, 5 (2): 171–178, doi:10.1016/0012-365X (73) 90108-8.
  20. ^ Garey, Michael R.; Johnson, David S. (1979), Computer und Unverdaulichkeit: Ein Leitfaden zur Theorie der NP-Vervollständigung, W. H. Freeman, ISBN 0-7167-1045-5, Probleme GT7 und GT8, S. 191–192.
  21. ^ Harary, Frank; Norman, Robert Z.; Cartwright, Dorwin (1965), Strukturmodelle: Eine Einführung in die Theorie der gerichteten Grafiken, John Wiley & Sons, p. 63.
  22. ^ Skiena (2009), p. 495.
  23. ^ Skiena (2009), p. 496.
  24. ^ Bang-Jensen & Gutin (2008), p. 38.
  25. ^ Picard, Jean-Claude (1976), "Maximales Abschluss eines Diagramms und Anwendungen für kombinatorische Probleme", Managementwissenschaft, 22 (11): 1268–1272, doi:10.1287/mnsc.22.11.1268, HERR 0403596.
  26. ^ Cormen et al. 2001, Abschnitt 24.2, Single-Source-kürzeste Wege in gerichteten acyclischen Graphen, S. 592–595.
  27. ^ Cormen et al. 2001, Abschnitte 24.1, Bellman -Ford -Algorithmus, S. 588–592 und 24.3, Dijkstra -Algorithmus, S. 595–601.
  28. ^ Cormen et al. 2001, p. 966.
  29. ^ Skiena (2009), p. 469.
  30. ^ Al-Mutawa, H. A.; Dietrich, J.; Marsland, S.; McCartin, C. (2014), "über die Form der kreisförmigen Abhängigkeiten in Java -Programmen", 23. Australian Software Engineering Conference, IEEE, S. 48–57, doi:10.1109/ASWEC.2014.15, ISBN 978-1-4799-3149-1, S2CID 17570052.
  31. ^ a b Gross, Jonathan L.; Yellen, Jay; Zhang, Ping (2013), Handbuch der Graphentheorie (2. Aufl.), CRC Press, p. 1181, ISBN 978-1-4398-8018-0.
  32. ^ Srikant, Y. N.; Shankar, Priti (2007), Das Compiler Design Handbuch: Optimierungen und Maschinencodegenerierung (2. Aufl.), CRC Press, S. 19–39, ISBN 978-1-4200-4383-9.
  33. ^ Wang, John X. (2002), Was jeder Ingenieur über Entscheidungsfindung unter Unsicherheit wissen sollte, CRC Press, p. 160, ISBN 978-0-8247-4373-4.
  34. ^ Sapatnekar, Sachin (2004), Zeitliche Koordinierung, Springer, p. 133, ISBN 978-1-4020-7671-8.
  35. ^ Dennis, Jack B. (1974), "Erste Version einer Datenflussprozedursprache", Programmierungssymposium, Vorlesungsnotizen in Informatik, Vol. 19, S. 362–376, doi:10.1007/3-540-06859-7_145, ISBN 978-3-540-06859-4.
  36. ^ Touati, sid; de Dinechin, Benoit (2014), Erweiterte Backend -Optimierung, John Wiley & Sons, p. 123, ISBN 978-1-118-64894-0.
  37. ^ Girlande, Jeff; Anthony, Richard (2003), Große Softwarearchitektur: Ein praktischer Leitfaden mit UML, John Wiley & Sons, p. 215, ISBN 9780470856383.
  38. ^ Gopnik, Alison; Schulz, Laura (2007), Kausales Lernen, Oxford University Press, p. 4,, ISBN 978-0-19-803928-0.
  39. ^ Shmulevich, Ilya; Dougherty, Edward R. (2010), Probabilistische boolesche Netzwerke: Modellierung und Kontrolle von Genregulationsnetzwerken, Gesellschaft für industrielle und angewandte Mathematik, p. 58, ISBN 978-0-89871-692-4.
  40. ^ Cowell, Robert G.; Dawid, A. Philip; Lauritzen, Steffen L.; Spiegelhalter, David J. (1999), "3.2.1 Moralisierung", Probabilistische Netzwerke und Expertensysteme, Springer, S. 31–33, ISBN 978-0-387-98767-5.
  41. ^ Dorf, Richard C. (1998), Das Technologiemanagementhandbuch, CRC Press, p. 9-7, ISBN 978-0-8493-8577-3.
  42. ^ Boslaugh, Sarah (2008), Enzyklopädie der Epidemiologie, Band 1, Salbei, p. 255, ISBN 978-1-4129-2816-8.
  43. ^ Pearl, Judäa (1995), "Kausale Diagramme für die empirische Forschung", Biometrika, 82 (4): 669–709, doi:10.1093/biomet/82.4.669.
  44. ^ Kirkpatrick, Bonnie B. (April 2011), "Haplotypen gegen Genotypen auf Stammbäumen", Algorithmen für die molekulare Biologie, 6 (10): 10, doi:10.1186/1748-7188-6-10, PMC 3102622, PMID 21504603.
  45. ^ McGuffin, M. J.; Balakrishnan, R. (2005), "Interaktive Visualisierung genealogischer Graphen" (PDF), IEEE -Symposium zur Informationsvisualisierung (Infovis 2005), S. 16–23, doi:10.1109/invis.2005.1532124, ISBN 978-0-7803-9464-3.
  46. ^ Bender, Michael A.; Pemmasani, Giridhar; Skiena, Steven; Sumazin, Pavel (2001), "Finden am wenigsten häufiger Vorfahren in gerichteten acyclischen Graphen", Verfahren des zwölften jährlichen ACM-SIAM-Symposiums über diskrete Algorithmen (Soda '01), Philadelphia, PA, USA: Gesellschaft für industrielle und angewandte Mathematik, S. 845–854, ISBN 978-0-89871-490-6.
  47. ^ Bartlang, Udo (2010), Architektur und Methoden für flexibles Content-Management in Peer-to-Peer-Systemen, Springer, p. 59, Bibcode:2010aamf.book ..... b, ISBN 978-3-8348-9645-2.
  48. ^ Pach, János; Sharir, Micha, Kombinatorische Geometrie und ihre algorithmischen Anwendungen: die Alcalá -Vorlesungen, Mathematische Umfragen und Monographien, Vol. 152, American Mathematical Society, S. 93–94, ISBN 978-0-8218-7533-9.
  49. ^ Preis, Derek J. de Solla (30. Juli 1965), "Netzwerke wissenschaftlicher Papiere" (PDF), Wissenschaft, 149 (3683): ​​510–515, Bibcode:1965Sci ... 149..510d, doi:10.1126/science.149.3683.510, PMID 14325149.
  50. ^ Price, Derek J. de Solla (1976), "Eine allgemeine Theorie der bibliometrischen und anderen kumulativen Vorteile", Zeitschrift der American Society for Information Science, 27 (5): 292–306, doi:10.1002/ASI.4630270505.
  51. ^ Clough, James R.; Gollings, Jamie; Loach, Tamar V.; Evans, Tim S. (2015), "Transitive Reduction of Citation Networks", Journal of Complex Networks, 3 (2): 189–203, Arxiv:1310.8224, doi:10.1093/comnet/cnu039, S2CID 10228152.
  52. ^ Evans, T.S.; Calmon, L.; Vasiliauskaite, V. (2020), "Der längste Weg im Preismodell", Wissenschaftliche Berichte, 10 (1): 10503, Arxiv:1903.03667, Bibcode:2020natsr..1010503e, doi:10.1038/s41598-020-67421-8, PMC 7324613, PMID 32601403
  53. ^ Crochemore, Maxime; Vérin, Renaud (1997), "Direkte Konstruktion von kompakt gerichteten acyclischen Wortgrafiken", Kombinatorisches Musteranpassung, Vorlesungsnotizen in Informatik, Vol. 1264, Springer, S. 116–129, Citeseerx 10.1.1.53.6273, doi:10.1007/3-540-63220-4_55, ISBN 978-3-540-63220-7.
  54. ^ Lothaire, M. (2005), Angewandte Kombinatorik über Wörter, Encyclopedia of Mathematics und ihre Anwendungen, vol. 105, Cambridge University Press, p. 18,, ISBN 9780521848022.
  55. ^ Lee, C. Y. (1959), "Darstellung von Schaltkreisen durch Binärentscheidungsprogramme", Glockensystem Technisches Journal, 38 (4): 985–999, doi:10.1002/j.1538-7305.1959.tb01585.x.
  56. ^ Akers, Sheldon B. (1978), "Binärentscheidungsdiagramme", IEEE -Transaktionen auf Computern, C-27 (6): 509–516, doi:10.1109/tc.1978.1675141, S2CID 21028055.
  57. ^ Friedman, S. J.;Supowit, K. J. (1987), "Finden der optimalen variablen Reihenfolge für binäre Entscheidungsdiagramme", Proc.24. ACM/IEEE Design Automation Conference (DAC '87), New York, NY, USA: ACM, S. 348–356, doi:10.1145/37888.37941, ISBN 978-0-8186-0781-3, S2CID 14796451.

Externe Links