diff options
Diffstat (limited to 'graph/graph.tex')
| -rw-r--r-- | graph/graph.tex | 39 |
1 files changed, 30 insertions, 9 deletions
diff --git a/graph/graph.tex b/graph/graph.tex index 6fbdb74..bcfe689 100644 --- a/graph/graph.tex +++ b/graph/graph.tex @@ -15,7 +15,7 @@ \end{itemize} \end{algorithm} -\begin{algorithm}{Lowest Common Ancestor} +\begin{algorithm}[optional]{Lowest Common Ancestor} \begin{methods} \method{init}{baut DFS-Baum über $g$ auf}{\abs{V}\*\log(\abs{V})} \method{getLCA}{findet LCA}{1} @@ -24,6 +24,17 @@ \sourcecode{graph/LCA_sparse.cpp} \end{algorithm} +\begin{algorithm}{Binary Lifting} + % https://codeforces.com/blog/entry/74847 + \begin{methods} + \method{Lift}{constructor}{\abs{V}} + \method{depth}{distance to root of vertex $v$}{1} + \method{lift}{vertex above $v$ at depth $d$}{\log(\abs{V})} + \method{lca}{lowest common ancestor of $u$ and $v$}{\log(\abs{V})} + \end{methods} + \sourcecode{graph/binary_lifting.cpp} +\end{algorithm} + \begin{algorithm}{Centroids} \begin{methods} \method{find\_centroid}{findet alle Centroids des Baums (maximal 2)}{\abs{V}} @@ -40,7 +51,15 @@ Subbaum unter dem Knoten $v$ ist das Intervall $[\text{\code{in[v]}},~\text{\code{out[v]}})$. \sourcecode{graph/hld.cpp} \end{algorithm} -\clearpage +\columnbreak + +\begin{algorithm}[optional]{DP rerooting} + \sourcecode{graph/reroot.cpp} +\end{algorithm} + +\begin{algorithm}[optional]{Virtual trees} + \sourcecode{graph/virtualTree.cpp} +\end{algorithm} \begin{algorithm}{Baum-Isomorphie} \begin{methods} @@ -60,7 +79,7 @@ Die schwerste Kante auf dem Kreis ist nicht Teil des minimalen Spannbaums. \end{algorithm} -\begin{algorithm}{Kruskal} +\begin{algorithm}{\textsc{Kruskal}} \begin{methods}[ll] berechnet den Minimalen Spannbaum & \runtime{\abs{E}\cdot\log(\abs{E})} \\ \end{methods} @@ -92,7 +111,7 @@ 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}{Erd\H{o}s-Gallai} +\begin{algorithm}{\textsc{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})} @@ -128,6 +147,8 @@ Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, da \sourcecode{graph/scc.cpp} \end{algorithm} +\columnbreak + \begin{algorithm}{2-SAT} \sourcecode{graph/2sat.cpp} \end{algorithm} @@ -139,7 +160,7 @@ Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, da \end{methods} \sourcecode{graph/bronKerbosch.cpp} \end{algorithm} -\clearpage +\columnbreak \begin{algorithm}{Cycle Counting} \begin{methods} @@ -197,7 +218,7 @@ Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, da \subsection{Max-Flow} \optional{ -\subsubsection{Capacity Scaling} +\subsubsection{Capacity Scaling \opthint} \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} @@ -212,15 +233,15 @@ Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, da \end{methods} \sourcecode{graph/pushRelabel2.cpp} -\subsubsection{Dinic's Algorithm mit Capacity Scaling} +\subsubsection{\textsc{Dinic}'s Algorithm mit Capacity Scaling} \begin{methods} - \method{maxFlow}{doppelt so schnell wie Ford Fulkerson}{\abs{V}^2\cdot\abs{E}} + \method{maxFlow}{doppelt so schnell wie \textsc{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} +\subsubsection{Anwendungen \opthint} \begin{itemize} \item \textbf{Maximum Edge Disjoint Paths}\newline Finde die maximale Anzahl Pfade von $s$ nach $t$, die keine Kante teilen. |