Hamiltonwegproblem
Einfache Sprache
Ziel ist es in einem Gerichteter Graph $G$ einen Hamiltonweg von $s$ nach $t$ zu finden.
Hamiltonwegproblem
Gegeben ein Gerichteter Graph $G=(V,E)$ und zwei Knoten $s,t\in V$. Existiert ein Hamiltonweg von $s$ nach $t$? Es ergibt sich folgende Sprache
$$\mathrm{HAMPATH} = \{\langle G, s, t\rangle\mid G \text{ ist ein gerichteter Graph mit einem Hamiltonweg von $s$ nach $t$}\}$$
Achtung
Es ist nicht bekannt ob HAMPATH in Polynomialzeit lösbar ist.