From a9d0fb392d56315139a0d2683217bc7a54bd7cce Mon Sep 17 00:00:00 2001
From: mzuenni <michi.zuendorf@gmail.com>
Date: Mon, 21 Apr 2025 13:33:59 +0200
Subject: merge

---
 content/graph/graph.tex | 1 +
 1 file changed, 1 insertion(+)

(limited to 'content/graph/graph.tex')

diff --git a/content/graph/graph.tex b/content/graph/graph.tex
index 213c597..eb12cdb 100644
--- a/content/graph/graph.tex
+++ b/content/graph/graph.tex
@@ -111,6 +111,7 @@ Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, da
 	\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}
 
-- 
cgit v1.2.3


From a5b6a77772a705cccfd25a108a966cc5070d63a3 Mon Sep 17 00:00:00 2001
From: mzuenni <michi.zuendorf@gmail.com>
Date: Mon, 21 Apr 2025 13:28:59 +0200
Subject: moved stuff

---
 content/graph/2sat.cpp         |   4 +-
 content/graph/bellmannFord.cpp |   1 -
 content/graph/graph.tex        | 208 ++++++++++++++++++++++-------------------
 tcr.pdf                        | Bin 698354 -> 698689 bytes
 4 files changed, 112 insertions(+), 101 deletions(-)

(limited to 'content/graph/graph.tex')

diff --git a/content/graph/2sat.cpp b/content/graph/2sat.cpp
index 75e54e6..3e0811f 100644
--- a/content/graph/2sat.cpp
+++ b/content/graph/2sat.cpp
@@ -1,11 +1,9 @@
+constexpr int var(int i) {return i << 1;} // use this!
 struct sat2 {
 	int n; // + scc variablen
 	vector<int> sol;
-
 	sat2(int vars) : n(vars*2), adj(n) {}
 
-	static int var(int i) {return i << 1;} // use this!
-
 	void addImpl(int a, int b) {
 		adj[a].push_back(b);
 		adj[1^b].push_back(1^a);
diff --git a/content/graph/bellmannFord.cpp b/content/graph/bellmannFord.cpp
index 09ea1aa..cadcde7 100644
--- a/content/graph/bellmannFord.cpp
+++ b/content/graph/bellmannFord.cpp
@@ -9,7 +9,6 @@ auto bellmannFord(int n, vector<edge>& edges, int start) {
 				dist[e.to] = dist[e.from] + e.cost;
 				prev[e.to] = e.from;
 	}}}
-
 	for (edge& e : edges) {
 		if (dist[e.from] != INF &&
 		    dist[e.from] + e.cost < dist[e.to]) {
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}
diff --git a/tcr.pdf b/tcr.pdf
index 6b38da9..eb0110f 100644
Binary files a/tcr.pdf and b/tcr.pdf differ
-- 
cgit v1.2.3

