\documentclass[10pt]{article}
\pagenumbering{Roman}

\usepackage{ngerman}
\usepackage{amssymb}
\usepackage{a4wide}

\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\C}{\mathbb{C}}
%\newcommand{\PR}{\mathcal{P}}
%\newcommand{\id}{\mathrm{id}}
%\newcommand{\Hom}{\mathrm{Hom}}
%\newcommand{\End}{\mathrm{End}}
%\newcommand{\Kern}{\mathrm{Kern}}
%\newcommand{\Bild}{\mathrm{Bild}}
%\newcommand{\im}{\mathrm{im}}
%\newcommand{\diag}{\mathrm{diag}}
%
%\newcommand{\aX}[1]{{\sf(#1)}}
%\newcommand{\SP}[2]{\langle\, #1\:\vert\, #2\,\rangle}
%\newcommand{\trivec}[3]{\left(\begin{array}{c}#1\\#2\\#3\\\end{array}\right)}
%\newcommand{\stdvec}[1]{\trivec{#1_1}{#1_2}{#1_3}}
%\newcommand{\pp}{\phantom{-}}

\setlength{\oddsidemargin}{-0.2cm}
\setlength{\evensidemargin}{-0.2cm}
\setlength{\textwidth}{16.4cm} % 21 - 2 * (2.5 - 0.2) = 16.4
\setlength{\parindent}{0pt}
\renewcommand{\arraystretch}{1.2}

\title{\bf Graphentheorie}
\author{Christian M. Meyer}
\date{}

\begin{document}
  \maketitle

  \subsection*{Graphen}
    % DEFINITION
    \paragraph{Definition:}
      Ein {\sf (ungerichteter) Graph} ist ein Tupel $G = (V, E)$ bestehend 
      aus der
      \medskip
    
      \begin{tabular}{p{3cm}l}
        {\sf Knotenmenge} & $V$ und der \\
        {\sf Kantenmenge} & $E \subseteq V \times V$.
      \end{tabular}
    
    % NACHBARSCHAFT UND GRAD
    \paragraph{Nachbarschaft und Grad:} Sei $G = (V, E)$ ein Graph. Die 
      folgenden Operationen sind f\"ur einen beliebigen Knoten $v \in V$
      definiert:
      \medskip
      
      \begin{tabular}{p{3cm}l}
        \sf Nachfolgeknoten:
            & $\mathrm{S}(v) = \{w \in V \mid (v, w) \in E\}$ \\
        \sf Vorg\"angerknoten:
            & $\mathrm{P}(v) = \{w \in V \mid (w, v) \in E\}$ \\
        \sf Nachbarknoten:
            & $\mathrm{N}(v) = \{w \in V \mid (v, w) \in E \vee (w, v) \in E\} 
              = \mathrm{S}(v) \cup \mathrm{P}(v)$ \medskip\\
        \sf Au{\ss}engrad:
            & $\mathrm{d^+}(v) = |\mathrm{S}(v)| \qquad\qquad$ 
              (Anzahl der in $v$ beginnenden Kanten) \\
        \sf Innengrad:
            & $\mathrm{d^-}(v) = |\mathrm{P}(v)| \qquad\qquad$ 
              (Anzahl der in $v$ endenden Kanten) \\
        \sf Grad:
            & $\mathrm{d}(v) = \mathrm{d^+}(v) + \mathrm{d^-}(v)$
      \end{tabular}
      \medskip
      
      Damit gilt: $\quad 2 \sum\limits_{v \in V} \mathrm{d^+}(v) 
      = 2 \sum\limits_{v \in V} \mathrm{d^-}(v) 
      = \sum\limits_{v \in V} \mathrm{d}(v) = 2 \cdot |E|$
      
    % GRAPHEN
    \paragraph{Graphen:} Ein Graph $G = (V, E)$ hei{\ss}t
      \medskip
      
      \begin{tabular}{p{3cm}cl}
        \sf knotenendlich    & $\Leftrightarrow$
            & $|V| < \infty$ \\
        \sf kantenendlich    & $\Leftrightarrow$
            & $|E| < \infty$ \\
        \sf $k$-regul\"ar    & $\Leftrightarrow$ 
            & $\forall\, v \in V.\quad \mathrm{d}(v) = k 
              \quad\qquad$ (mit $k \in \N_0$) \\
        \sf vollst\"andig    & $\Leftrightarrow$ 
            & $\forall\, v, w \in V.\quad (v, w) \in E 
              \quad\Rightarrow\quad |E| = {|V| \cdot (|V| - 1) \over 2}$ \\
        \sf einfach/schlicht & $\Leftrightarrow$ 
            & $G$ hat weder Schlingen noch Mehrfachkanten.
      \end{tabular}
      \medskip
            
      Sei $G' = (V', E')$ ein weiterer Graph. $G'$ hei{\ss}t
      \medskip
      
      \begin{tabular}{p{3cm}cl}
        \sf Teilgraph von $G$    & $\Leftrightarrow$
            & $G' \subseteq G \qquad\Leftrightarrow\qquad V' \subseteq V 
              \;\wedge\; E' \subseteq E$ \\
        \sf Obergraph von $G$    & $\Leftrightarrow$ 
            & $G \subseteq G'$ \\
        \sf Clique von $G$       & $\Leftrightarrow$ 
            & $G' \subseteq G \;\wedge\; G' $ vollst\"andig \\
        \sf Partialgraph von $G$ & $\Leftrightarrow$ 
            & $G' \subseteq G \;\wedge\; 
              E' = \{(v,w) \in E \mid v, w \in V'\} \quad$ 
              (auch: Untergraph von $G$)\\
        \sf isomorph zu $G$      & $\Leftrightarrow$ 
            & $\exists\, \varphi\colon V \longrightarrow V'.\; \varphi $ 
              bijektiv. $\forall\, (v, w) \in E.\; 
              \big(\varphi(v), \varphi(w)\big) \in E'$ \\
      %  \sf invers zu $G$        & $\Leftrightarrow$ 
      %      & $G' = (V, E') \quad $ mit $E' = \{(v, w) \mid (w, v) \in E\}$ \\
      %      && (Meist mit $G^{-1} = (V, E^{-1})$ bezeichnet) \\        
      \end{tabular}
      \medskip
      
      Zu beachten ist, dass die {\sf Inklusion} $\subseteq$ eine 
      Ordnungsrelation auf $G$ bildet.
    
    % KNOTEN  
    \paragraph{Knoten:} Ein Knoten $v \in V$ hei{\ss}t
      \medskip
      
      \begin{tabular}{p{3cm}cl}
        \sf isoliert & $\Leftrightarrow$ & $\mathrm{d}(v) = 0$ \\
        \sf adjazent zu $w \in V$ & $\Leftrightarrow$ & $(v, w) \in E 
            \qquad\qquad$ (auch: $v$ und $w$ sind adjazent)
      \end{tabular}
  
    % KANTEN
    \paragraph{Kanten:} Eine Kante $e = (v, w) \in E$ hei{\ss}t
      \medskip
      
      \begin{tabular}{p{3cm}cll}
        \sf Schlinge       & $\Leftrightarrow$ 
            & $v = w$ \\
        \sf Mehrfachkante  & $\Leftrightarrow$ 
            & $e = (v, w)$ kommt mehrfach in $E$ vor 
            & (auch: Parallele) \\
        \sf inzident zu $u \in V$ & $\Leftrightarrow$ 
            & $u = v \;\vee\; u = w$
            & (auch: $e$ und $u$ sind inzident) \\
      \end{tabular}
      
    % OPERATIONEN
    \paragraph{Operationen:} F\"ur zwei Graphen $G_1 = (V_1, E_1)$ und       
      $G_2 = (V_2, E_2)$ sind folgende Operationen definiert:
      \medskip
      
      \begin{tabular}{p{3cm}l}
        \sf Reduktion:
            & $G_1 \setminus\; G_2 := (V_1 \setminus V_2, E_1 \setminus E_2)$ \\
        \sf Vereinigung:   
            & $G_1 \cup\, G_2 := (V_1 \cup\, V_2, E_1 \cup\, E_2)$ \\
        \sf Schnitt:       
            & $G_1 \cap\, G_2 := (V_1 \cap\, V_2, E_1 \cap\, E_2)$ \\
        \sf Ringsumme:     
            & $G_1 \oplus\, G_2 := \big(V_1 \cup\, V_2, 
              (E_1 \cup\, E_2) \setminus (E_1 \cap\, E_2)\big)$ \\
        \sf Inversion:
            & $G_1^{-1} := (V_1, E_1^{-1}) \quad$ mit 
              $E_1^{-1} := \{(w, v) \mid (v, w)\in E_1\}$
      \end{tabular}
      
    % WEGE
    \paragraph{Wege:} Eine Folge von Knoten $p = (v_1, v_2, \dots, v_n)$ 
      aus $G = (V, E)$
      mit
      $v_i \in V$ f\"ur alle $1 \le i \le n$ hei{\ss}t    
      \medskip
      
      \begin{tabular}{p{3cm}cl}
        \sf Weg/Kantenzug: & $\Leftrightarrow$ 
            & $p = (v_1, v_2, \dots, v_n) \;\wedge\; 
              \forall\, v_i, v_n \in V.\; (v_i, v_{i + 1}) \in E \qquad$ 
              mit $1 \le i < n$ \\
        \sf Kreis/Zyklus:  & $\Leftrightarrow$ 
            & $p$ ist ein Weg $\;\wedge\; v_1 = v_n$      
      \end{tabular}
      \medskip
      
      Ein Weg verbindet also die Knoten $v_1$ und $v_n$, indem die Knoten $v_2,
      \dots, v_{n - 1}$ \"uber die entsprechenden Kanten von $G$ besucht 
      werden. Der Knoten $v_1$ hei{\ss}t hier {\sf Anfangsknoten}, der Knoten 
      $v_2$ {\sf Endknoten} des Weges. Man definiert:
      \medskip
      
      \begin{tabular}{p{3cm}l}
        \sf Wegegraph zu $G$:
            & $G^+ := (V, E^+) \quad$ mit $E^+ := \{(v, w) \in V \times V \mid
              \mbox{es gibt einen Weg von $v$ nach $w$}\}$
      \end{tabular}
      \medskip
      
      Der Wegegraph enth\"alt nur Wege $p$ mit $||p|| \ge 1$. Vereinigt man 
      alle Schlingen mit dem Wegegraphen, ergibt sich die {\sf reflexive und
      transitive H\"ulle} von $G$: 
      $$G^* := (V, E^+ \cup \{(v, v) \mid v \in V\})$$           
      
    % GERICHTETE GRAPHEN
    \paragraph{Gerichtete Graphen:} Ein gerichteter Graph $\vec G = (V, E)$ ist
      ein Graph, dessen Kanten eine Richtung besitzen, folglich gilt nicht 
      l\"anger $(v, w) \in E \;\Rightarrow\; (w, v) \in E$. Die oben 
      eingef\"uhrten Bezeichnungen bleiben erhalten. Der zu $\vec G$ 
      {\sf zugeordnete ungerichtete Graph} wird mit 
      $$\overline G = G \cup G^{-1} = (V, E \cup E^{-1})$$
      
      bezeichnet.
      
    % WEGEIGENSCHAFTEN
    \paragraph{Wegeigenschaften:}
      Ein Weg bzw. Kreis $p = (v_1, v_2, \dots, v_n) \in G^+$ in einem Graphen
      $G = (V, E)$ hei{\ss}t
      \medskip
      
      \begin{tabular}{p{3cm}cl}        
        \sf knoteneinfach  & $\Leftrightarrow$ 
            & $\forall\, i, j \in \N_1^n.\; i \ne j \quad
              \qquad v_i \ne v_j$ \\
        \sf kanteneinfach  & $\Leftrightarrow$ 
            & $\forall\, i, j \in \N_1^{n - 1}.\; i \ne j 
              \qquad v_i \ne v_j \;\wedge\; v_{i + 1} \ne v_{j + 1}$ \\
        \sf knoteneinfach  & $\Leftrightarrow$ 
            & $\forall\, v, w \in p.\; v \ne w$ \\
        \sf kanteneinfach  & $\Leftrightarrow$ 
            & $\forall\, (v_1, v_2), (w_1, w_2) \in p.\; (v_1, v_2) \ne 
              (w_1, w_2)$ mit $v_1 \ne w_1, v_2 \ne w_2$ \\
        \sf eulersch       & $\Leftrightarrow$ 
            & $p$ ist ein kanteneinfacher Zyklus $\;\wedge\quad 
              \forall\, (v, w) \in E.\; (v, w) \in p$ \\
        \sf hamiltonsch    & $\Leftrightarrow$ 
            & $p$ ist ein knoteneinfacher Zyklus $\;\wedge\quad 
              \forall\, v \in V.\; v \in p$ \\
      \end{tabular}
      \medskip
      
      Ein knoteneinfacher Weg ist gleichzeitig ein kanteneinfacher Weg. Ein
      eulerscher Zyklus wird auch als {\sf eulersche Linie (Kreis)} 
      bezeichnet. Entsprechend werden hamiltonsche Zyklen auch
      {\sf hamiltonsche Linie (Kreis)} genannt. Die L\"ange eines Weges gibt 
      die Anzahl der Kanten an, also $||p|| = n - 1$. Zwei Wege $p_1 = (v_1, 
      \dots v_k)$ und $p_2 = (w_1, \dots, w_\ell)$ hei{\ss}en
      \medskip
      
      \begin{tabular}{p{3cm}cl}        
        \sf knotendisjunkt  & $\Leftrightarrow$ 
            & $\forall\, v \in p_1.\; v \not\in p_2$ \\
        \sf kantendisjunkt  & $\Leftrightarrow$ 
            & $\forall\, (v, w) \in p_1.\; (v, w) \not\in p_2$ \\
        \sf konkateniert    & $\Leftrightarrow$ 
            & $p_1 \circ p_2 = (v_1, \dots, v_k, w_1, \dots w_\ell)$
      \end{tabular}
      
    % ZUSAMMENHANG
    \paragraph{Zusammenhang:}
      Sei $G = (V, E)$ und $w \in V$. $G$ hei{\ss}t
      \medskip
      
      \begin{tabular}{p{3cm}cl}        
        \sf zusammenh\"angend & $\Leftrightarrow$ 
            & $\forall\, v, w \in V.\quad v$ ist mit $w$ verbunden. \\
      \end{tabular}
      \medskip
      
      Ein Knoten $v \in V$ hei{\ss}t
      \medskip
      
      \begin{tabular}{p{3cm}cl}        
        \sf verbunden mit $w$ & $\Leftrightarrow$ 
            & $\exists\, p \in G^+.\quad p = (v, \dots, w)$ \\
        \sf Trennknoten & $\Leftrightarrow$ 
            & $G$ zusammenh\"angend $\wedge\; (V \setminus \{v\}, E)$ 
              nicht zusammenh\"angend
      \end{tabular}
      \medskip
      
      Ein Kante $e = (v, w) \in E$ hei{\ss}t
      \medskip
      
      \begin{tabular}{p{3cm}cl}        
        \sf Schnittkante & $\Leftrightarrow$ 
            & $G$ zusammenh\"angend $\wedge\; (V, E \setminus \{e\})$ 
              nicht zusammenh\"angend
      \end{tabular}
      \medskip            
      
      Ein Teilgraph $G' = (V', E') \subseteq G$ hei{\ss}t
      \medskip
      
      \begin{tabular}{p{3cm}cl}        
        \sf Komponente von $G$ & $\Leftrightarrow$ 
            & $G'$ zusammenh\"angend. \\
        \sf Ger\"ust von $G$   & $\Leftrightarrow$ 
            & $G = (V, \widetilde{E})$ \medskip\\
        \sf Trennmenge $\widetilde{V}$:   &
            & $G$ zusammenh\"angend $\wedge$ $(V \setminus \widetilde{V}, E)$
              nicht zusammenh\"angend \\
        \sf Schnittmenge $\widetilde{E}$: &
            & $G$ zusammenh\"angend $\wedge$ $(V, E \setminus \widetilde{E})$
              nicht zusammenh\"angend \\
      \end{tabular}
      \medskip
      
      $G$ hei{\ss}t {\sf mehrfach zusammenh\"angend}, falls 
      $|\widetilde{E}| = 0$ gilt, es also keine Schnittkanten gibt.
    
    % SATZ ÜBER EULERSCHE GRAPHEN  
    \paragraph{Satz \"uber eulersche Graphen:}
      F\"ur einen Graphen $G = (V, E)$ sind \"aquivalent:
      \medskip
      
      \begin{tabular}{p{0.5cm}l}        
        \sf (1) 
            & $G$ ist {\sf eulersch}. \\
%        \sf (2) 
%            & $\exists\, p \in G^+.\; p$ ist eulersch. \\
        \sf (2)
            & $G$ ist zusammenh\"angend und ungerichtet
              $\wedge\; \forall\, v \in V.\quad \mathrm{d}(v)$ ist gerade \\
        \sf (3)
            & $G$ ist zusammenh\"angend und gerichtet \hspace{2ex}
              $\wedge\; \forall\, v \in V.\quad 
              \mathrm{d^+}(v) = \mathrm{d^-}(v)$
      \end{tabular}
      
    % ZYKLEN
    \paragraph{Zyklen:}
      Ein Graph $G = (V, E)$ hei{\ss}t
      \medskip
      
      \begin{tabular}{p{3cm}cl}        
        \sf zyklisch    & $\Leftrightarrow$ 
            & $G$ hat (mindestens) einen Zyklus \\
        \sf azyklisch   & $\Leftrightarrow$ 
            & $G$ hat keinen Zyklus \\
        \sf azyklisch   & $\Rightarrow$
            & $\exists\, v, w \in V.\quad \mathrm{d^+}(v) = 0 
              \;\wedge\; \mathrm{d^-}(w) = 0$
      \end{tabular}
      
    % PLANARITÄT
    \paragraph{Planarit\"at:}
      Sei $G' = (V', E')$. Ein Graph $G = (V, E)$ hei{\ss}t
      \medskip
      
      \begin{tabular}{p{3cm}cl}        
        \sf planar    & $\Leftrightarrow$ 
            & $G$ l\"asst sich ohne Kantenkreuzungen in der Ebene darstellen.\\
        \sf homeomorph zu $G'$ & $\Leftrightarrow$ 
            & $\forall\, v \in V \oplus V'.\quad \mathrm{d}(v) = 2$
      \end{tabular}
      
    % FÄRBBARKEIT
    \paragraph{F\"arbbarkeit:}
      Sei $G = (V, E)$ und $S$ eine Menge von Farben. Eine 
      {\sf Knotenmarkierung} ist gegeben durch 
      $f\colon V \longrightarrow S$. Die Abbildung $f$ hei{\ss}t
      \medskip
      
      \begin{tabular}{p{3cm}cl}        
        \sf F\"arbung    & $\Leftrightarrow$ 
            & $\forall\, v \in V.\; \forall w \in \mathrm{N}(v).\quad
              f(v) \ne f(w)$
      \end{tabular}
      \medskip
      
      Weitere Eigenschaften:
      \medskip
      
      \begin{tabular}{p{3cm}cl}        
        \sf $G$ ist $k$-f\"arbbar & $\Leftrightarrow$
            & $\exists\, f\colon V \longrightarrow S.\quad 
            f$ ist eine F\"arbung von $G \;\wedge\; |S| = k$ \\
        \sf chromatische Zahl: &
            & $\chi(G) = \min\{k \in \N \mid G$ ist $k$-f\"arbbar$\}$ \\
            %& $\chi(G) = \min\{|S| \mid f\colon V \longrightarrow S 
            %  \;\mbox{ist eine F\"arbung von $G$}\}$ \\
        \sf Vierfarbensatz: &
            & $G$ ist planar $\quad\Rightarrow\quad \chi(G) = 4$ \\
        \sf Vollst\"andigkeit &
            & $G$ ist vollst\"andig $\quad\Rightarrow\quad \chi(G) = |V|$
      \end{tabular}
      \medskip
      
      Analog definiert man {\sf Kantenmarkierungen} als eine Abbildung 
      $c\colon V \times V \longrightarrow S$ f\"ur eine beliebige Wertemenge
      $S$. Man nennt $c(e)$ das {\sf Gewicht}, die {\sf Kapazit\"at}
      oder die {\sf Kosten} von $e \in E$.
        
%  \subsection*{B\"aume}
%    \paragraph{Definition:} Ein {\sf Baum} ist ein einfacher azyklischer,
%      zusammenh\"angender Graph $B = (V, E)$. Es gilt $|E| - 1 = |V|$. 
%      F\"ur B\"aume gibt es au{\ss}erdem eine induktive Definition:
%      $\emptyset$ und $\{w\}$ sind B\"aume. Falls $B_i$ B\"aume sind, so 
%      auch $\{v\} \cup \bigcup_{i \in I} B_i$. Die B\"aume $B_i$ hei{\ss}en
%      {\sf Unterb\"aume} von $B$.
%    
%    \paragraph{B\"aume:} Ein Baum $B = (V, E)$ hei{\ss}t
%      \medskip
%      
%      \begin{tabular}{p{3cm}cl}        
%        \sf orientiert/gerichtet & $\Leftrightarrow$ 
%            & $G_B$ gerichtet \\
%        \sf Bin\"arbaum   & $\Leftrightarrow$ 
%            & $\forall\, v \in V.\; \mathrm{d}(v) \le 2$ \\
%        \sf Wurzel         & $\Leftrightarrow$ 
%            & $\mathrm{d}^-(v) = 0$ \\
%      \end{tabular}
%      
%    \paragraph{Knoten:} Ein Knoten $v \in V$ hei{\ss}t
%      \medskip
%      
%      \begin{tabular}{p{3cm}cl}        
%        \sf Wurzel         & $\Leftrightarrow$ 
%            & $\mathrm{d}^-(v) = 0$ \\
%        \sf Blatt          & $\Leftrightarrow$ 
%            & $\mathrm{d}^+(v) = 0$ \\
%        \sf Innerer Knoten & $\Leftrightarrow$
%            & $\mathrm{d}^-(v) \ne 0 \;\wedge\; \mathrm{d}^+(v) \ne 0$
%      \end{tabular}  
%      
%    \paragraph{H\"ohe und Gewicht:} F\"ur einen Baum $B = (V, E)$ mit Wurzel $w \in V$ sowie einem
%      Knoten $v \in V$ ist definiert:
%      \medskip
%      
%      \begin{tabular}{p{3cm}l}      
%        \sf Stufe/Ebene von $v$: & $\mathrm{Level}(v) = ||p||\quad$ mit $p = (w, \dots, v) \in V$ \\
%            & $\mathrm{Level}(w) = 0, \qquad \mathrm{Level}(v) = \mathrm{Level}\big(\mathrm{Pred}(v)\big) + 1$ \\
%        \sf H\"ohe von $B$: & $\mathrm{Height}(B) = \max\limits_{v \in V} \big(\mathrm{Level}(v) + 1\big)$ \\
%        \sf Gewicht von $B$: & $\mathrm{Weight}(B) = |\{v \in V \mid v$ ist ein Blatt $\}|$
%      \end{tabular}
%  
%  \subsection*{Bin\"arb\"aume}
      
\end{document}