Pfad (Graphentheorie)

Für die Familie der als Pfade bekannten Grafiken siehe Pfadgrafik.
Ein dreidimensionales Hypercube -Diagramm zeigen a Hamiltonianischer Weg rot und a längste induzierte Pfad fett schwarz.

Im Graphentheorie, a Weg in einem Graph ist ein endlich oder unendlich Reihenfolge von Kanten das verbindet eine Sequenz von Eckpunkte die nach den meisten Definitionen alle unterschiedlich sind (und da die Eckpunkte unterschiedlich sind, sind auch die Kanten). EIN gerichteter Weg (manchmal genannt Dipath[1]) in einem gerichteter Graph ist eine endliche oder unendliche Sequenz von Kanten, die eine Sequenz verschiedener Scheitelpunkte verbindet, aber mit der zusätzlichen Einschränkung, dass die Kanten alle in die gleiche Richtung gerichtet sind.

Pfade sind grundlegende Konzepte der Graphentheorie, die in den Einführungsabschnitten der meisten Texte der Graphentheorie beschrieben werden. Siehe z. Bondy und Murty (1976), Gibbons (1985) oder Diestel (2005). Korte et al. (1990) decken fortgeschrittener ab Algorithmisch Themen zu Pfaden in Grafiken.

Definitionen

Walk, Trail und Pfad

Trail but not path.svg
Lassen G = (V, E, ϕ) eine Grafik sein. Ein endlicher Spaziergang ist eine Abfolge von Kanten (e1, e2,…, en - 1) für die es eine Sequenz von Eckpunkten gibt (v1, v2,…, vn) so dass ϕ(ei) = {vi, vi + 1} zum i = 1, 2,…, n - 1. (v1, v2,…, vn) ist der Scheitelpunktsequenz des Spaziergangs. Der Spaziergang ist abgeschlossen wenn v1 = vn, und es ist offen Andernfalls. Ein unendlicher Wander Strahl) hat einen ersten Scheitelpunkt, aber keinen letzten Scheitelpunkt.
  • A Pfad ist ein Spaziergang, bei dem alle Kanten unterschiedlich sind.[2]
  • A Weg ist eine Spur, in der alle Scheitelpunkte (und damit auch alle Kanten) unterschiedlich sind.[2]

Wenn w = (e1, e2,…, en - 1) ist ein endlicher Spaziergang mit Scheitelpunktsequenz (v1, v2,…, vn) dann w soll ein sein Gehen Sie von v1 zu vn. Ähnlich für einen Weg oder einen Weg. Wenn es einen endlichen Spaziergang zwischen zwei gibt unterscheidbar Scheitelpunkte dann gibt es auch einen endlichen Pfad und einen endlichen Weg zwischen ihnen.

Einige Autoren benötigen nicht, dass alle Scheitelpunkte eines Pfades unterschiedlich sind und stattdessen den Begriff verwenden Einfacher Weg sich auf einen solchen Pfad beziehen, auf dem alle Scheitelpunkte unterschiedlich sind.

A gewichtete Grafik assoziiert einen Wert (Gewicht) mit jeder Kante in der Grafik. Das Spaziergang (oder Weg oder Pfad) In einem gewichteten Diagramm befindet sich die Summe der Gewichte der durchquerten Kanten. Manchmal die Worte kosten oder Länge werden anstelle von Gewicht verwendet.

Gerichteter Walk, Regieweg und gerichteter Weg

  • A gerichteter Walk ist ein endlich oder unendlich Reihenfolge von Kanten in die gleiche Richtung gerichtet, die eine Sequenz von verbindet Eckpunkte.[2]
Lassen G = (V, E, ϕ) Seien Sie eine gerichtete Grafik. Ein endlich gerichteter Walk ist eine Abfolge von Kanten (e1, e2,…, en - 1) für die es eine Sequenz von Eckpunkten gibt (v1, v2,…, vn) so dass ϕ(ei) = ((vi, vi + 1) zum i = 1, 2,…, n - 1. (v1, v2,…, vn) ist der Scheitelpunktsequenz des gerichteten Spaziergangs. Der gerichtete Spaziergang ist abgeschlossen wenn v1 = vn, und es ist offen Andernfalls. Ein unendlich gerichteter Walk ist eine Abfolge von Kanten des hier beschriebenen Typs, jedoch ohne den ersten oder letzten Scheitel Strahl) hat einen ersten Scheitelpunkt, aber keinen letzten Scheitelpunkt.
  • A Regiespur ist ein gerichteter Spaziergang, bei dem alle Kanten unterschiedlich sind.[2]
  • A gerichteter Weg ist ein gerichteter Weg, auf dem alle Scheitelpunkte unterschiedlich sind.[2]

