LaTeX-examples/presentations/ICPC-Referat/Hamiltonkreisproblem.tex

\subsection{Hamiltonkreisproblem}

\begin{frame}{Hamiltonkreisproblem}{Hamiltonian path}
	\begin{block}{Erklärung}
		Ein Hamiltonkreis ist ein Kreis in einem Graphen, in dem jeder Knoten genau einmal benutzt wird.\\

		Das Hamiltonkreisproblem ist NP-vollständig.
	\end{block}
\end{frame}

\begin{frame}{Hamiltonkreisproblem}{Bedingungen und Kriterien (Auszug)}
	\begin{block}{Kriterien (notwendig)}
		\begin{itemize}
			\item G hat keine Schnittknoten
			\item G hat keine Brückenkanten
			\item G hat Minimalgrad $\geq 2$
		\end{itemize}
	\end{block}
	\begin{block}{Bedingungen}
		Bei Graphen G mit $n \geq 3$ Knoten
		\begin{itemize}
			\item G hat Minimalgrad $\frac{n}{2} \Rightarrow$ $\exists $ Hamiltonkreis
			\item G ist vollständig $\Rightarrow \exists$ Hamiltonkreis
			\item G ist Kantengraph eines eulerschen oder hamiltonschen Graphen
		\end{itemize}
	\end{block}
\end{frame}

\begin{frame}{Hamilton- und Eulerkreisproblem}{Anwendungsbeispiel}
	\begin{block}{Gegeben}
		Eine Menge von Wörtern
	\end{block}
	\begin{block}{Gesucht}
		Aneinanderreihung von Wörtern, sodass jeweils Anfangs- und Endbuchstaben gleich sind
		(auch im Ringschluss).
	\end{block}
\end{frame}


\begin{frame}{Hamilton- und Eulerkreisproblem}{Anwendungsbeispiel}
	Wortmenge: $\{$as, man, meet, nets, set, sum, tea, team$\}$

	Menge der Anfangs- und Endbuchstaben: $\{$a, m, n, s, t$\}$
	\begin{figure}
		\begin{tikzpicture}[->,scale=1.3, auto,swap]
			% First we draw the vertices
			\foreach \pos/\name in {{(1,0)/nets}, {(3,0)/set}, {(5,0)/tea},
				                    {(0,2)/man}, {(6,2)/team}, {(1,4)/as},
									{(3,4)/sum}, {(5,4)/meet}}
				\node[vertex] (\name) at \pos {$\name$};
			% Connect vertices with edges and draw weights
			\foreach \source/ \dest /\pos in {nets/set/, nets/sum/, set/tea/, set/team/,
									tea/as/, man/nets/, team/man/, team/meet/, as/set/,
									as/sum/, sum/meet/, sum/man/, meet/team/bend left, meet/tea/}
				\path (\source) edge [\pos] node {} (\dest);
			% Start animating the edge selection.
			% For convenience we use a background layer to highlight edges
			% This way we don't have to worry about the highlighting covering
			% weight labels.
			\begin{pgfonlayer}{background}
				\foreach \source / \dest / \fr / \pos in { as/as/1/, as/sum/2/, sum/man/3/, man/nets/4/,
									nets/set/5/, set/team/6/, team/meet/7/, meet/tea/8/, tea/as/9/}
				    \path<\fr->[selected edge] (\source.center) edge [\pos] node {} (\dest.center);
			\end{pgfonlayer}
		\end{tikzpicture}
	\end{figure}
%		Animierter Graph mit einem Hamiltonkreis. (ohne speziellen Algorithmus?) Wie ausführlich sollen Hamiltonkreise noch genau behandelt werden?
\end{frame}


\begin{frame}{Hamilton- und Eulerkreisproblem}{Anwendungsbeispiel}
	Wortmenge: $\{$as, man, meet, nets, set, sum, tea, team$\}$

	Menge der Anfangs- und Endbuchstaben: $\{$a, m, n, s, t$\}$
	\begin{figure}
		\begin{tikzpicture}[->,scale=1.8, auto,swap]
			% Draw a 7,11 network
			% First we draw the vertices
			\foreach \pos/\name in {{(0,0)/a}, {(0,2)/s},
				                    {(4,0)/m}, {(2,2)/t}, {(3,2)/n}}
				\node[vertex] (\name) at \pos {$\name$};
			% Connect vertices with edges and draw weights
			\tikzstyle{LabelStyle}=[fill=white, fill opacity=0.0, text opacity=1,sloped]
			\foreach \source/ \dest /\foo /\pos in {a/s/as/,s/m/sum/bend right,
										s/t/set/, m/t/meet/bend left,m/n/man/bend right,
										t/a/tea/bend left, t/m/team/bend left, n/s/nets/bend right}
				%\path (\source) edge [\pos] node {\foo} (\dest);
				\Edge[label=\foo,style={\pos}](\source)(\dest);
			% Start animating the edge selection.
			% For convenience we use a background layer to highlight edges
			% This way we don't have to worry about the highlighting covering
			% weight labels.
			\begin{pgfonlayer}{background}
				\foreach \source / \dest / \fr / \pos in {s/s/1/, s/t/2/, t/m/3/bend left, m/n/4/bend right, n/s/5/bend right,
														s/m/6/bend right, m/t/7/bend left, t/a/8/bend left, a/s/9/}
				    \path<\fr->[selected edge] (\source.center) edge [\pos] node {} (\dest.center);
			\end{pgfonlayer}
		\end{tikzpicture}
	\end{figure}
\end{frame}