\section{Implementierung von \textsc{Contract}}
\begin{enumerate}
	\item $G$ nach $H$ kopieren. \hfill $\Oh(1)$
	\item Wenn $\abs{V_H} \leq 2$, dann ist die Zerlegung $\tup{S, T}$ von $G$,
		die den beiden letzen Knoten in $H$ entspricht, das Ergebnis.
		\label{step2}
	\item Wähle eine Zufallszahl $z$ im Intervall $\interval{1; \abs{V_H}}$. \hfill $\Oh(1)$
	\item Nimm den Knoten $a = V_H[z]$ und wähle eine Zufallszahl $z'$ im Intervall $\interval{1, \abs{Adj[a]}}$.

		Nimm den Knoten $b = Adj_{z'}[a]$. \hfill $\Oh(1)$
	\item Bestimme für jeden zu $a$ oder $b$ adjazenten Knoten $c_i$ die Anzahl der Kanten
		zwischen $c_i$ und $a$ oder $b$. \hfill $\Oh(V_H) = \Oh(n)$.
	\item Kontrahiere die Kante $ab$. Lösche dazu die Knoten $a, b$ sowie alle zu $a$ oder $b$ inzidenten Kanten. Da Mehrfachkanten als Zahl implementiert sind, sind
		nur maximal 2 Einträge pro $c_i$ zu löschen. \hfill $\Oh(n)$
		
		Füge einen neuen Knoten $d$ ein. Füge für jeden Knoten $c_i$ die vorher bestimmte Anzahl
		an Kanten zwischen $c_i$ und $a$ oder $b$ als Kanten zwischen $c_i$ und $d$ ein.
		\hfill $\Oh(n)$
	\item Gehe zurück zu \autoref{step2}
\end{enumerate}

Da der Knoten $a$ durch eine gleichverteilte Zufallszahl $z$ ausgewählt wird und der
Knoten $b$ ebenfalls gleichverteilt ausgewählt wird, ist die Kante $ab$ ebenfalls
gleichverteilt ausgewählt.
\points{6}