Warum sind gerichtete Graphen wichtig?

18

Wir haben über Algorithmen für MST, starke Konnektivität, Routing usw. in gerichteten Diagrammen gelesen.

In letzter Zeit wurde auch nach dynamischen und fehlertoleranten Algorithmen für gerichtete Graphen geforscht.

Aber ich habe mich gefragt, ob es praktische Anwendungen gibt, bei denen das unterstreichende Graphennetz "gerichtet" ist. Abgesehen von den sozialen Netzwerken befassen sich alle Probleme, die mir einfallen, wie das Schienen- / Straßennetz, das Internetnetz usw., nur mit ungerichteten Diagrammen.

Bearbeiten 1: Ich verstehe, dass diese verwendet werden können, um einige Szenarien zu modellieren, in denen Links geleitet werden, aber ich habe mich gefragt, wie oft diese Szenarien in der realen Welt auftreten und wie wichtig das Studium der Fehlertoleranz für gerichtete Grafiken ist.

graphs graph-theory fault-tolerance chyle
quelle
6
Zwei der bekanntesten Klassen gerichteter Graphen in der gesamten Informatik sind der Baum und DAG (Directed Acyclic Graph). Der Baum wird in vielen Bereichen verwendet (z. B. Stammbäume, Hierarchien). Die DAG kann anspruchsvollere Versionen davon erstellen. DAGs werden im Wesentlichen immer dann verwendet, wenn Sie eine Reihe von Entitäten haben, die voneinander abhängig sind. Wenn Ihr Problem eine "Zeit" - oder "Schritt-für-Schritt" -Komponente hat, steht die Regie für diesen unaufhaltsamen Fortschritt. Sie sehen DAGs in Form von Flussdiagrammen, Paketverwaltungssoftware und SSA-Formularen für die Zwischendarstellung von Compilern.
Ich werde nicht existieren Idonotexist
2
OK, was ist deine eigentliche Frage? Möchten Sie wissen, warum gerichtete Diagramme wichtig sind oder warum Fehlertoleranz in gerichteten Diagrammen wichtig ist? Das sind zwei völlig getrennte Fragen.
David Richerby
2
Ihre Beispiele sind zwar in der Implementierung physisch "ungerichtet", haben jedoch häufig Grafiken, die logisch funktionieren. Zum Beispiel fahren Züge nicht bidirektional - sie fahren in die eine oder andere Richtung nach einem Zeitplan. Nehmen wir an, man plant nicht die Züge, sondern nur die Fahrgäste. Dann ist diese Person an einem gerichteten Graphen interessiert, trotz der willkürlichen Tatsache, dass Züge theoretisch in beide Richtungen auf einer Schiene fahren können.
Darren Ringer
5
chyle: Netzwerke können mit Sicherheit davon profitieren, durch einen gerichteten Graphen dargestellt zu werden. Die meisten Internetverbindungen im Haushalt sind asymmetrisch. Die Upstream- und Downstream-Links können völlig unterschiedliche Eigenschaften haben (Bandbreite, Latenz, Paketverlust usw.)
Alexander - Reinstate Monica
1
Ich kenne nicht alle anderen, aber mein Stammbaum ist ein Digraph. Ich bin nicht das Elternteil meiner Mutter.

Antworten:

36

Unter Hinweis darauf, dass ein gerichteter Graph ein Graph ist, bei dem die Kanten eine zugeordnete Richtung haben.

Mit einem gerichteten Graphen können Sie asymmetrische Beziehungen zwischen Knoten darstellen, während wir in einem ungerichteten Graphen nur symmetrische Beziehungen darstellen können.

In der Praxis können Sie mithilfe eines gerichteten Diagramms Folgendes darstellen:

  • Straßennetze (unter Verwendung eines gerichteten Graphen können Sie die Richtung der Straßen darstellen);
  • Hyperlinks, die Webseiten verbinden ;
  • Abhängigkeiten in Softwaremodulen ;
  • Beute-Raubtier-Beziehungen ;
  • deterministischer endlicher Automat .

Neben diesen klassischen Beispielen können Sie viele andere reale Szenarien (Finanzhandel, Planung, Infektionskrankheiten, Zitierweise, Kontrollfluss usw.) darstellen, die eine geordnete Beziehung erfordern [1] .

