diff options
| -rw-r--r-- | other/other.tex | 19 | ||||
| -rw-r--r-- | tcr.pdf | bin | 257277 -> 257317 bytes | |||
| -rw-r--r-- | tcr.tex | 2 |
3 files changed, 13 insertions, 8 deletions
diff --git a/other/other.tex b/other/other.tex index 3271542..b0a50f9 100644 --- a/other/other.tex +++ b/other/other.tex @@ -31,33 +31,38 @@ $n$ Personen im Kreis, jeder $k$-te wird erschossen. \subsection{Gemischtes} \begin{itemize} - \item \emph{\textsc{Johnsons} Reweighting Algorithmus:} + \item \textbf{\textsc{Johnsons} Reweighting Algorithmus:} Füge neue Quelle \lstinline{S} hinzu, mit Kanten mit Gewicht 0 zu allen Knoten. Nutze \textsc{Bellmann-Ford} zum Betsimmen der Entfernungen \lstinline{d[i]} von \lstinline{S} zu allen anderen Knoten. Stoppe, wenn es negative Zyklen gibt. Sonst ändere die gewichte von allen Kanten \lstinline{(u,v)} im ursprünglichen Graphen zu \lstinline{d[u]+w[u,v]-d[v]}. Dann sind alle Kantengewichte nichtnegativ, \textsc{Dijkstra} kann angewendet werden. - \item Für ein System von Differenzbeschränkungen: + + \item \textbf{System von Differenzbeschränkungen:} Ändere alle Bedingungen in die Form $a-b \leq c$. Für jede Bedingung füge eine Kante \lstinline{(b,a)} mit Gweicht \lstinline{c} ein. Füge Quelle \lstinline{s} hinzu, mit Kanten zu allen Knoten mit Gewicht 0. Nutze \textsc{Bellmann-Ford}, um die kürzesten Pfade von \lstinline{s} aus zu finden. \lstinline{d[v]} ist mögliche Lösung für \lstinline{v}. - \item Min-Weight-Vertex-Cover im bipartiten Graph: + + \item \textbf{Min-Weight-Vertex-Cover im bipartiten Graph:} Partitioniere in \lstinline{A, B} und füge Kanten \lstinline{s -> A} mit Gewicht \lstinline{w(A)} und Kanten \lstinline{B -> t} mit Gewicht \lstinline{w(B)} hinzu. Füge Kanten mit Kapazität $\infty$ von \lstinline{A} nach \lstinline{B} hinzu, wo im originalen Graphen Kanten waren. Max-Flow ist die Lösung.\newline Im Residualgraphen: - \begin{itemize} + \begin{itemize}[nosep] \item Das Vertex-Cover sind die Knoten inzident zu den Brücken. \emph{oder} \item Die Knoten in \lstinline{A}, die \emph{nicht} von \lstinline{s} erreichber sind und die Knoten in \lstinline{B}, die von \lstinline{erreichber} sind. \end{itemize} - \item Allgemeiner Graph: + + \item \textbf{Allgemeiner Graph:} Das Komplement eines Vertex-Cover ist ein Independent Set. $\Rightarrow$ Max Weight Independent Set ist Komplement von Min Weight Vertex Cover. - \item Bipartiter Graph: + + \item \textbf{Bipartiter Graph:} Min Vertex Cover (kleinste Menge Kanten, die alle Knoten berühren) = Max Matching. - \item Bipartites Matching mit Gewichten auf linken Knoten. + + \item \textbf{Bipartites Matching mit Gewichten auf linken Knoten:} Minimiere Matchinggewicht. Lösung: Sortiere Knoten links aufsteigend nach Gewicht, danach nutze normlen Algorithmus (\textsc{Kuhn}, Seite \pageref{kuhn}) \end{itemize} Binary files differ@@ -22,7 +22,7 @@ % Titlepage with table of contents. \maketitle \setlength{\columnsep}{1cm} -\begin{multicols}{3} +\begin{multicols}{2} \tableofcontents \end{multicols} \newpage |