notes/school/di-ma/uebung/08/08_3.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.3}

\begin{enumerate}[1.]

    \item 6 Farben

        \begin{itemize}
            \item jede Farbe genau einmal neben einer anderen
            \item keine gleichen Farben nebeneinander
        \end{itemize}

        man müsste 3 Hamiltonkreise finden mit disjunkten Kanten. Da aber $\forall v \in V$ gilt, dass $deg(v)= 5$ und
        pro Hamiltonkreis zwei Kanten wegfallen, ist der letzte Pfad, nachdem zwei Hamiltonkreise abgelaufen wurden,
        kein Kreis, sprich Startknoten $\neq$ Endknoten

        $\Rightarrow$ Mindestens eine Farbkombination wird nicht erreicht

        $\Rightarrow$ nicht möglich mit 6 Farben

    \item Ungerade Anzahl Farben $\geq 3$.

        \begin{itemize}
            \item zeichne vollständigen Graphen (Knoten $\widehat{=}$ Farben)
            \item wähle beliebigen Startknoten und finde Kamiltonkreise, solange bis kein Hamiltonkreis mehr gefunden
                werden kann
            \item aktualisiere dabei den Graphen, indem die vom Hamiltonkreis genutzten Kanten aus dem Graph entfernt
                werden
            \item falls keine Kante mehr vorhanden (und auch kein Hamiltonkreis mehr), dann sind die gefundenen
                Hamiltonkreise eine mögliche Lösung des Problems.
        \end{itemize}

    % \item Platten $\widehat{=}$ Knoten, Fugen $\widehat{=}$ Kanten. Jeder Knoten hat genau 2 Nachbarn, der Graph $G$
    %     beschreibt einen Kreisgraph $C_n$.

    %     $G$ soll ein Rechteck eingrenzen. Sei $x$ die Höhe und $y$ die Breite des Rechtecks (gemessen in benötigten
    %     Platten). $G$ besteht aus $2*x + 2*y - 2$ Knoten (Platten), was immer eine gerade Zahl ergibt.

    %     In der Vorlesung wurde besprochen, dass jeder Kreisgraph $C_n$ mit einem geraden $n$ eine chromatische Zahl
    %     $\chi(C_n) = 2$ hat.

    %     Da jede Farbe jede andere Farbe genau einmal Nachbar jeder anderen Farbe sein soll, müssen bei $n$ Farben,
    %     Knoten die selbe Farbe haben $n/2$

\end{enumerate}

\end{document}