diff options
Diffstat (limited to 'graph')
| -rw-r--r-- | graph/graph.tex | 8 |
1 files changed, 4 insertions, 4 deletions
diff --git a/graph/graph.tex b/graph/graph.tex index e9c32c7..4394192 100644 --- a/graph/graph.tex +++ b/graph/graph.tex @@ -71,7 +71,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} @@ -103,7 +103,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})} @@ -223,9 +223,9 @@ 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} |