--- title: Graphentheorie date: 2018-10-31 --- Idee: ![Knoten](20181031_1-knoten.png) ![Kante](20181031_1-kante.png) Knoten entsprechen Objekten, Kanten Beziehungen zwischen den Objekten. Was wir nicht erlauben: * Schleifen, d.h. Kanten von einem Konten zu sich selbst ![Schleife](20181031_1-loop.png) * Mehrfache ungerichtete Kanten zwischen zwei Knoten ![Mehrfach ungerichtet](20181031_1-double_undirected.png) # Gerichtete Graphen Hier haben Kanten eine Richtung. ![Gerichteter Graph](20181031_1-dag.png) Bei gerichteten Graphen erlauben wir zwischen zwei Knoten zwei Kanten mit unterschiedlicher Richtung. # Definition (Graph) Sei $V$ eine endliche Menge und $E$ eine Teilmenge von $E \subseteq \binom{V}{2} = \{ \{u,v\} | u,v \in V, u \neq v \}$ (alle 2-elementingen Teilmengen). Ein Graph ist ein Tupel $$ G = (V, E) $$ **Beispiel**: $V = \{1,2,3\}$, $E = \{ \{1,2\}, \{2,3\}, \{1,3\} \}$ ![Beispiel Graph](20181031_1-ex_graph.png) # Definition (Gerichteter Graph; Digraph) Sei $V$ eine endliche Menge und $E \subseteq V \times V = \{ (u,v) | u,v \in E, u \neq v \}$. Ein Digraph ist ein Tupel $G = (V, E)$. **Beispiel**: $V = \{1,2,3\}$, $E = \{ (2,3), (1,2), (3,1), (3,2) \}$ ![Beispiel Digraph](20181031_1-ex_digraph.png) # Wichtige Beispiele von Graphen a) Vollständiger Graph Je zwei Knoten sind miteinander verbunden, d.h. für endliche Menge $V$ mit $|V| = n$ ist $E = \binom{V}{2}$ für $K_n = (V,E)$ ![$K_3$](20181031_1-ex_graph.png) ![$K_4$](20181031_1-k4.png) ![$K_5$](20181031_1-k5.png) b) Kreisgraph $C_n$ ![$C_4$](20181031_1-c4.png) ![$C_5$](20181031_1-c5.png) Allgemein für $V = \{ v_1, ..., v_n \}$ dann ist $E = \{ \{v_i, v_{i+1}\} | i \in \{1,..., n-1\} \} \cup \{v_n, v_1\}$ c) Pfad mit $n$ Knoten $P_n$ ![Pfad](20181031_1-path.png) d) $d$-dimensionaler Würfel $Q_d$ Knoten sind alle Elemente aus $\{0,1\}^d$, $V = \{0,1\} \times ... \times \{0,1\} = \{0,1\}^d$ und es gibt eine Kante zwischen zwei Knoten genau dann, wenn sich die beiden Knoten an genau einer Stelle unterscheiden. # Definition (Benachbart, Randknoten, Nachbarschaft, $k$-regulär) Sei $G = (V, E)$ ein Graph. a) Zwei Knoten $u,v \in V$ heißen *benachbart* oder *adjazent*, falls $e = \{u,v\} \in E$. In diesem Fall heißen $u$ und $v$ *Randknoten* von $e$ oder *inzident* zu $e$ b) Die Nachbarschaft eines Knoten $u \in V$ ist die Menge aller zu $u$ benachbarten Knoten. $$ \Gamma(u) = \{ v \in V | \{u,v\} \in V \} $$ Die Größe der Nachbarschaft eines Knotens $u$ heißt **Grad** von $u$ $$ deg(u) = | \Gamma(u) | $$ c) Ein Graph heißt **$k$-regulär**, falls gilt $deg(u) = k, \forall u \in V$ **Beispiel**: In $Q_2$ sind * $(00)$ und $(01)$ Nachbarn * $\Gamma((00)) = \{(01,10)\}$ * $Q_2$ ist 2-regulär, da $deg(u) = 2, \forall u \in V$ * $Q_d$ ist $d$-regulär * Der Pfad $P_n$ ist nicht regulär # Andere Darstellung eines Graphen a) **Adjazenzmatrix** Wir stellen Nachbarschaftsbeziehungen, d.h. Kanten in Form einer Matrix dar. Genauer sei $G = (V, E)$ ein Graph mit $V = \{v_1, ..., v_n\}$. Die Adjazenzmatrix $A$ ist eine $n \times n$ Matrix $A = (a_{ij})$ wobei $a_{ij} = \begin{cases} 1 & \{v_i, v_j\} \in E \\ 0 & \text{sonst} \end{cases}$ **Beispiel 1**: ![Beispiel Graph](20181031_1-adj_ex.png) $$ A = \left( \begin{matrix} 0 & 1 & 1 & 1 \\ 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 \end{matrix} \right) $$ b) **Inzidenzmatrix** Sei $G = (V,E)$ mit $V = \{v_1, ..., v_n\}$, $E = \{e_1, ..., e_m\}$. Die Inzidenzmatrix $B$ von $G$ ist eine $n \times m$ Matrix $B = (b_{ij})$ wobei $b_{ij} = \begin{cases} 1 & \text{falls } v_i \text{ inzident zu } e_j \\ 0 & \text{sonst} \end{cases}$. **Beispiel 2**: ![Beispiel Graph](20181031_1-inzidenz_ex.png) $$ B = \left(\begin{matrix} 1 & 0 \\ 1 & 1 \\ 0 & 1 \end{matrix}\right) $$ **Bemerkung**: Andere Nummerierung von Knoten und Kanten liefert andere Adjazenz- und Inzidenzmatrix. **Nochmal Beispiel 1 und 2**: In Beispiel 1 gilt $$ deg(1) = 3 \\ deg(2) = 1 \\ deg(3) = 2 \\ deg(4) = 2 $$ Es gilt $deg(1) + deg(2) + deg(3) + deg(4) = 4 \cdot 2 = 8$ und es gibt zwei Knoten mit ungeradem Grad. In Beispiel 2 gilt $$ deg(1) = 1 \\ deg(2) = 2 \\ deg(3) = 1 \\ \\ \sum\limits_{i=1}^3 deg(i) = 4 = 2 \cdot 2 $$ Und es gibt zwei Knoten mit ungeradem Grad. Allgemein gilt: # Satz Sei $G = (V, E)$ ein Graph, dann gilt $\sum\limits_{u \in V} deg(u) = 2 |E|$ # Beweis Durch doppeltes Abzählen der Inzidenzmatrix $B = (b_{ij})$. a) Spaltensumme liefert in jeder Spalte 2. Da es genau $|E|$ Spalten gibt, ist $\sum\limits_{i,j} b_{ij} = 2 |E|$ b) Zeilensumme liefert in Zeile $i$ $deg(v_i)$ und damit insgesamt $\sum\limits_{i,j} b{ij} = \sum\limits_{v \in V} deg(v)$ $$ \tag*{$\Box$} $$ **Folgerung**: Sei $G=(V,E)$ ein Graph. Die Anzahl der Knoten mit ungeradem Grad ist gerade. ## Beweis Wir teilen die Menge $V$ der Knoten in $V_1$ und $V_2$, wobei $$ \begin{align*} V_1 &= \{ v \in V | deg(v) \text{ ist ungerade} \} \\ V_2 &= \{ v \in V | deg(v) \text{ ist gerade} \} \\ \\ V_1 \cup V_2 &= V \\ V_1 \cap V_2 &= \emptyset \end{align*} $$ Es gilt $$ \begin{align*} & \sum\limits_{v \in V} deg(v) &= \sum\limits_{v \in V_1} deg(v) + \sum\limits_{v \in V_2} deg(v) = 2 |E| \\ \Rightarrow & \sum\limits_{v \in V_1} deg(v) &= \underbrace{2 |E| - \sum\limits_{v \in V_2} deg(v)}_\text{gerade} \\ \Rightarrow & \sum\limits_{v \in V_1} deg(v) \text{ ist gerade} \\ \Rightarrow & |V_1| \text{ ist gerade} \end{align*} $$ $$ \tag*{$\Box$} $$ # Definition (Teilgraph/Untergraph) Sei $G=(V,E)$ ein Graph. a) Ein Graph $G' = (V',E')$ heißt Teilgraph von $G$, falls $V' \subseteq V$ und $E' \subseteq E$. b) Ein Teilgraph $G' = (V',E')$ heißt Untergraph von $G$, falls $E' = \{ \{u,v\} | u,v \in V' \land \{u,v\} \in E \} = E \cap \binom{V'}{2}$ **Beispiel**: ![$G$](20181031_1-ex_tg_ug.png) dann ist ![$G$](20181031_1-ex_tg.png) ein Teilgraph von $G$ (aber kein Untergraph) und ![$G$](20181031_1-ex_ug.png) ist ein Untergraph von $G$ **Notation**: Sei $G=(V,E)$ ein Graph und $V' \subseteq V$, $E' \subseteq E$, dann bezeichnet a) $G[V']$ den von $V'$ induzierten Untergraph b) $G \setminus E' = (V, E \setminus E')$ c) $G \setminus V' = (V \setminus V', E) = G[V \setminus V']$