Quelltext der Seite Erreichbarkeitsproblem in Graphen

__NOTOC__
Das '''Erreichbarkeitsproblem in Graphen''' (auch STCON bzw. USTCON, GAP, PATH oder REACH) behandelt die Frage, ob es in einem [[Graph (Graphentheorie)|Graphen]] einen [[Weg (Graphentheorie)|Weg]] von einem Knoten <math>s</math> zu einem Knoten <math>t</math> gibt. Existiert solch ein Weg, so ist <math>t</math> von <math>s</math> aus '''erreichbar'''. Andernfalls ist <math>t</math> von <math>s</math> 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 [[gerichteter Graph|gerichteten Graphen]]. In dieser Variante ist es ein [[NL-Vollständigkeit| NL-vollständiges]] Problem.
* Die Abkürzung USTCON steht für engl. ''undirected s-t-Connectivity'' und bezeichnet das Erreichbarkeitsproblem in einem [[ungerichteter Graph|ungerichteten Graphen]]. In dieser Variante ist es ein [[L (Komplexitätsklasse)|L-komplexes]] Problem.

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

== Aussagen und Sätze ==
* In [[ungerichteter Graph|ungerichteten]] Graphen ist jeder Knoten von jedem anderen Knoten aus genau dann erreichbar, wenn der Graph [[zusammenhängender Graph|zusammenhängend]] ist.
* In [[Gerichteter Graph|gerichteten]] Graphen ist dies genau dann der Fall, wenn der Graph [[stark zusammenhängender Graph|stark zusammenhängend]] ist.
* Das Problem STCON ist [[NL-Vollständigkeit|NL-vollständig]].
* Das Problem STCON ist in <math>DSPACE(o(log (n)^2))</math> ([[Satz von Savitch]])
* Das Problem USTCON liegt in der Komplexitätsklasse [[L (Komplexitätsklasse)|L]].

=== 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.
# 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 <math>|V|</math> hochzählt (nach jedem Schritt). Der Platzverbrauch ist <math>\mathcal{O}(log (n))</math>, da lediglich der aktuelle Knoten gespeichert werden muss und der Zähler auch nur <math>\mathcal{O}(log(n))</math> Speicher benötigt.
# 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 <math> NL \subseteq P </math> 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.

== Literatur ==
* {{Literatur |Autor=Eric Allender |Titel=Reachability Problems: An Update |Hrsg=S. B. Cooper, B. Löwe, A. Sorbi |Sammelwerk=Computation and Logic in the Real World. CiE 2007 |Reihe=Lecture Notes in Computer Science |BandReihe=4497 |Datum=2007 |Verlag=Springer |ISBN=978-3-540-73001-9 |DOI=10.1007/978-3-540-73001-9_3 |Online=https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&doi=e486aea347c9d0b9e256319741d968128516620c}}

== Quellen ==
* Christos H. Papadimitriou: ''Computational Complexity''. Addison-Wesley, ISBN 978-0-201-53082-7

[[Kategorie:Problem (Graphentheorie)]]
[[Kategorie:Komplexitätstheorie]]