updated tcr

1 files changed, 223 insertions, 78 deletions

diff --git a/graph/graph.tex b/graph/graph.tex
index 37356f6..a26661d 100644
--- a/graph/graph.tex
+++ b/graph/graph.tex
@@ -1,90 +1,192 @@
 \section{Graphen}
 
-% \subsection{Minimale Spannbäume}
+\begin{algorithm}{DFS}
+	\input{graph/dfs}
+\end{algorithm}
 
-% \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.)
+\begin{algorithm}{Minimale Spannbäume}
+	\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.
+\end{algorithm}
 
-% \paragraph{Kreiseigenschaft}
-% Für jeden Kreis $K$ im Graphen gilt:
-% Die schwerste Kante auf dem Kreis ist nicht Teil des minimalen Spannbaums.
+\begin{algorithm}{Kruskal}
+	\begin{methods}[ll]
+		berechnet den Minimalen Spannbaum & \runtime{\abs{E}\cdot\log(\abs{E})} \\
+	\end{methods}
+	\sourcecode{graph/kruskal.cpp}
+\end{algorithm}
+
+\begin{algorithm}{Erd\H{o}s-Gallai}
+	Sei $d_1 \geq \cdots \geq d_{n}$. Es existiert genau dann ein Graph $G$ mit Degreesequence $d$ falls $\sum\limits_{i=1}^{n} d_i$ gerade ist und für $1\leq k \leq n$: $\sum\limits_{i=1}^{k} d_i \leq k\cdot(k-1)+\sum\limits_{i=k+1}^{n} \min(d_i, k)$
+	\begin{methods}
+		\method{havelHakimi}{findet Graph}{(\abs{V}+\abs{E})\cdot\log(\abs{V})}
+	\end{methods}
+	\sourcecode{graph/havelHakimi.cpp}
+\end{algorithm}
+
+\begin{algorithm}{Centroids}
+	\begin{methods}
+		\method{find\_centroid}{findet alle Centroids des Baums (maximal 2)}{\abs{V}}
+	\end{methods}
+	\sourcecode{graph/centroid.cpp}
+\end{algorithm}
+
+\begin{algorithm}{Baum-Isomorphie}
+	\begin{methods}
+		\method{getTreeLabel}{berechnet kanonischen Namen für einen Baum}{\abs{V}}
+	\end{methods}
+	\sourcecode{graph/treeIsomorphism.cpp}
+\end{algorithm}
 
 \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}
-Floyd Warshall:
-\begin{itemize}[nosep]
-	\item Nur negative Werte sollten die Nullen bei Schlingen überschreiben.
-	\item Von parallelen Kanten sollte nur die günstigste gespeichert werden.
-	\item \lstinline{i} liegt genau dann auf einem negativen Kreis, wenn \lstinline{dist[i][i] < 0} ist.
-	\item Wenn für \lstinline{c} gilt, dass \lstinline{dist[u][c] != INF && dist[c][v] != INF && dist[c][c] < 0}, wird der u-v-Pfad beliebig kurz.
-\end{itemize}
+\subsubsection{Algorithmus von \textsc{Dijkstra}}
+\method{dijkstra}{kürzeste Pfade in Graphen ohne negative Kanten}{\abs{E}\*\log(\abs{V})}
+\sourcecode{graph/dijkstra.cpp}
+
+\subsubsection{\textsc{Bellmann-Ford}-Algorithmus}
+\method{bellmanFord}{kürzeste Pfade oder negative Kreise finden}{\abs{V}\*\abs{E}}
+\sourcecode{graph/bellmannFord.cpp}
 
-\subsection{Strongly Connected Components (\textsc{Tarjans}-Algorithmus)}
-\lstinputlisting{graph/scc.cpp}
-
-\subsection{Artikulationspunkte und Brücken}
-\lstinputlisting{graph/articulationPoints.cpp}
-
-\subsection{Eulertouren}
-\begin{itemize}[nosep]
-	\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.
-	\item Algorithmus schlägt nicht fehl, falls kein Eulerzyklus existiert.
-	Die Existenz muss separat geprüft werden.
+\subsubsection{\textsc{Floyd-Warshall}-Algorithmus}
+\method{floydWarshall}{kürzeste Pfade oder negative Kreise finden}{\abs{V}^3}
+\begin{itemize}
+	\item \code{dist[i][i] = 0, dist[i][j] = edge\{j, j\}.weight} oder \code{INF}
+	\item \code{i} liegt auf einem negativen Kreis $\Leftrightarrow$ \code{dist[i][i] < 0}.
 \end{itemize}
