Erreichbarkeitsproblem in Graphen

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

Das Erreichbarkeitsproblem in Graphen (auch STCON bzw. USTCON, GAP, PATH oder REACH) behandelt die Frage, ob es in einem Graphen einen Weg von einem Knoten zu einem Knoten gibt. Existiert solch ein Weg, so ist von aus erreichbar. Andernfalls ist von aus nicht erreichbar. GAP steht für engl. Graph Accessibility Problem und REACH für engl. Reachability.

  • Die Abkürzung STCON steht für engl. s-t-Connectivity und bezeichnet das Erreichbarkeitsproblem in einem gerichteten Graphen. In dieser Variante ist es ein NL-vollständiges Problem.
  • Die Abkürzung USTCON steht für engl. undirected s-t-Connectivity und bezeichnet das Erreichbarkeitsproblem in einem ungerichteten Graphen. In dieser Variante ist es ein L-komplexes Problem.

Es lässt sich beispielsweise mit Hilfe der Breitensuche oder der Tiefensuche lösen.

Aussagen und Sätze[Bearbeiten | Quelltext bearbeiten]

Beweisidee für STCON ist NL-vollständig[Bearbeiten | Quelltext bearbeiten]

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. Zusätzlich pflegt man noch einen binären Zähler, der bis maximal hochzählt (nach jedem Schritt). Der Platzverbrauch ist , da lediglich der aktuelle Knoten gespeichert werden muss und der Zähler auch nur Speicher benötigt.
  2. Die Probleme in NL sind solche, die auf logarithmischem Platz von einer NTM gelöst werden können. Eine jede Turingmaschine besitzt einen Konfigurationsgraphen, welcher die verschiedenen 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 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[Bearbeiten | Quelltext bearbeiten]