Erreichbarkeitsproblem in Graphen

Einfache Sprache

Def. Erreichbarkeitsproblem in Graphen

Gegeben ein Gerichteter Graph $G=(V,E)$ und zwei Knoten $s,t\in V$. Existiert ein Gerichteter Kantenzug von $s$ nach $t$? Es ergibt sich folgende Sprache

$$\mathrm{PATH} = \mathrm{STCON} = \{\langle G, s, t\rangle\mid G \text{ ist ein gerichteter Graph mit einem gerichtetem Kantenzug von $s$ nach $t$}\}$$

Das Komplement von $\mathrm{PATH}$ ist das Unerreichbarkeitsproblem in Graphen.

Säzte

• Satz PATH is NL-vollständig
• Satz PATH ist in P
• Satz NL ist gleich coNL Hier wird PATH verwendet.