75 lines
2.3 KiB
TeX
75 lines
2.3 KiB
TeX
\section{Christofides’ Algorithmus}
|
||
\begin{tasks}
|
||
\item
|
||
Siehe \autoref{fig:christofides}.
|
||
\points{4}
|
||
\item
|
||
Siehe \autoref{fig:checkmate}. Diese Tour kann nicht von \algt{Christofides}
|
||
berechnet werden, denn egal mit welcher Kante in welche Richtung gestartet
|
||
wird, nimmt \algt{Cristofides} immer eine Kante in die Tour, die nicht in
|
||
\autoref{fig:checkmate} ist.
|
||
|
||
\begin{figure}
|
||
\centering
|
||
\includegraphics[page=10, width=0.5\textwidth]{figures.pdf}
|
||
\caption{Eine kleinere TSP-Tour, die von \algt{Cristofides} nicht berechnet werden kann.}
|
||
\label{fig:checkmate}
|
||
\end{figure}
|
||
\points{1}
|
||
\end{tasks}
|
||
|
||
{
|
||
\newpage
|
||
\KOMAoptions{mpinclude=false}
|
||
\recalctypearea
|
||
\begin{figure}
|
||
\centering
|
||
\begin{subfigure}{.3\linewidth}
|
||
\centering
|
||
\includegraphics[page=1, width=0.9\textwidth]{figures.pdf}
|
||
\caption{Der gewichtete, vollständige Graph $G$.}
|
||
\end{subfigure}
|
||
\begin{subfigure}{.3\linewidth}
|
||
\centering
|
||
\includegraphics[page=2, width=0.9\textwidth]{figures.pdf}
|
||
\caption{Minimalen Spannbaum finden.}
|
||
\end{subfigure}
|
||
\begin{subfigure}{.3\linewidth}
|
||
\centering
|
||
\includegraphics[page=3, width=0.9\textwidth]{figures.pdf}
|
||
\caption{Knoten $U$ mit ungeraden Graden finden.}
|
||
\end{subfigure}
|
||
\begin{subfigure}{.3\linewidth}
|
||
\centering
|
||
\includegraphics[page=4, width=0.9\textwidth]{figures.pdf}
|
||
\caption{Minimales, perfektes Matching auf $G[U]$ finden.}
|
||
\end{subfigure}
|
||
\begin{subfigure}{.3\linewidth}
|
||
\centering
|
||
\includegraphics[page=5, width=0.9\textwidth]{figures.pdf}
|
||
\caption{Eulertour konstruieren.}
|
||
\end{subfigure}
|
||
\begin{subfigure}{.3\linewidth}
|
||
\centering
|
||
\includegraphics[page=6, width=0.9\textwidth]{figures.pdf}
|
||
\caption{Eulertour konstruieren.}
|
||
\end{subfigure}
|
||
\begin{subfigure}{.3\linewidth}
|
||
\centering
|
||
\includegraphics[page=7, width=0.9\textwidth]{figures.pdf}
|
||
\caption{Eulertour konstruieren.}
|
||
\end{subfigure}
|
||
\begin{subfigure}{.3\linewidth}
|
||
\centering
|
||
\includegraphics[page=8, width=0.9\textwidth]{figures.pdf}
|
||
\caption{Eulertour konstruieren.}
|
||
\end{subfigure}
|
||
\begin{subfigure}{.3\linewidth}
|
||
\centering
|
||
\includegraphics[page=9, width=0.9\textwidth]{figures.pdf}
|
||
\caption{Schon besuchte Knoten überspringen. TSP vollständig.}
|
||
\end{subfigure}
|
||
\caption{Cristofides' Algorithmus}
|
||
\label{fig:christofides}
|
||
\end{figure}
|
||
}
|