1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
|
\section{Graphen}
\subsection{Minimale Spannbäume}
\paragraph{Schnitteigenschaft}
Für jeden Schnitt $C$ im Graphen gilt:
Gibt es eine Kante $e$, die echt leichter ist als alle anderen Schnittkanten, so gehört diese zu allen minimalen Spannbäumen.
($\Rightarrow$ Die leichteste Kante in einem Schnitt kann in einem minimalen Spannbaum verwendet werden.)
\paragraph{Kreiseigenschaft}
Für jeden Kreis $K$ im Graphen gilt:
Die schwerste Kante auf dem Kreis ist nicht Teil des minimalen Spannbaums.
\subsubsection{Kruskal}
\lstinputlisting{graph/kruskal.cpp}
\subsection{Kürzeste Wege}
\subsubsection{Algorithmus von \textsc{Dijkstra}}
Kürzeste Pfade in Graphen ohne negative Kanten.
\lstinputlisting{graph/dijkstra.cpp}
\subsubsection{\textsc{Bellmann-Ford}-Algorithmus}
Kürzestes Pfade in Graphen mit negativen Kanten.
Erkennt negative Zyklen.
\lstinputlisting{graph/bellmannFord.cpp}
\subsubsection{\textsc{Floyd-Warshall}-Algorithmus}
\lstinputlisting{graph/floydWarshall.cpp}
\begin{itemize}[nosep]
\item Nur negative Werte sollten die Nullen überschreiben.
\item Von parallelen Kanten sollte nur die günstigste gespeichert werden.
\item \lstinline{i} liegt genau dann auf einem negativen Kreis, wenn \lstinline{dist[i][i] < 0} ist.
\item Wenn für \lstinline{c} gilt, dass \lstinline{dist[u][c] != INF && dist[c][v] != INF && dist[c][c] < 0}, wird der u-v-Pfad beliebig kurz.
\end{itemize}
\subsection{Strongly Connected Components (\textsc{Tarjans}-Algorithmus)}
\lstinputlisting{graph/scc.cpp}
% TODO (pjungeblut): This has errors for bridges!
\subsection{Artikulationspunkte und Brücken}
\lstinputlisting{graph/articulationPoints.cpp}
\subsection{Eulertouren}
\begin{itemize}[nosep]
\item Zyklus existiert, wenn jeder Knoten geraden Grad hat (ungerichtet), bzw. bei jedem Knoten Ein- und Ausgangsgrad übereinstimmen (gerichtet).
\item Pfad existiert, wenn alle bis auf (maximal) zwei Knoten geraden Grad haben (ungerichtet), bzw. bei allen Knoten bis auf zwei Ein- und Ausgangsgrad übereinstimmen, wobei einer eine Ausgangskante mehr hat (Startknoten) und einer eine Eingangskante mehr hat (Endknoten).
\item \textbf{Je nach Aufgabenstellung überprüfen, wie isolierte Punkte interpretiert werden sollen.}
\item Der Code unten läuft in Linearzeit.
Wenn das nicht notwenidg ist (oder bestimmte Sortierungen verlangt werden), gehts mit einem \lstinline{set} einfacher.
\item Algorithmus schlägt nicht fehl, falls kein Eulerzyklus existiert.
Die Existenz muss separat geprüft werden.
\end{itemize}
\begin{lstlisting}
VISIT(v):
forall e=(v,w) in E
delete e from E
VISIT(w)
print e
\end{lstlisting}
\lstinputlisting{graph/euler.cpp}
\subsection{Lowest Common Ancestor}
\lstinputlisting{graph/LCA.cpp}
\subsection{Max-Flow}
\subsubsection{Capacity Scaling}
Gut bei dünn besetzten Graphen.
\lstinputlisting{graph/capacityScaling.cpp}
\subsubsection{Push Relabel}
Gut bei sehr dicht besetzten Graphen.
\lstinputlisting{graph/pushRelabel.cpp}
\subsubsection{Dinic's Algorithm mit Capacity Scaling}
Nochmal ca. Faktor 2 schneller als Ford Fulkerson mit Capacity Scaling.
\lstinputlisting{graph/dinicScaling.cpp}
\subsubsection{Anwendungen}
\begin{itemize}[nosep]
\item \textbf{Maximum Edge Disjoint Paths}\newline
Finde die maximale Anzahl Pfade von $s$ nach $t$, die keine Kante teilen.
\begin{enumerate}[nosep]
\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}[nosep]
\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}
\subsection{Min-Cost-Max-Flow}
\lstinputlisting{graph/minCostMaxFlow.cpp}
\subsection{Maximal Cardinatlity Bipartite Matching}\label{kuhn}
\lstinputlisting{graph/maxCarBiMatch.cpp}
\lstinputlisting{graph/hopcroftKarp.cpp}
\subsection{2-SAT}
\lstinputlisting{graph/2sat.cpp}
% \subsection{TSP}
% \lstinputlisting{graph/TSP.cpp}
\subsection{Bitonic TSP}
\lstinputlisting{graph/bitonicTSP.cpp}
|