-\begin{lstlisting}
-VISIT(v):
-	forall e=(v,w) in E
-	delete e from E
-	VISIT(w)
-	print e
-\end{lstlisting}
-\lstinputlisting{graph/euler.cpp}
-
-\subsection{Lowest Common Ancestor}
-\lstinputlisting{graph/lca.cpp}
+\sourcecode{graph/floydWarshall.cpp}
 
-\subsection{Max-Flow}
+\subsubsection{Matrix-Algorithmus}
+Sei $d_{ij}$ die Distanzmatrix von $G$, dann gibt $d_{ij}^k$ die kürzeste Distanz von $i$ nach $j$ mit maximal $k$ kanten an mit der Verknüpfung: $c_{ij} = a_{ij} * b_{ij} = \min\{a_{ik} + b_{kj}\}$
+
+
+Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, dann gibt $a_{ij}^k$ die Anzahl der Wege von $i$ nach $j$ mit Länge genau \textcolor{gray}{(maximal)} $k$ an mit der Verknüpfung: $c_{ij} = a_{ij} \* b_{ij} = \sum a_{ik} + b_{kj}$
+
+\begin{algorithm}{Artikulationspunkte, Brücken und BCC}
+	\begin{methods}
+		\method{findArticulationPoints}{berechnet Artikulationspunkte,}{\abs{V}+\abs{E}}
+		\method{}{Brücken und BCC}{}
+	\end{methods}
+	\textbf{Wichtig:} isolierte Knoten und Brücken sind keine BCC.
+	\sourcecode{graph/articulationPoints.cpp}
+\end{algorithm}
 
+\begin{algorithm}{Strongly Connected Components (\textsc{Tarjan})}
+	\begin{methods}
+		\method{scc}{berechnet starke Zusammenhangskomponenten}{\abs{V}+\abs{E}}
+	\end{methods}
+	\sourcecode{graph/scc.cpp}
+\end{algorithm}
+
+\begin{algorithm}{2-SAT}
+	\sourcecode{graph/2sat.cpp}
+\end{algorithm}
+
+\begin{algorithm}{Eulertouren}
+	\begin{methods}
+		\method{euler}{berechnet den Kreis}{\abs{V}+\abs{E}}
+	\end{methods}
+	\sourcecode{graph/euler.cpp}
+	\begin{itemize}
+		\item Zyklus existiert, wenn jeder Knoten geraden Grad hat (ungerichtet),\\ bei jedem Knoten Ein- und Ausgangsgrad übereinstimmen (gerichtet).
+		\item Pfad existiert, wenn genau $\{0, 2\}$ Knoten ungeraden Grad haben (ungerichtet),\\ bei allen Knoten Ein- und Ausgangsgrad übereinstimmen oder einer eine Ausgangskante mehr hat (Startknoten) und einer eine Eingangskante mehr hat (Endknoten).
+		\item \textbf{Je nach Aufgabenstellung überprüfen, wie ein unzusammenhängender Graph interpretiert werden sollen.}
+		\item Wenn eine bestimmte Sortierung verlangt wird oder Laufzeit vernachlässigbar ist, ist eine Implementierung mit einem \code{vector<set<int>> adjlist} leichter
+		\item \textbf{Wichtig:} Algorithmus schlägt nicht fehl, falls kein Eulerzyklus existiert.
+		Die Existenz muss separat geprüft werden.
+	\end{itemize}
+\end{algorithm}
+
+\begin{algorithm}{Cycle Counting}
+	\begin{methods}
+		\method{findBase}{berechnet Basis}{\abs{V}\cdot\abs{E}}
+		\method{count}{zählt Zykel}{2^{\abs{\mathit{base}}}}
+	\end{methods}
+	\begin{itemize}
+		\item jeder Zyklus ist das xor von einträgen in \code{base}.
+	\end{itemize}
+	\sourcecode{graph/cycleCounting.cpp}
+\end{algorithm}
+
+\begin{algorithm}{Lowest Common Ancestor}
+	\begin{methods}
+		\method{init}{baut DFS-Baum über $g$ auf}{\abs{V}\*\log(\abs{V})}
+		\method{getLCA}{findet LCA}{1}
+		\method{getDepth}{berechnet Distanz zur Wurzel im DFS-Baum}{1}
+	\end{methods}
+	\sourcecode{graph/LCA_sparse.cpp}
+\end{algorithm}
+
+\begin{algorithm}{Heavy-Light Decomposition}
+	\begin{methods}
+		\method{get\_intervals}{gibt Zerlegung des Pfades von $u$ nach $v$}{\log(\abs{V})}
+	\end{methods}
+	\textbf{Wichtig:} Intervalle sind halboffen
+	
+	Subbaum unter dem Knoten $v$ ist das Intervall  $[\text{\code{in[v]}},~\text{\code{out[v]}})$.
+	\sourcecode{graph/hld.cpp}
+\end{algorithm}
+
+\begin{algorithm}{Dynamic Connectivity}
+	\begin{methods}
+		\method{Constructor}{erzeugt Baum ($n$ Knoten, $m$ updates)}{n+m}
+		\method{addEdge}{fügt Kannte ein,\texttt{id}=delete Zeitpunkt}{\log(n)}
+		\method{eraseEdge}{entfernt Kante \texttt{id}}{\log(n)}
+	\end{methods}
+	\sourcecode{graph/connect.cpp}
+\end{algorithm}
+
+\begin{algorithm}{Global Mincut}
+	\begin{methods}
+		\method{stoer\_wagner}{berechnet globalen Mincut}{\abs{V}^2\*\log(\abs{E})}
+		\method{merge(a,b)}{merged Knoten $b$ in Knoten $a$}{\abs{E}}
+	\end{methods}
+	\textbf{Tipp:} Cut Rekonstruktion mit \code{unionFind} für Partitionierung oder \code{vector<bool>} für edge id's im cut.
+	\sourcecode{graph/stoerWagner.cpp}
+\end{algorithm}
+
+\subsection{Max-Flow}
+\optional{
 \subsubsection{Capacity Scaling}
-Gut bei dünn besetzten Graphen.
-\lstinputlisting{graph/capacityScaling.cpp}
+\begin{methods}
+	\method{maxFlow}{gut bei dünn besetzten Graphen.}{\abs{E}^2\*\log(C)}
+	\method{addEdge}{fügt eine \textbf{gerichtete} Kante ein}{1}
+\end{methods}
+\sourcecode{graph/capacityScaling.cpp}
+}
 
