Erreichbarkeitsproblem in Graphen


Erreichbarkeitsproblem in Graphen

Das Erreichbarkeitsproblem in Graphen (auch STCON, GAP, PATH oder REACH) behandelt die Frage, ob es in einem Graphen einen Weg von einem Knoten s zu einem Knoten t gibt. Existiert solch ein Weg, so ist t von s aus erreichbar. Andernfalls ist t von s aus nicht erreichbar.

Die Abkürzung STCON steht für engl. s-t-Connectivity, GAP für engl. Graph Accessibility Problem und REACH für engl. Reachability. Das analoge Problem für ungerichtete Graphen heißt USTCON.

Das Erreichbarkeitsproblem ist ein NL-vollständiges Problem. Es lässt sich beispielsweise mit Hilfe der Breitensuche oder der Tiefensuche lösen.

Aussagen und Sätze

Beweisidee für STCON ist NL-vollständig

Es ist zu zeigen, dass jedes Problem in NL auf STCON reduziert werden kann und STCON in NL liegt.

  1. Für STCON in NL muss man einen geeigneten Algorithmus angeben. Eine nichtdeterministische Turingmaschine (NTM) rät hierzu den (korrekten) Nachfolgerknoten, um den gesuchten Knoten zu finden. Der Platzverbrauch ist O(1), da lediglich der aktuelle Knoten gespeichert werden muss.
  2. Die Probleme in NL sind solche, die auf logarithmischen Platz von einer NTM gelöst werden können. Eine jede Turingmaschine besitzt einen Konfigurationsgraphen, welcher die verschieden Konfigurationen einer TM beschreibt (die Kopfposition, den Bandinhalt und den Zustand). Der Konfigurationsgraph einer NTM, welcher uns ein Problem in NL löst, ist, da die Mengeninklusion  NL \subseteq P gilt, von maximal polynomieller Größe. Um einen Weg, und damit eine Lösung für ein beliebiges Problem in NL zu finden, müssen wir nun lediglich das folgende Problem lösen: "Gibt es einen Weg vom Anfangszustand zum akzeptierenden Zustand?" Die Lösung für dieses Problem kann uns der oben angegebene Algorithmus liefern.

Quellen


Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Wege, Pfade, Zyklen und Kreise in Graphen — Wege, Pfade, Zyklen und Kreise sind Begriffe der Graphentheorie und beschreiben im Allgemeinen eine spezielle, zusammenhängende Folge von Knoten in einem Graphen. Da die Begriffe eng miteinander verwandt sind, werden sie in diesem… …   Deutsch Wikipedia

  • Disjunkte Wege — Wege, Pfade, Zyklen und Kreise sind Begriffe der Graphentheorie und beschreiben im Allgemeinen eine spezielle, zusammenhängende Folge von Knoten in einem Graphen. Da die Begriffe eng miteinander verwandt sind, werden sie in diesem… …   Deutsch Wikipedia

  • Distanzgraph — Wege, Pfade, Zyklen und Kreise sind Begriffe der Graphentheorie und beschreiben im Allgemeinen eine spezielle, zusammenhängende Folge von Knoten in einem Graphen. Da die Begriffe eng miteinander verwandt sind, werden sie in diesem… …   Deutsch Wikipedia

  • Dreieck (Graphentheorie) — Wege, Pfade, Zyklen und Kreise sind Begriffe der Graphentheorie und beschreiben im Allgemeinen eine spezielle, zusammenhängende Folge von Knoten in einem Graphen. Da die Begriffe eng miteinander verwandt sind, werden sie in diesem… …   Deutsch Wikipedia

  • Dreiecksfreier Graph — Wege, Pfade, Zyklen und Kreise sind Begriffe der Graphentheorie und beschreiben im Allgemeinen eine spezielle, zusammenhängende Folge von Knoten in einem Graphen. Da die Begriffe eng miteinander verwandt sind, werden sie in diesem… …   Deutsch Wikipedia

  • Durchmesser (Graphentheorie) — Wege, Pfade, Zyklen und Kreise sind Begriffe der Graphentheorie und beschreiben im Allgemeinen eine spezielle, zusammenhängende Folge von Knoten in einem Graphen. Da die Begriffe eng miteinander verwandt sind, werden sie in diesem… …   Deutsch Wikipedia

  • Endknoten eines Weges — Wege, Pfade, Zyklen und Kreise sind Begriffe der Graphentheorie und beschreiben im Allgemeinen eine spezielle, zusammenhängende Folge von Knoten in einem Graphen. Da die Begriffe eng miteinander verwandt sind, werden sie in diesem… …   Deutsch Wikipedia

  • Fächer (Graphentheorie) — Wege, Pfade, Zyklen und Kreise sind Begriffe der Graphentheorie und beschreiben im Allgemeinen eine spezielle, zusammenhängende Folge von Knoten in einem Graphen. Da die Begriffe eng miteinander verwandt sind, werden sie in diesem… …   Deutsch Wikipedia

  • Gerichteter Kreis — Wege, Pfade, Zyklen und Kreise sind Begriffe der Graphentheorie und beschreiben im Allgemeinen eine spezielle, zusammenhängende Folge von Knoten in einem Graphen. Da die Begriffe eng miteinander verwandt sind, werden sie in diesem… …   Deutsch Wikipedia

  • Gerichteter Pfad — Wege, Pfade, Zyklen und Kreise sind Begriffe der Graphentheorie und beschreiben im Allgemeinen eine spezielle, zusammenhängende Folge von Knoten in einem Graphen. Da die Begriffe eng miteinander verwandt sind, werden sie in diesem… …   Deutsch Wikipedia