lolhi

\begin{document}
	Zunächst zeigen wir dass LONGEST-PATH $\in$ NP. Sei dazu $(G = (V,E),u,v,k)$ eine LONGEST-PATH Instanz und $v_1$,...,$v_n$ eine geratene Knotenabfolge in $V$. Wir müssen prüfen ob $v_1$,...$v_n$ tatsächlich ein Pfad der Länge $\ge$ k ist. Wir können zunächst in $\mathcal{O}$ ($\vert V \vert$)  überprüfen ob $v_1$,...,$v_l$  und $v_l$ = $w$ sowie ob $l$ $k$. Um zu testen ob alle Knoten $v_i$,$v_j$ für $i$  $j$ verschieden sind prüfen wir alle solchen Paare durch. Dies geht in  $\mathcal{O}$ ($\vert V \vert$)  . Danach müssen wir noch prüfen ob jeweils ($v_i$,$v_i+1$)\in$ E liegt, für $i$ = 1, ...,$l$-1. Dies geht wiederum in $\mathcal{O}$ ($\vert V \vert$ \cdot $\vert E \vert$ ) . Der Gesamtaufwand hierfür ist also $\mathcal{O}$ ($\vert V \vert$($\vert V \vert + $\vert E \vert$)), was polynomiell in der Eingabegröße ist. Damit ist LONGEST-PATH $\in$ NP.
	\\
	Wir zeigen nun durch Reduktion von HAMILTON-PATH Problem dasss LONGEST-PATH NP-vollständig ist. Ist dazu $I = (G=(V,E),u,v,\vert V \vert$) eine Instanz von HAMILTON-PATH, so setzen wir $I\prime$  = $(G=(V,E),u,v \vert V \vert)$ . Wir behaupten dass I $\in$ HAMITON-PATH genau dann wenn $I\prime$ $\in$ LONGEST-PATH. Ist I $\in$ HAMILTON-PATH, dann gibt es einen Pfad der an allen Knoten genau einmal vorkommt und $u$ und $w$ verbindet. Dieser Pfad hat also die Länge $\vert V \vert$.Damit gibt es aber auch einen Longest-Path der Länge $\vert V \vert$ in $G$ der $u$ und $w$ verbindet, also ist $I\prime$ $\in$  LONGEST-PATH . Ist hingegen $I\prime$ $\in$  LONGEST-PATH, dann gibt es einen Pfad $v_l,...,v_\vert V \vert$) der Länge $\vert V \vert$ in welchem kein Knoten zweimal vorkommt und $u$ mit $w$ verbindet. Damit ist dann aber $v_1,...,v_\vert V \vert $ ein Hamilton-Path, da $G$ nur $\vert V \vert$ Knoten besitzt. Also ist $I$ $\in$ HAMILTON-PATH und wir haben gezeigt dass LONGEST-PATH NP-vollständig ist.


\end{document}