-% \subsubsection{Push Relabel}
-% Gut bei sehr dicht besetzten Graphen.
-% \lstinputlisting{graph/pushRelabel.cpp}
+\subsubsection{Push Relabel}
+\begin{methods}
+	\method{maxFlow}{gut bei sehr dicht besetzten Graphen.}{\abs{V}^2\*\sqrt{\abs{E}}}
+	\method{addEdge}{fügt eine \textbf{gerichtete} Kante ein}{1}
+\end{methods}
+\sourcecode{graph/pushRelabel3.cpp}
 
 \subsubsection{Dinic's Algorithm mit Capacity Scaling}
-Nochmal ca. Faktor 2 schneller als Ford Fulkerson mit Capacity Scaling.
-\lstinputlisting{graph/dinicScaling.cpp}
+\begin{methods}
+	\method{maxFlow}{doppelt so schnell wie Ford Fulkerson}{\abs{V}^2\cdot\abs{E}}
+	\method{addEdge}{fügt eine \textbf{gerichtete} Kante ein}{1}
+\end{methods}
+\sourcecode{graph/dinicScaling.cpp}
 
+\optional{
 \subsubsection{Anwendungen}
-\begin{itemize}[nosep]
+\begin{itemize}
 	\item \textbf{Maximum Edge Disjoint Paths}\newline
 	Finde die maximale Anzahl Pfade von $s$ nach $t$, die keine Kante teilen.
-	\begin{enumerate}[nosep]
+	\begin{enumerate}
 		\item Setze $s$ als Quelle, $t$ als Senke und die Kapazität jeder Kante auf 1.
 		\item Der maximale Fluss entspricht den unterschiedlichen Pfaden ohne gemeinsame Kanten.
 	\end{enumerate}
 	\item \textbf{Maximum Independent Paths}\newline
 	Finde die maximale Anzahl an Pfaden von $s$ nach $t$, die keinen Knoten teilen.
-	\begin{enumerate}[nosep]
+	\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 den unterschiedlichen Pfaden ohne gemeinsame Knoten.
 	\end{enumerate}
@@ -93,26 +195,69 @@ Nochmal ca. Faktor 2 schneller als Ford Fulkerson mit Capacity Scaling.
 	Bei Quelle $s$ und Senke $t$, partitioniere in $S$ und $T$.
 	Zu $S$ gehören alle Knoten, die im Residualgraphen von $s$ aus erreichbar sind (Rückwärtskanten beachten).
 \end{itemize}
+}
 
-\subsection{Min-Cost-Max-Flow}
-\lstinputlisting{graph/minCostMaxFlow.cpp}
+\begin{algorithm}{Min-Cost-Max-Flow}
+	\begin{methods}
+		\method{mincostflow}{berechnet Fluss}{\abs{V}^2\cdot\abs{E}^2}
+	\end{methods}
+	\sourcecode{graph/minCostMaxFlow.cpp}
+\end{algorithm}
 
-\subsection{Maximal Cardinatlity Bipartite Matching}\label{kuhn}
-\lstinputlisting{graph/maxCarBiMatch.cpp}
-\lstinputlisting{graph/hopcroftKarp.cpp}
+\begin{algorithm}{Maximal Cardinatlity Bipartite Matching}
+	\label{kuhn}
+	\begin{methods}
+		\method{kuhn}{berechnet Matching}{\abs{V}\*\min(ans^2, \abs{E})}
+	\end{methods}
+	\begin{itemize}
+		\item die ersten [0..n) Knoten in \code{adjlist} sind die linke Seite des Graphen
+	\end{itemize}
+	\sourcecode{graph/maxCarBiMatch.cpp}
+	\begin{methods}
+		\method{hopcroft\_karp}{berechnet Matching}{\sqrt{\abs{V}}\*\abs{E}}
+	\end{methods}
+	\sourcecode{graph/hopcroftKarp.cpp}
+\end{algorithm}
 
-\subsection{Maximum Weight Bipartite Matching}
-\lstinputlisting{graph/maxWeightBipartiteMatching.cpp}
+\begin{algorithm}{Maximum Weight Bipartite Matching}
+	\begin{methods}
+		\method{match}{berechnet Matching}{\abs{V}^3}
+	\end{methods}
+	\sourcecode{graph/maxWeightBipartiteMatching.cpp}
+\end{algorithm}
 
-\subsection{Wert des maximalen Matchings}
-\lstinputlisting{graph/matching.cpp}
+\begin{algorithm}{Wert des maximalen Matchings}
+	Fehlerwahrscheinlichkeit: $\left(\frac{m}{MOD}\right)^I$
+	\sourcecode{graph/matching.cpp}
+\end{algorithm}
 
-\subsection{2-SAT}
-\lstinputlisting{graph/2sat.cpp}
+\begin{algorithm}{Allgemeines maximales Matching}
+	\begin{methods}
+		\method{match}{berechnet algemeines Matching}{\abs{E}\*\abs{V}\*\log(\abs{V})}
+	\end{methods}
+	\sourcecode{graph/blossom.cpp}
+\end{algorithm}
 
-% \subsection{TSP}
-% \lstinputlisting{graph/TSP.cpp}
+\optional{
+\begin{algorithm}{TSP}
+	\begin{methods}
+		\method{TSP}{berechnet eine Tour}{n^2\*2^n}
+	\end{methods}
+	\sourcecode{graph/TSP.cpp}
+\end{algorithm}
 
-\subsection{Bitonic TSP}
-\lstinputlisting{graph/bitonicTSP.cpp}
+\begin{algorithm}{Bitonic TSP}
+	\begin{methods}
+		\method{bitonicTSP}{berechnet eine Bitonische Tour}{n^2}
+	\end{methods}
+	\sourcecode{graph/bitonicTSPsimple.cpp}
+\end{algorithm}
+}
 
+\begin{algorithm}{Maximal Cliques}
+	\begin{methods}
+		\method{bronKerbosch}{berechnet alle maximalen Cliquen}{3^\frac{n}{3}}
+		\method{addEdge}{fügt \textbf{ungerichtete} Kante ein}{1}
+	\end{methods}
+	\sourcecode{graph/bronKerbosch.cpp}
+\end{algorithm}