agt_exercise/übung_5/aufgabe_2.tex

\section{Hamiltonkreise}
\begin{tasks}
\item
	Ein Kreis hat im allgemeinen mindestens die Länge 3. Da der Turniergraph mindestens
	3 Knoten enthält und stark zusammenhängend ist, liegt jeder Knoten auf einem Kreis
	mit Länge $\geq 3$.
	\points{1}
\item
	Gegeben ist ein Kreis $K$ mit Länge $\geq 3$.
	Um $K$ zu verkleinern wählen wir uns drei aufeinanderfolgende Knoten $a, b, c$ aus.
	Nach Definition gibt es für jedes Knotenpaar eine gerichtete Kante. Wir ersetzen
	jetzt einen Weg der Länge 2 durch eine Kante die nach Annahme existieren muss. Das
	machen wir solange, bis der Kreis die Länge 3 hat.
	
	\points{2}
\item
	\points{1}
\item
	\points{1}
\item
	\points{1}
\item
	\points{1}
\end{tasks}