130 lines
3.9 KiB
TeX
130 lines
3.9 KiB
TeX
\documentclass[12pt,a4paper,german]{article}
|
|
\usepackage{url}
|
|
%\usepackage{graphics}
|
|
\usepackage{times}
|
|
\usepackage[T1]{fontenc}
|
|
\usepackage{ngerman}
|
|
\usepackage{float}
|
|
\usepackage{diagbox}
|
|
\usepackage[utf8]{inputenc}
|
|
\usepackage{geometry}
|
|
\usepackage{amsfonts}
|
|
\usepackage{amsmath}
|
|
\usepackage{cancel}
|
|
\usepackage{wasysym}
|
|
\usepackage{csquotes}
|
|
\usepackage{graphicx}
|
|
\usepackage{epsfig}
|
|
\usepackage{paralist}
|
|
\usepackage{tikz}
|
|
\geometry{left=2.0cm,textwidth=17cm,top=3.5cm,textheight=23cm}
|
|
|
|
%%%%%%%%%% Fill out the the definitions %%%%%%%%%
|
|
\def \name {Valentin Brandl} %
|
|
\def \matrikel {108018274494} %
|
|
\def \pname {Marvin Herrmann} %
|
|
\def \pmatrikel {108018265436} %
|
|
\def \gruppe {2 (Mi 10-12 Andre)}
|
|
\def \qname {Pascal Brackmann}
|
|
\def \qmatrikel {108017113834} %
|
|
\def \uebung {8} %
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
|
|
% DO NOT MODIFY THIS HEADER
|
|
\newcommand{\hwsol}{
|
|
\vspace*{-2cm}
|
|
\noindent \matrikel \quad \name \hfill \"Ubungsgruppe: \gruppe \\
|
|
\noindent \pmatrikel \quad \pname \\
|
|
\noindent \qmatrikel \quad \qname \\
|
|
\begin{center}{\Large \bf L\"osung f\"ur \"Ubung \# \uebung}\end{center}
|
|
}
|
|
|
|
\begin{document}
|
|
%Import header
|
|
\hwsol
|
|
|
|
\section*{Aufgabe 8.2}
|
|
|
|
Gerichtete Kante $\widehat{=}$ Sieg des Ausgangsknoten
|
|
|
|
\begin{enumerate}[1.]
|
|
|
|
\item Kanten $\begin{cases}
|
|
1: Schere \\
|
|
2: Stein \\
|
|
3: Papier \\
|
|
4: Axt
|
|
\end{cases}$
|
|
|
|
Mit 4 Symbolen:
|
|
|
|
\begin{figure}[h!]
|
|
\centering
|
|
\includegraphics{build/school/di-ma/uebung/08/08_2_1.png}
|
|
\end{figure}
|
|
|
|
$\Rightarrow$ zwei Symbole können jeweils nur gegen genau ein anderes Symbol gewinnen.
|
|
|
|
$\Rightarrow$ $A = \left( \begin{matrix}
|
|
0 & 1 & -1 & -1 \\
|
|
-1 & 0 & -1 & 1 \\
|
|
1 & 1 & 0 & -1 \\
|
|
1 & -1 & 1 & 0
|
|
\end{matrix}\right)$
|
|
|
|
\item mit 5 Symbolen: $\begin{cases}
|
|
1: rock \\
|
|
2: paper \\
|
|
3: scissors \\
|
|
4: spock \\
|
|
5: lizard
|
|
\end{cases}$
|
|
|
|
\begin{figure}[h!]
|
|
\centering
|
|
\includegraphics{build/school/di-ma/uebung/08/08_2_2.png}
|
|
\end{figure}
|
|
|
|
$\Rightarrow$ $A = \left(\begin{matrix}
|
|
0 & 1 & -1 & 1 & -1 \\
|
|
-1 & 0 & 1 & -1 & 1 \\
|
|
1 & -1 & 0 & 1 & -1 \\
|
|
-1 & 1 & -1 & 0 & 1 \\
|
|
1 & -1 & 1 & -1 & 0
|
|
\end{matrix}\right)$
|
|
|
|
$\Rightarrow$ Anhand der Adjazenzmatrix lässt sich ablesen, ob ein Spiel ausgewogen definiert wurde, d.h. bei
|
|
einem ausgewogenen Spiel ist die Anzahl Aus- und Eingehender Kanten in einen Knoten identisch (Anzahl von $1$
|
|
und $-1$ in jeder Zeile gleich)
|
|
|
|
$\Rightarrow$ dies ist genau der Fall, wenn eine ungerade Anzahl an Symbolen existiert
|
|
|
|
Verfahren:
|
|
|
|
\begin{enumerate}[i.]
|
|
|
|
\item Zeichne den gerichteten Graphen, der die aktuellen Regeln abbildet. Knoten $\widehat{=}$ Symbole,
|
|
gerichtete Kante: Ursprungsknoten $=$ \enquote{verliert gegen}, Zielknoten $=$ \enquote{gewinnt gegen}.
|
|
|
|
\item Füge 2 neue Symbole hinzu (Knoten)
|
|
|
|
\item \label{new_old} Füge eine gerichtete Kante von einem neuen Knoten zu einem alten Knoten ein, zu dem
|
|
noch keine Kante vorhanden ist, und gehe diese entlang zum alten Knoten
|
|
|
|
\item \label{old_new} Füge eine gerichtete Kante vom Knoten zu einem neu hinzugefügten Knoten ein, to dem
|
|
noch keine Kante
|
|
besteht
|
|
|
|
\item Wiederhole iii) und iv) bis keine neuen Kanten mehr hinzugefügt werden können
|
|
|
|
\item verfollständige den Hamiltonkreis im äußeren Ring
|
|
|
|
\item Wiederhole ii), falle die Anzahl neuer Symbole $> 2$ ist, jedoch muss die Anzahl von Symbolen
|
|
$(|S_{alt}| + |S_{neu}|) \mod 2 = 1$ betragen
|
|
|
|
\end{enumerate}
|
|
|
|
\end{enumerate}
|
|
|
|
\end{document}
|