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} = \{\langle G, s, t\rangle\mid G \text{ ist ein gerichteter Graph mit einem gerichtetem Kantenzug von $s$ nach $t$}\}$$