merge

1 files changed, 73 insertions, 60 deletions

diff --git a/graph/graph.tex b/graph/graph.tex
index 6fbdb74..060d157 100644
--- a/graph/graph.tex
+++ b/graph/graph.tex
@@ -1,18 +1,31 @@
 \section{Graphen}
 
-\begin{algorithm}{Eulertouren}
+\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}{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}
+
+\begin{algorithm}{Heavy-Light Decomposition}
 	\begin{methods}
-		\method{euler}{berechnet den Kreis}{\abs{V}+\abs{E}}
+		\method{get\_intervals}{gibt Zerlegung des Pfades von $u$ nach $v$}{\log(\abs{V})}
 	\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>> adj} leichter
-		\item \textbf{Wichtig:} Algorithmus schlägt nicht fehl, falls kein Eulerzyklus existiert.
-		Die Existenz muss separat geprüft werden.
-	\end{itemize}
+	\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}{Lowest Common Ancestor}
@@ -31,16 +44,20 @@
 	\sourcecode{graph/centroid.cpp}
 \end{algorithm}
 
-\begin{algorithm}{Heavy-Light Decomposition}
+\begin{algorithm}{Eulertouren}
 	\begin{methods}
-		\method{get\_intervals}{gibt Zerlegung des Pfades von $u$ nach $v$}{\log(\abs{V})}
+		\method{euler}{berechnet den Kreis}{\abs{V}+\abs{E}}
 	\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}
+	\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>> adj} leichter
+		\item \textbf{Wichtig:} Algorithmus schlägt nicht fehl, falls kein Eulerzyklus existiert.
+		Die Existenz muss separat geprüft werden.
+	\end{itemize}
 \end{algorithm}
-\clearpage
 
 \begin{algorithm}{Baum-Isomorphie}
 	\begin{methods}
@@ -49,24 +66,6 @@
 	\sourcecode{graph/treeIsomorphism.cpp}
 \end{algorithm}
 
-\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}
-
-\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}
-
 \subsection{Kürzeste Wege}
 
 \subsubsection{\textsc{Bellmann-Ford}-Algorithmus}
@@ -91,6 +90,14 @@ Sei $d_{i\smash{j}}$ die Distanzmatrix von $G$, dann gibt $d_{i\smash{j}}^k$ die
 
 Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, dann gibt $a_{i\smash{j}}^k$ die Anzahl der Wege von $i$ nach $j$ mit Länge genau \textcolor{gray}{(maximal)} $k$ an mit der Verknüpfung: $c_{i\smash{j}} = a_{i\smash{j}} \otimes b_{i\smash{j}} = \sum a_{ik} + b_{k\smash{j}}$
 
+\begin{algorithm}{Dynamic Connectivity}
+	\begin{methods}
+		\method{Constructor}{erzeugt Baum ($n$ Knoten, $m$ updates)}{n+m}
+		\method{addEdge}{fügt Kannte ein,\code{id}=delete Zeitpunkt}{\log(n)}
+		\method{eraseEdge}{entfernt Kante \code{id}}{\log(n)}
+	\end{methods}
+	\sourcecode{graph/connect.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)$
@@ -100,13 +107,11 @@ Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, da
 	\sourcecode{graph/havelHakimi.cpp}
 \end{algorithm}
 
-\begin{algorithm}{Dynamic Connectivity}
+\begin{algorithm}{Strongly Connected Components (\textsc{Tarjan})}
 	\begin{methods}
-		\method{Constructor}{erzeugt Baum ($n$ Knoten, $m$ updates)}{n+m}
-		\method{addEdge}{fügt Kannte ein,\code{id}=delete Zeitpunkt}{\log(n)}
-		\method{eraseEdge}{entfernt Kante \code{id}}{\log(n)}
+		\method{scc}{berechnet starke Zusammenhangskomponenten}{\abs{V}+\abs{E}}
 	\end{methods}
-	\sourcecode{graph/connect.cpp}
+	\sourcecode{graph/scc.cpp}
 \end{algorithm}
 
 \begin{algorithm}{DFS}
@@ -121,13 +126,6 @@ Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, da
 	\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}
@@ -139,7 +137,6 @@ Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, da
 	\end{methods}
 	\sourcecode{graph/bronKerbosch.cpp}
 \end{algorithm}
-\clearpage
 
 \begin{algorithm}{Cycle Counting}
 	\begin{methods}
@@ -164,6 +161,14 @@ Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, da
 	\sourcecode{graph/blossom.cpp}
 \end{algorithm}
 
+\begin{algorithm}{Rerooting Template}
+    \sourcecode{graph/reroot.cpp}
+\end{algorithm}
+
+\begin{algorithm}{Virtual Trees}
+    \sourcecode{graph/virtualTree.cpp}
+\end{algorithm}
+
 \begin{algorithm}{Maximal Cardinatlity Bipartite Matching}
 	\label{kuhn}
 	\begin{methods}
@@ -179,13 +184,6 @@ Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, da
 	\sourcecode{graph/hopcroftKarp.cpp}
 \end{algorithm}
 
-\begin{algorithm}{Maximum Weight Bipartite Matching}
-	\begin{methods}
-		\method{match}{berechnet Matching}{\abs{V}^3}
-	\end{methods}
-	\sourcecode{graph/maxWeightBipartiteMatching.cpp}
-\end{algorithm}
-
 \begin{algorithm}{Global Mincut}
 	\begin{methods}
 		\method{stoer\_wagner}{berechnet globalen Mincut}{\abs{V}\abs{E}+\abs{V}^2\*\log(\abs{E})}
@@ -205,12 +203,21 @@ Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, da
 \sourcecode{graph/capacityScaling.cpp}
 }
 
+\optional{
 \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/pushRelabel2.cpp}
+\sourcecode{graph/pushRelabel.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}
 
 \subsubsection{Dinic's Algorithm mit Capacity Scaling}
 \begin{methods}
@@ -218,6 +225,8 @@ Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, da
 	\method{addEdge}{fügt eine \textbf{gerichtete} Kante ein}{1}
 \end{methods}
 \sourcecode{graph/dinicScaling.cpp}
+\vfill*
+\columnbreak
 
 \optional{
 \subsubsection{Anwendungen}
@@ -241,12 +250,15 @@ Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, da
 \end{itemize}
 }
 
-\begin{algorithm}{Min-Cost-Max-Flow}
+\begin{algorithm}{Maximum Weight Bipartite Matching}
 	\begin{methods}
-		\method{mincostflow}{berechnet Fluss}{\abs{V}^2\cdot\abs{E}^2}
+		\method{match}{berechnet Matching}{\abs{V}^3}
 	\end{methods}
-	\sourcecode{graph/minCostMaxFlow.cpp}
+	\sourcecode{graph/maxWeightBipartiteMatching.cpp}
 \end{algorithm}
+\vfill*
+\columnbreak
+
 
 \begin{algorithm}[optional]{TSP}
 	\begin{methods}
@@ -261,3 +273,4 @@ Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, da
 	\end{methods}
 	\sourcecode{graph/bitonicTSPsimple.cpp}
 \end{algorithm}
+