From ed2cdb7ff56664d2447301802e574c9289ca4e3f Mon Sep 17 00:00:00 2001 From: Gloria Mundi Date: Sat, 16 Nov 2024 22:05:24 +0100 Subject: cosmetic changes --- content/other/other.tex | 12 ++++++------ 1 file changed, 6 insertions(+), 6 deletions(-) (limited to 'content/other/other.tex') diff --git a/content/other/other.tex b/content/other/other.tex index 9f8cfce..153fc2d 100644 --- a/content/other/other.tex +++ b/content/other/other.tex @@ -125,7 +125,7 @@ c'(u,v)&=c(u,v)-d(u,v)&c'(t,s)&=x \end{align*} Löse Fluss auf $G'$ mit \textsc{Dinic's Algorithmus}, wenn alle Kanten von $s'$ saturiert sind ist der Fluss in $G$ gültig. $x$ beschränkt den Fluss in $G$ (Binary-Search für minflow, $\infty$ sonst). - \item \textbf{\textsc{Johnsons} Reweighting Algorithmus:} + \item \textbf{\textsc{Johnson}s Reweighting Algorithm:} Initialisiere alle Entfernungen mit \texttt{d[i] = 0}. Berechne mit \textsc{Bellmann-Ford} kürzeste Entfernungen. Falls es einen negativen Zyklus gibt abrrechen. Sonst ändere die Gewichte von allen Kanten \texttt{(u,v)} im ursprünglichen Graphen zu \texttt{d[u]+w[u,v]-d[v]}. @@ -184,8 +184,8 @@ [X/G] = \frac{1}{\vert G \vert} \sum_{g \in G} m^{\#(g)} \] - \item \textbf{Verteilung von Primzahlen:} - Für alle $n \in \mathbb{N}$ gilt: Ex existiert eine Primzahl $p$ mit $n \leq p \leq 2n$. + \item \textbf{\textsc{Bertrand}sches Postulat:} + Für alle $n \in \mathbb{N}$ gilt: Ex existiert eine Primzahl $p$ mit $n < p \leq 2n$. \item \textbf{Satz von \textsc{Kirchhoff}:} Sei $G$ ein zusammenhängender, ungerichteter Graph evtl. mit Mehrfachkanten. @@ -197,7 +197,7 @@ \newline Entferne letzte Zeile und Spalte und berechne Betrag der Determinante. - \item \textbf{\textsc{Dilworths}-Theorem:} + \item \textbf{\textsc{Dilworth}'s Theorem:} Sei $S$ eine Menge und $\leq$ eine partielle Ordnung ($S$ ist ein Poset). Eine \emph{Kette} ist eine Teilmenge $\{x_1,\ldots,x_n\}$ mit $x_1 \leq \ldots \leq x_n$. Eine \emph{Partition} ist eine Menge von Ketten, sodass jedes $s \in S$ in genau einer Kette ist. @@ -211,13 +211,13 @@ Falls $x \leq y$, füge Kante $u_x \to v_y$ hinzu. Wenn Matching zu langsam ist, versuche Struktur des Posets auszunutzen und evtl. anders eine maximale Antikette zu finden. - \item \textbf{\textsc{Turan}'s-Theorem:} + \item \textbf{\textsc{Turan}'s Theorem:} Die Anzahl an Kanten in einem Graphen mit $n$ Knoten der keine clique der größe $x+1$ enthält ist: \begin{align*} ext(n, K_{x+1}) &= \binom{n}{2} - \left[\left(x - (n \bmod x)\right) \cdot \binom{\floor{\frac{n}{x}}}{2} + \left(n\bmod x\right) \cdot \binom{\ceil{\frac{n}{x}}}{2}\right] \end{align*} - \item \textbf{\textsc{Euler}'s-Polyedersatz:} + \item \textbf{\textsc{Euler}scher Polyedersatz:} In planaren Graphen gilt $n-m+f-c=1$. \item \textbf{\textsc{Pythagoreische Tripel}:} -- cgit v1.2.3