---
title: Bäume
date: 2018-11-06
---

Bäume sollen zusammenhängende Graphen sein. Mit minimaler Anzahl von Kanten bei
gegebener Knotenmenge, d.h. $|E| = |V| - 1$. Solche Graphen können keine Kreise
enthalten.

# Definition (Baum, Wald, Blatt)

a) Ein **Baum** ist ein kreisfreier, zusammenhängender Graph
a) Ein **Wald** ist ein Grpah mit Zusammenhangskomponenten, die Bäume sind.
a) ein **Blatt** ist ein Knoten $u$ in einem Baum $T=(V,E)$ mit $deg(u) = 1$.
Knoten, die keine Blätter sind, heißen innere Knoten

$$
\tag*{$\Box$}
$$


**Beispiel**

![Baum](20181106_2-tree.png)

Ist ein Baum. Blätter $2,5,6$

![Wald](20181106_2-forest.png)


# Lemma

a) Ein Baum mit mindestens 2 Knoten hat mindestens 2 Blätter.

a) In einem Baum gibt es zwischen je 2 Knoten genau einen Pfad.

a) Sei $T=(V,E)$ ein Baum, dann hat $T\setminus \{v\}$ für $v\in V$ genau
$deg(v)$ Zusammenhangskomponenten.


# Beweis (Lemma)

a) Da es mindestens 2 Konten $u,v$ gibt, gibt es auch mindestens 1 Kante
${u,v}$ mit $u,v \in V$. Gehe in jeder Richtung den Baum entlang, bis wir in
einer Sackgasse enden. diese beiden Endpunkte sind Blätter. Da es keine Kreise
gibt, muss die Sackgasse erreicht werden.

a) Gäbe es 2 Pfade, dann auch einen Kreis. Widerspruch zu "kreisfrei"

a) jetzt nicht


# Satz

Für jeden Baum $T = (V,E)$ gilt $|E| = |V| - 1$

# Beweis

Wir nehmen an, der Satz sei falsch. Sei $T_0 = (V_0, E_0)$ ein Gegenbeispiel
mit minimaler Anzahl von Knoten, d.h. es gilt $|E_0| \neq |V_0|-1$ und für alle
Bäume $T=(V,E)$ mit weniger als $|V_0|$ Knoten gilt $|E|=|V|-1$.

Es gilt sicher $|V_0| \geq 2$, dann gibt es in $T_0$ nach Lemma a) mindestens 2
Blätter $u, v$.

Betrachte $T' = T_0 \setminus \{u\}$. Da $u$ Blatt gilt $deg(u) = 1$ und laut
Lemma c) hat $T'$ $deg(u)=1$ viele Zusammenhangskomponenten, d.h. $T'$ ist
zusammenhängend und kreisfrei.

$\Rightarrow T'$ ist ein Baum mit $T' = (V',E')$ mit $V' = V\setminus \{u\}$,
$E' = E \setminus \{u, u'\}$, wobei $u'$ der (eindeutige) mit $u$ benachbarte
Knoten ist.

Da $|V'| \leq |V_0|$ gilt $|E'| = |V'| - 1$, damit $|E_0| - 1 = (|V_0| - 1) -1$

$\Rightarrow |E_0| = |V_0| - 1$. Widerspruch dazu, dass $T_0$ ein Gegenbeispiel
ist.

$$
\tag*{$\Box$}
$$


# Definition (Spannbaum)

Sei $G=(V,E)$ ein Graph. Ein Spannbaum $T=(V',E')$ ist ein Teilgraph von $G$
mit

i) $T$ ist Baum
i) $V' = V$


# Satz (Existenz Spannbaum)

Ein Graph hat genau dann einen Spannbaum, falls $G$ zusammenhängend ist.