diff options
Diffstat (limited to 'content/graph/graph.tex')
| -rw-r--r-- | content/graph/graph.tex | 208 |
1 files changed, 111 insertions, 97 deletions
diff --git a/content/graph/graph.tex b/content/graph/graph.tex index eb12cdb..5335967 100644 --- a/content/graph/graph.tex +++ b/content/graph/graph.tex @@ -66,15 +66,42 @@ \sourcecode{graph/treeIsomorphism.cpp} \end{algorithm} -\subsection{Kürzeste Wege} +\begin{algorithm}{DFS} + \input{graph/dfs} +\end{algorithm} -\subsubsection{\textsc{Bellmann-Ford}-Algorithmus} -\method{bellmanFord}{kürzeste Pfade oder negative Kreise finden}{\abs{V}\*\abs{E}} -\sourcecode{graph/bellmannFord.cpp} +\begin{algorithm}{Strongly Connected Components (\textsc{Tarjan})} + \begin{methods} + \method{scc}{berechnet starke Zusammenhangskomponenten}{\abs{V}+\abs{E}} + \end{methods} + \textbf{Info:} SCCs sind in umgekehrter topologischer Reihenfolge! + \sourcecode{graph/scc.cpp} +\end{algorithm} -\subsubsection{Algorithmus von \textsc{Dijkstra}} -\method{dijkstra}{kürzeste Pfade in Graphen ohne negative Kanten}{\abs{E}\*\log(\abs{V})} -\sourcecode{graph/dijkstra.cpp} +\begin{algorithm}{2-SAT} + \sourcecode{graph/2sat.cpp} +\end{algorithm} + +\begin{algorithm}{Artikulationspunkte, Brücken und BCC} + \begin{methods} + \method{find}{berechnet Artikulationspunkte, Brücken und BCC}{\abs{V}+\abs{E}} + \end{methods} + \textbf{Wichtig:} isolierte Knoten und Brücken sind keine BCC. + \sourcecode{graph/articulationPoints.cpp} +\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} + +\subsection{Kürzeste Wege} \subsubsection{\textsc{Floyd-Warshall}-Algorithmus} \method{floydWarshall}{kürzeste Pfade oder negative Kreise finden}{\abs{V}^3} @@ -90,6 +117,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} \cdot b_{k\smash{j}}$ +\subsubsection{\textsc{Bellmann-Ford}-Algorithmus} +\method{bellmanFord}{kürzeste Pfade oder negative Kreise finden}{\abs{V}\*\abs{E}} +\sourcecode{graph/bellmannFord.cpp} + +\subsubsection{Algorithmus von \textsc{Dijkstra}} +\method{dijkstra}{kürzeste Pfade in Graphen ohne negative Kanten}{\abs{E}\*\log(\abs{V})} +\sourcecode{graph/dijkstra.cpp} + \begin{algorithm}{Dynamic Connectivity} \begin{methods} \method{Constructor}{erzeugt Baum ($n$ Knoten, $m$ updates)}{n+m} @@ -99,38 +134,13 @@ Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, da \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)$ - \begin{methods} - \method{havelHakimi}{findet Graph}{(\abs{V}+\abs{E})\cdot\log(\abs{V})} - \end{methods} - \sourcecode{graph/havelHakimi.cpp} -\end{algorithm} -\begin{algorithm}{Strongly Connected Components (\textsc{Tarjan})} - \begin{methods} - \method{scc}{berechnet starke Zusammenhangskomponenten}{\abs{V}+\abs{E}} - \end{methods} - \textbf{Info:} SCCs sind in umgekehrter topologischer Reihenfolge! - \sourcecode{graph/scc.cpp} -\end{algorithm} -\begin{algorithm}{DFS} - \input{graph/dfs} -\end{algorithm} -\begin{algorithm}{Artikulationspunkte, Brücken und BCC} - \begin{methods} - \method{find}{berechnet Artikulationspunkte, Brücken und BCC}{\abs{V}+\abs{E}} - \end{methods} - \textbf{Wichtig:} isolierte Knoten und Brücken sind keine BCC. - \sourcecode{graph/articulationPoints.cpp} -\end{algorithm} -\vfill\null\columnbreak -\begin{algorithm}{2-SAT} - \sourcecode{graph/2sat.cpp} -\end{algorithm} + + + \begin{algorithm}{Maximal Cliques} \begin{methods} @@ -140,17 +150,35 @@ Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, da \sourcecode{graph/bronKerbosch.cpp} \end{algorithm} -\begin{algorithm}{Cycle Counting} +\begin{algorithm}{Maximum Cardinatlity Bipartite Matching} + \label{kuhn} \begin{methods} - \method{findBase}{berechnet Basis}{\abs{V}\cdot\abs{E}} - \method{count}{zählt Zykel}{2^{\abs{\mathit{base}}}} + \method{kuhn}{berechnet Matching}{\abs{V}\*\min(ans^2, \abs{E})} \end{methods} \begin{itemize} - \item jeder Zyklus ist das xor von einträgen in \code{base}. + \item die ersten [0..l) Knoten in \code{adj} sind die linke Seite des Graphen \end{itemize} - \sourcecode{graph/cycleCounting.cpp} + \sourcecode{graph/maxCarBiMatch.cpp} + \columnbreak + \begin{methods} + \method{hopcroft\_karp}{berechnet Matching}{\sqrt{\abs{V}}\*\abs{E}} + \end{methods} + \sourcecode{graph/hopcroftKarp.cpp} +\end{algorithm} + +\vfill\null +\columnbreak + +\begin{algorithm}{Maximum Weight Bipartite Matching} + \begin{methods} + \method{match}{berechnet Matching}{\abs{V}^3} + \end{methods} + \sourcecode{graph/maxWeightBipartiteMatching.cpp} \end{algorithm} +\vfill\null +\columnbreak + \begin{algorithm}{Wert des maximalen Matchings} Fehlerwahrscheinlichkeit: $\left(\frac{m}{MOD}\right)^I$ \sourcecode{graph/matching.cpp} @@ -163,28 +191,8 @@ 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}{Maximum 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..l) Knoten in \code{adj} 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} +\vfill\null +\columnbreak \begin{algorithm}{Global Mincut} \begin{methods} @@ -195,15 +203,31 @@ Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, da \sourcecode{graph/stoerWagner.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}{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} + \subsection{Max-Flow} \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/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/pushRelabel.cpp} } \begin{algorithm}{Min-Cost-Max-Flow} @@ -223,37 +247,27 @@ Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, da \sourcecode{graph/dinicScaling.cpp} \optional{ -\subsubsection{Anwendungen} -\begin{itemize} - \item \textbf{Maximum Edge Disjoint Paths}\newline - 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 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} - \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} - \item \textbf{Min-Cut}\newline - Der maximale Fluss ist gleich dem minimalen Schnitt. - 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} + \subsubsection{Anwendungen} + \begin{itemize} + \item \textbf{Maximum Edge Disjoint Paths}\newline + 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 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} + \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} + \item \textbf{Min-Cut}\newline + Der maximale Fluss ist gleich dem minimalen Schnitt. + 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} } -\begin{algorithm}{Maximum Weight Bipartite Matching} - \begin{methods} - \method{match}{berechnet Matching}{\abs{V}^3} - \end{methods} - \sourcecode{graph/maxWeightBipartiteMatching.cpp} -\end{algorithm} -\vfill\null -\columnbreak - - \begin{algorithm}[optional]{TSP} \begin{methods} \method{TSP}{berechnet eine Tour}{n^2\*2^n} |