Wenn w = (e1, e2,…, en - 1) ist ein endlicher gerichteter Spaziergang mit Scheitelpunktsequenz (v1, v2,…, vn) dann w soll ein sein Gehen Sie von v1 zu vn. Ähnlich für einen gerichteten Weg oder einen Weg. Wenn es einen endlich gerichteten Spaziergang zwischen zwei gibt unterscheidbar Scheitelpunkte dann gibt es auch einen endlich gerichteten Weg und einen endlichen gerichteten Weg zwischen ihnen.

Einige Autoren benötigen nicht, dass alle Scheitelpunkte eines gerichteten Pfades unterschiedlich sind und stattdessen den Begriff verwenden Einfacher gerichteter Weg sich auf einen solchen gerichteten Pfad beziehen.

A Gewichtete Graph assoziiert einen Wert (Gewicht) mit jeder Kante in der gerichteten Grafik. Das Gewicht eines gerichteten Spaziergangs (oder Weg oder Pfad) In einem gewichteten Graphen ist die Summe der Gewichte der durchquerten Kanten. Manchmal die Worte kosten oder Länge werden anstelle von Gewicht verwendet.

Beispiele

  • Ein Diagramm ist in Verbindung gebracht Wenn Wege mit jedem Eckpaar enthalten.
  • Eine gerichtete Grafik ist stark verbunden Wenn es entgegengesetzt orientierte gerichtete Pfade gibt, die jedes Eckpaar enthalten.
  • Ein Pfad, so dass keine Grafikkanten zwei nicht aufeinanderfolgende Pfadscheitelpunkte verbinden, wird als eine genannt induzierter Weg.
  • Ein Pfad, der jeden Scheitelpunkt des Diagramms ohne Wiederholungen enthält Hamiltonianischer Weg.
  • Zwei Wege sind Scheitelpunkt-unabhängig (Alternative, Interne Scheitelpunkt-Disjoint) Wenn sie keinen internen Scheitelpunkt gemeinsam haben. Ebenso sind zwei Pfade kantenunabhängig (oder Randdisjoint) Wenn sie keine interne Kante gemeinsam haben. Zwei interne Vertex-Disjoint-Pfade sind Edge-Disjoint, aber das Gegenteil ist nicht unbedingt wahr.
  • Das Distanz Zwischen zwei Scheitelpunkten in einem Diagramm liegt die Länge eines kürzesten Weges zwischen ihnen, wenn einer existiert, und ansonsten ist der Abstand unendlich.
  • Der Durchmesser eines verbundenen Graphen ist der größte Abstand (oben definiert) zwischen Eckpunktpaaren des Graphen.

Pfade finden

Es gibt mehrere Algorithmen, die es finden, um zu finden kürzeste und am längsten Wege in Graphen mit der wichtigen Unterscheidung, dass das erstere Problem rechnerisch einfacher ist als der letztere.

Dijkstra -Algorithmus erzeugt eine Liste der kürzesten Pfade von einem Quellscheitelpunkt zu jedem anderen Scheitelpunkt in gerichteten und ungerichteten Graphen mit nicht negativen Kantengewichten (oder ohne Kantengewichte), während die Bellman -.ford -Algorithmus Kann auf gerichtete Graphen mit negativen Kantengewichten angewendet werden. Das Floyd -Warshall -Algorithmus Kann verwendet werden, um die kürzesten Pfade zwischen allen Eckpaaren in gewichteten gerichteten Graphen zu finden.

Siehe auch

Verweise

  1. ^ Graph-Struktur-Theorie: Proceedings der AMS-IMS-SIAM Joint Summer Research Conference on Graph Minderjährige, von 22. Juni bis 5. Juli 1991, abgehalten, S.205
  2. ^ a b c d e f Bender & Williamson 2010, p. 162.
  • Bender, Edward A.; Williamson, S. Gill (2010). Listen, Entscheidungen und Grafiken. Mit einer Einführung in die Wahrscheinlichkeit.
  • Bondy, J. A.; Murty, U. S. R. (1976). Graphentheorie mit Anwendungen. North Holland. p.12-21. ISBN 0-444-19451-7.
  • Diestel, Reinhard (2005). Graphentheorie. Springer-Verlag. S. 6–9. ISBN 3-540-26182-6.
  • Gibbons, A. (1985). Algorithmische Graphentheorie. Cambridge University Press. S. 5–6. ISBN 0-521-28881-9.
  • Korte, Bernhard; Lovász, László; Prömel, Hans Jürgen; Schrijver, Alexander (1990). Pfade, Strömungen und VLSI-Layout. Springer-Verlag. ISBN 0-387-52685-4.