\section{Graphen}

\subsection{Minimale Spannbäume}
% Add an implementation.
Benutze Algorithmus von \textsc{Kruskal} oder Algorithmus von \textsc{Prim}.

\paragraph{Schnitteigenschaft}
Für jeden Schnitt $C$ im Graphen gilt:
Gibt es eine Kante $e$, die echt leichter ist als alle anderen Schnittkanten, so gehört diese zu allen minimalen Spannbäumen.
($\Rightarrow$ Die leichteste Kante in einem Schnitt kann in einem minimalen Spannbaum verwendet werden.)

\paragraph{Kreiseigenschaft}
Für jeden Kreis $K$ im Graphen gilt:
Die schwerste Kante auf dem Kreis ist nicht Teil des minimalen Spannbaums.

\subsubsection{Kruskal}
\lstinputlisting{graph/kruskal.cpp}

\subsection{Kürzeste Wege}

\subsubsection{Algorithmus von \textsc{Dijkstra}}
Kürzeste Pfade in Graphen ohne negative Kanten.
\lstinputlisting{graph/dijkstra.cpp}

\subsubsection{\textsc{Bellmann-Ford}-Algorithmus}
Kürzestes Pfade in Graphen mit negativen Kanten.
Erkennt negative Zyklen.
\lstinputlisting{graph/bellmannFord.cpp}

\subsubsection{\textsc{Floyd-Warshall}-Algorithmus}
\lstinputlisting{graph/floydWarshall.cpp}
\begin{itemize}
	\item \textsc{Floyd-Warshall} findet auch negative Kreise.
	Es existiert genau dann ein negativer Kreis, wenn \lstinline{dist[i][i] < 0} ist.
	\item \textbf{Evtl. überschreibt die Eingabe die Nullen auf der Hauptdiagonalen.}
	Das ist fast immer ungewollt! 
\end{itemize}

\subsection{Strongly Connected Components (\textsc{Tarjans}-Algorithmus)}
\lstinputlisting{graph/scc.cpp}

% TODO (pjungeblut): This has errors for bridges!
\subsection{Artikulationspunkte und Brücken}
\lstinputlisting{graph/articulationPoints.cpp}

\subsection{Eulertouren}
\begin{itemize}
	\item Zyklus existiert, wenn jeder Knoten geraden Grad hat (ungerichtet), bzw. bei jedem Knoten Ein- und Ausgangsgrad übereinstimmen (gerichtet).
	\item Pfad existiert, wenn alle bis auf (maximal) zwei Knoten geraden Grad haben (ungerichtet), bzw. bei allen Knoten bis auf zwei Ein- und Ausgangsgrad übereinstimmen, wobei einer eine Ausgangskante mehr hat (Startknoten) und einer eine Eingangskante mehr hat (Endknoten).
	\item \textbf{Je nach Aufgabenstellung überprüfen, wie isolierte Punkte interpretiert werden sollen.}
	\item Der Code unten läuft in Linearzeit.
	Wenn das nicht notwenidg ist (oder bestimmte Sortierungen verlangt werden), gehts mit einem \lstinline{set} einfacher.
\end{itemize}
\begin{figure}[h]
	\begin{lstlisting}
	VISIT(v):
		forall e=(v,w) in E
		delete e from E
		VISIT(w)
		print e
	\end{lstlisting}
	\caption{Idee für Eulerzyklen}
\end{figure}
\lstinputlisting{graph/euler.cpp}
\paragraph{Achtung:}
\begin{itemize}
	\item Die Ausgabe erfolgt in falscher Reihenfolge.
	\item Algorithmus schlägt nicht fehl, falls kein Eulerzyklus existiert.
	Die Existenz muss separat geprüft werden.
\end{itemize}

\subsection{Lowest Common Ancestor}
\lstinputlisting{graph/LCA.cpp}

\subsection{Max-Flow}

\subsubsection{Capacity Scaling}
\lstinputlisting{graph/capacityScaling.cpp}

\subsubsection{Maximum Edge Disjoint Paths}
Finde die maximale Anzahl Pfade von $s$ nach $t$, die keine Kante teilen.
\begin{enumerate}
	\item Setze $s$ als Quelle, $t$ als Senke und die Kapazität jeder Kante auf 1.
	\item Der maximale Fluss entspricht der unterschiedlichen Pfade ohne gemeinsame Kanten.
\end{enumerate}

\subsubsection{Maximum Independent Paths}
Finde die maximale Anzahl Pfade von $s$ nach $t$, die keinen Knoten teilen.
\begin{enumerate}
	\item Setze $s$ als Quelle, $t$ als Senke und die Kapazität jeder Kante \emph{und jedes Knotens} auf 1.
	\item Der maximale Fluss entspricht der unterschiedlichen Pfade ohne gemeinsame Knoten.
\end{enumerate}

\subsection{Min-Cost-Max-Flow}
\lstinputlisting{graph/minCostMaxFlow.cpp}

\subsection{Maximal Cardinatlity Bipartite Matching}\label{kuhn}
\lstinputlisting{graph/maxCarBiMatch.cpp}

\subsection{TSP}
\lstinputlisting{graph/TSP.cpp}

\subsection{Bitonic TSP}
\lstinputlisting{graph/bitonicTSP.cpp}