darioSka
quelle
4
Gute Antwort. Ich denke, OP vergisst, dass man eigentlich zwei Straßen hat , wenn man eine Straße hat (eine für jede Richtung, normalerweise perfekt parallel). Sie können als einfaches Diagramm dargestellt werden, aber gerichtete Diagramme ergänzen das Modell um wichtige Informationen.
ecc
Mir gefällt das und ich stelle fest, dass in dieser Antwort mit Hyperlinks verknüpfte Webseiten erwähnt werden - was die Verwendung der Zurück-Funktion ausschließt. ;-)
SDsolar
Um den Kommentar von @ ecc in die Landessprache einzufügen, haben Sie zwei Knoten, die durch zwei Kanten verbunden sind. Jede Kante ist entgegengesetzt zur anderen gerichtet. Es kommt häufig in deterministischen Zustandsdiagrammen vor. Für Straßen würde es sich auf eine einzelne Kante reduzieren, egal ob gerichtet (in eine Richtung) oder ungerichtet.
SDsolar
4
@ecc auch, wo ich aus (Kalifornien) bin, haben wir Einbahnstraßen
k_g
5

Es existieren gerichtete Graphen. Wie in den Kommentaren erwähnt, sind insbesondere gerichtete azyklische Graphen (Directed Acyclic Graphs, DAGs) bei vielen Rechenaufgaben wie dem Kompilieren von Code von großem Nutzen.

Erwähnenswert ist auch, dass die meisten gerichteten Graph-Algorithmen im ungerichteten Fall verwendet werden können, indem einfach jede ungerichtete Kante durch zwei gerichtete Kanten ersetzt wird. Der doppelte Versuch, aus einem ungerichteten Graphen einen gerichteten Graphen zu machen, ist für die meisten Algorithmen nicht möglich.

Cort Ammon - Setzen Sie Monica wieder ein
quelle
3

Die Anfänge der topologischen Sortierung (eine grundlegende Operation für gerichtete azyklische Graphen) liegen in Abhängigkeitsnetzwerken im Projektmanagement, insbesondere der PERT- Methode. Kahn und Lasser zitieren beide PERT in ihren Arbeiten und stützen ihre Beispiele darauf, z

Ein PERT-Netzwerk mit 30.000 Aktivitäten kann in weniger als einer Stunde Maschinenzeit bestellt werden.

Die Online-Auftragsplanung wird immer noch mit diesem Netzwerktyp durchgeführt. Beispielsweise plant ein ETL-System die Ausführung von Jobs erst, nachdem die Jobs ausgeführt wurden, die ihre Eingabedaten bereitstellen.

KWillets
quelle
2

Antwort: Aus dem OP schließe ich, dass die Frage tatsächlich mit SDGs (Signed Directed Graphs) zusammenhängt. Hier ist meine Antwort, die grundlegende gerichtete Graphen behandelt und dann zu SDGs führt.

Gerichtete Graphen werden häufig bei der Fehlerbaumanalyse in industriellen Systemen verwendet. Wenn Sie die Fehlerursachen beseitigen, folgen Sie dem gerichteten Diagramm, um andere Möglichkeiten zu erkunden.

Gerichtete Graphen werden verwendet, um ein kontraproduktives Wiederauffinden von Knoten zu verhindern, die effektiv beseitigt wurden. Bei der Fehlerdiagnose ist häufig die Zeit bis zur Wiederherstellung des Betriebs entscheidend. In komplexen Industrieanlagen gibt es immer einen zeitabhängigen Parallelbaum, der zum Totalausfall des Systems führen kann, wenn der Fehler nicht innerhalb verschiedener Zeitgrenzen behoben wird. Ein Hin- und Herbewegen würde mit größerer Wahrscheinlichkeit zu einem Totalausfall führen, was zu sehr viel zeitaufwendigeren Wiederherstellungsvorgängen führen kann (z. B. zum Entleeren von Tanks und Rohrleitungen, um eine Raffinerie neu zu starten).

Es ist, als würde man einen Ast abschneiden - Sie müssen nicht zum Stamm zurückkehren, wenn Sie versuchen, einen einzelnen Zweig zu finden.

SDGs haben die zusätzliche Eigenschaft, Leitlinien basierend auf Wahrscheinlichkeiten oder Schwellenwerten zu geben, um Entscheidungen zu treffen, wenn der Baum durchquert wird.

Hier ist ein Link zu einem guten Buch zum Thema Fehlererkennung und -diagnose in industriellen Systemen (Seite 224), in dem die Vorteile der SDG-basierten Diagnose beschrieben werden:

https://books.google.com/books?id=KFLlBwAAQBAJ&pg=PA224

SDsolar
quelle