Handout.tex

\documentclass[a4paper,9pt]{scrartcl}
\usepackage{amssymb, amsmath} % needed for math
\usepackage[utf8]{inputenc} % this is needed for umlauts
\usepackage[ngerman]{babel} % this is needed for umlauts
\usepackage[T1]{fontenc}    % this is needed for correct output of umlauts in pdf
\usepackage[margin=2.5cm]{geometry} %layout
\usepackage{hyperref}   % links im text
\usepackage{color}
\usepackage{framed}
\usepackage{enumerate}  % for advanced numbering of lists
\usepackage{braket} % needed for nice printing of sets
\usepackage{xcolor}
\usepackage{lastpage}
\usepackage{parskip}
\usepackage{csquotes}
\clubpenalty  = 10000   % Schusterjungen verhindern
\widowpenalty = 10000   % Hurenkinder verhindern

\hypersetup{
  pdfauthor   = {Martin Thoma},
  pdfkeywords = {Diskrete Mathematik},
  pdftitle    = {Graphentheorie I: Handout}
}

\usepackage{fancyhdr}
\pagestyle{fancy}
\lhead{Diskrete Mathematik}
\chead{Graphentheorie I (Martin Thoma)}
\rhead{Seite \thepage\ von \pageref{LastPage}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Custom definition style, by                                       %
% http://mathoverflow.net/questions/46583/what-is-a-satisfactory-way-to-format-definitions-in-latex/58164#58164
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\makeatletter
\newdimen\errorsize \errorsize=0.2pt
% Frame with a label at top
\newcommand\LabFrame[2]{%
    \fboxrule=\FrameRule
    \fboxsep=-\errorsize
    \textcolor{FrameColor}{%
    \fbox{%
      \vbox{\nobreak
      \advance\FrameSep\errorsize
      \begingroup
        \advance\baselineskip\FrameSep
        \hrule height \baselineskip
        \nobreak
        \vskip-\baselineskip
      \endgroup
      \vskip 0.5\FrameSep
      \hbox{\hskip\FrameSep \strut
        \textcolor{TitleColor}{\textbf{#1}}}%
      \nobreak \nointerlineskip
      \vskip 1.3\FrameSep
      \hbox{\hskip\FrameSep
        {\normalcolor#2}%
        \hskip\FrameSep}%
      \vskip\FrameSep
    }}%
}}
\definecolor{FrameColor}{rgb}{0.25,0.25,1.0}
\definecolor{TitleColor}{rgb}{1.0,1.0,1.0}

\newenvironment{contlabelframe}[2][\Frame@Lab\ (cont.)]{%
  % Optional continuation label defaults to the first label plus
  \def\Frame@Lab{#2}%
  \def\FrameCommand{\LabFrame{#2}}%
  \def\FirstFrameCommand{\LabFrame{#2}}%
  \def\MidFrameCommand{\LabFrame{#1}}%
  \def\LastFrameCommand{\LabFrame{#1}}%
  \MakeFramed{\advance\hsize-\width \FrameRestore}
}{\endMakeFramed}
\newcounter{definition}
\newenvironment{definition}[1]{%
  \par
  \refstepcounter{definition}%
  \begin{contlabelframe}{Definition \thedefinition:\quad #1}
 \noindent\ignorespaces}
{\end{contlabelframe}}
\makeatother
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Theorem                                                           %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% needed for theorems
\usepackage{amsthm}
\usepackage{thmtools}
\usepackage{changepage}
\newlength\Thmindent
\setlength\Thmindent{20pt}

\newenvironment{precondition}
  {\par\medskip\adjustwidth{\Thmindent}{}\normalfont\textbf{Voraussetzungen:}\par\nobreak}
  {\endadjustwidth}
\newenvironment{claim}
  {\par\medskip\adjustwidth{\Thmindent}{}\normalfont\textbf{Behauptung:}}
  {\endadjustwidth}

\declaretheoremstyle[
  spaceabove=0pt,spacebelow=0pt,
  preheadhook=\adjustwidth{\Thmindent}{},
  prefoothook=\endadjustwidth,
  headpunct=:,
  numbered=no,
  qed=\qedsymbol
]{proof}
\declaretheorem[style=proof,name=Beweis]{Proof}

\theoremstyle{plain}
\newtheorem{theorem}{Satz}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Add some shortcuts                                                %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\usepackage{pifont}% http://ctan.org/pkg/pifont
\newcommand{\cmark}{\ding{51}}% a checkmark
\newcommand{\xmark}{\ding{55}}% a cross
\usepackage{amsmath}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Begin document                                                    %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{document}
\begin{definition}{Graph}
Ein Graph ist ein Tupel $(E, K)$, wobei $E \neq \emptyset$ die Eckenmenge und
$K \subseteq E \times E$ die
Kantenmenge bezeichnet.
\end{definition}

\begin{definition}{Grad einer Ecke}
Der \textbf{Grad} einer Ecke ist die Anzahl der Kanten, die von dieser Ecke
ausgehen.
\end{definition}

\begin{definition}{Isolierte Ecke}
Hat eine Ecke den Grad 0, so nennt man sie \textbf{isoliert}.
\end{definition}

\begin{definition}{Schlinge}
Sei $G=(E, K)$ ein Graph und $k=\Set{e_1, e_2} \in K$ eine Kante.

$k$ heißt \textbf{Schlinge} $:\Leftrightarrow e_1 = e_2$
\end{definition}

\begin{definition}{Inzidenz}
Sei $e \in E$ und $k = \Set{e_1, e_2} \in K$.

$e$ heißt \textbf{inzident} zu $k :\Leftrightarrow e = e_1$ oder $e = e_2$
\end{definition}

\begin{definition}{Vollständiger Graph}
Sei $G = (E, K)$ ein Graph.

$G$ heißt \textbf{vollständig} $:\Leftrightarrow K = E \times E \setminus \Set{\Set{e, e} | e \in E}$
\end{definition}

Ein vollständiger Graph mit $n$ Ecken wird als $K_n$ bezeichnet.

\begin{definition}{Bipartiter Graph}
Sei $G = (E, K)$ ein Graph und $A, B \subset E$ zwei disjunkte Eckenmengen mit
$E \setminus A = B$.

$G$ heißt \textbf{bipartit} $:\Leftrightarrow \forall_{k = \Set{e_1, e_2} \in K}: (e_1 \in A \text{ und } e_2 \in B) \text{ oder } (e_1 \in B \text{ und } e_2 \in A) $
\end{definition}

\begin{definition}{Vollständig bipartiter Graph}
Sei $G = (E, K)$ ein bipartiter Graph und $\Set{A, B}$ bezeichne die Bipartition.

$G$ heißt \textbf{vollständig bipartit} $:\Leftrightarrow A \times B = K$
\end{definition}

\begin{definition}{Kantenzug, Länge eines Kantenzuges und Verbindung von Ecken}
Sei $G = (E, K)$ ein Graph.

Dann heißt eine Folge $k_1, k_2, \dots, k_s$ von Kanten, zu denen es Ecken
$e_0, e_1, e_2, \dots, e_s$ gibt, so dass
\begin{itemize}
    \item $k_1 = \Set{e_0, e_1}$
    \item $k_2 = \Set{e_1, e_2}$
    \item \dots
    \item $k_s = \Set{e_{s-1}, e_s}$
\end{itemize}
gilt ein \textbf{Kantenzug}, der $e_0$ und $e_s$ \textbf{verbindet} und $s$
seine \textbf{Länge}.
\end{definition}

Ein Kantenzug wird durch den Tupel $(e_0, \dots, e_s) \in E^{s+1}$
charakterisiert.

\begin{definition}{Geschlossener Kantenzug}
Sei $G = (E, K)$ ein Graph und $A = (k_1, k_2, \dots, k_s)$ ein Kantenzug
mit $k_1 = \Set{e_0, e_1}$ und $k_s = \Set{e_{s-1}, e_s}$.

A heißt \textbf{geschlossen} $:\Leftrightarrow e_0 = e_s$ .
\end{definition}

\begin{definition}{Weg}
Sei $G = (E, K)$ ein Graph und $A = (k_1, k_2 \dots, k_s)$ ein Kantenzug.

A heißt \textbf{Weg} $:\Leftrightarrow \forall_{i, j \in 1, \dots, s}: i \neq j \Rightarrow k_i \neq k_j$ .
\end{definition}

\begin{definition}{Kreis}
Sei $G = (E, K)$ ein Graph und $A = (k_1, k_2 \dots, k_s)$ ein Kantenzug.

A heißt \textbf{Kreis} $:\Leftrightarrow A$ ist geschlossen und ein Weg.
\end{definition}

\vspace{0.5cm}
\begin{theorem}{Aufgabe 5}
    ~~~
    \begin{precondition}
        Sei $G = (E, K)$ ein Graph, in dem jede Ecke min. Grad 2 hat.
    \end{precondition}
    \begin{claim}
        Es ex. ein Kreis $C$ in $G$ mit $|C| > 0$
    \end{claim}
    \begin{Proof} In den Folien.
    \end{Proof}
\end{theorem}
\vspace{0.5cm}

\begin{definition}{Zusammenhängender Graph}
Sei $G = (E, K)$ ein Graph.

$G$ heißt \textbf{zusammenhängend} $:\Leftrightarrow \forall e_1, e_2 \in E: $
Es ex. ein Kantenzug, der $e_1$ und $e_2$ verbindet
\end{definition}

\begin{definition}{Eulerscher Kreis}
Sei $G$ ein Graph und $A$ ein Kreis in $G$.

$A$ heißt \textbf{eulerscher Kreis} $:\Leftrightarrow \forall_{k \in K}: k \in A$.
\end{definition}

\begin{definition}{Eulerscher Graph}
Ein Graph heißt \textbf{eulersch}, wenn er einen eulerschen Kreis enthält.
\end{definition}
\vspace{0.5cm}
\begin{theorem}{Euler 1736}
    ~~~
    \begin{precondition}
        Sei $G = (E, K)$ ein Graph.
    \end{precondition}
    \begin{claim}
        Wenn ein Graph $G$ eulersch ist, dann hat jede Ecke von $G$ geraden Grad.
    \end{claim}
    \begin{Proof} Direkt\\
        Sei $C = (e_0, \dots, e_n, e_0) \in E^{n+2}$ ein Eulerkreis in $G$
        $\Rightarrow $ Es gilt: $\forall e \in E\;\exists i \in \Set{0, \dots, n}: e = e_i$ und alle Kanten aus $G$ sind genau ein einziges Mal in $C$.\\
        Außerdem gilt:
        \[\text{Grad}(e_i) = \begin{cases}
            2 \cdot \text{Anzahl der Vorkommen von } e_i \text{ in } C & \text{falls } i\neq 0\\
            2 \cdot (\text{Anzahl der Vorkommen von } e_i \text{ in } C -1)  & \text{falls } i = 0\\
        \end{cases}
        \]
        $\Rightarrow \forall e \in E: \text{Grad}(e)$ ist gerade
    \end{Proof}
\end{theorem}
\vspace{0.5cm}
\begin{theorem}{Umkehrung des Satzes von Euler}
    ~~~
    \begin{precondition}
        Sei $G = (E, K)$ ein zusammenhängender Graph.
    \end{precondition}
    \begin{claim}
        Wenn jede Ecke von $G$ geraden Grad hat, dann ist $G$ eulersch.
    \end{claim}
    \begin{Proof} über Induktion über Anzahl $m$ der Kanten\\
        \underline{I.A.:} $m=0$: $G$ ist eulersch. \cmark\\
        $m=1$: Es gibt keinen Graphen in dem jede Ecke geraden Grad hat. \cmark\\
        $m=2$: Nur ein Graph ist zusammenhängend, hat zwei Kanten und nur Ecken geraden Grades. Dieser ist eulersch. \cmark
        \goodbreak
        \underline{I.V.:} Sei $m \in \mathbb{N}_0$ beliebig, aber fest und
        es gelte:

        Für alle zusammenhängenden Graphen $G$ mit höchstens $m$ Kanten, bei denen jede Ecke geraden Grad hat, ist $G$ eulersch.

        \underline{I.S.:} Sei $G=(E,K)$ mit $2 \leq m  = |K|$ ein zusammenhängender Graph, der nur Ecken geraden Grades hat.\\
        $\Rightarrow$ Jede Ecke von $G$ hat min. Grad 2.
        $\stackrel{A5}{\Rightarrow}$ Es gibt einen Kreis $C$ in $G$.\\

        Sei nun
            \[G_C = (E_C, K_C) \text{ mit } E_C \subseteq E \text{ und } K_C \subseteq K \]
        der Graph, der durch $C$ induziert wird.
        Sei

            \[ G^* = (E, K \setminus K_C) \]

        Es gilt:
        \begin{itemize}
            \item Jede Ecke in $G^*$ hat geraden Grad.
            \item Jede Zusammenhangskomponente hat weniger als $m$ Knoten.
            \item[$\Rightarrow$] I.V. ist auf jede Zusammenhangskomponente anwendbar.
            \item[$\Rightarrow$] Jede Zusammenhangskomponente hat einen Eulerkreis.
            \item[$\Rightarrow$] Der Kreis $C$ kann durch die Eulerkreise erweitern werden. So erhält man insgesamt einen Eulerkreis.
        \end{itemize}
        $\Rightarrow$ $G$ ist eulersch.
    \end{Proof}
\end{theorem}
\vspace{0.5cm}

\begin{definition}{Offene eulersche Linie}
Sei $G$ ein Graph und $A$ ein Weg, der kein Kreis ist.

$A$ heißt \textbf{offene eulersche Linie} von $G :\Leftrightarrow$ Jede Kante
in $G$ kommt genau ein mal in $A$ vor.
\end{definition}
\vspace{0.5cm}
\begin{theorem}{}
    ~~~
    \begin{precondition}
        Sei $G = (E, K)$ ein zusammenhängender Graph.
    \end{precondition}
    \begin{claim}
        $G$ hat eine offene eulersche Linie $:\Leftrightarrow G$ hat genau zwei Ecken ungeraden Grades
    \end{claim}
    \begin{Proof} Direkt von \enquote{$\Rightarrow$}; Rückrichtung \enquote{$\Leftarrow$} analog\\
        Sei $L=(e_0, \dots, e_s)$ in $G$  eine offene eulersche Linie in $G$.\\
        $\Leftrightarrow G^* = (E, K \cup \Set{e_s, e_0})$ hat einen Eulerkreis.\\
        $\Leftrightarrow G^*$ hat nur Knoten geraden Grades.\\
        $\Leftrightarrow G$ hat genau zwei Knoten ($e_0, e_s$) ungeraden Grades.
    \end{Proof}
\end{theorem}

\vfill
Alle \LaTeX-Quellen und die neueste Version der PDF sind unter

\href{https://github.com/MartinThoma/LaTeX-examples/tree/master/presentations/Diskrete-Mathematik}{github.com/MartinThoma/LaTeX-examples/tree/master/presentations/Diskrete-Mathematik}

zu finden
\end{document}