4  Bäume und Wälder

Definiiton 4.1

  • An acyclic graph, that is one not containing any cycles, is called a forest.
  • A connected forest is called a tree.
  • The vertices of degree 1 in a tree are its leaves, the others are its inner vertices.

Bemerkung: A forest is a graph whose components tree are trees.

Bemerkung 4.2

  • Every non-trivial tree has at least two leafs (consider the ends of a longest path).

This little fact often comes in handy, especially in induction proofs about trees:

  • If we remove a leaf from a tree, what remains is still a tree.

In general:

  • A tree G contains at least \(\Delta(G)\) leaves, where \(\Delta(G)\) is its maximum degree.

Theorem 4.3

The following assertions are equivalent for a graph \(T\):

  1. \(T\) is a tree;
  2. Any two vertices of \(T\) are linked by a unique path in \(T\);
  3. \(T\) is minimally connected, i.e. \(T\) is connected but \(T - e\) is disconnected for every edge \(e \in T\);
  4. \(T\) is maximally acyclic, i.e. \(T\) contains no cycle but \(T + xy\) does, for any two non-adjacent vertices \(x, y \in T\).
Beweis

Übung 2.

Definition

Let \(G = (V(G), E(G))\). A subgraph \(G^\prime \subseteq G\) called a spanning tree if \(V(G^\prime) = V(G).\)

Corollary 4.7

Every connected graph contains a spanning tree.

Beweis

Consider a minimal connected spanning subgraph obtained by successively deleting edges, and use (3).

Bemerkung (Induktionsprinzip über Knotenzahl durch sukssesives Hinzufügen der Blätter)

Die Knotenmenge eines Baumes \((V, E)\) hat stets eine Aufzählung \((v_i) \in V\) mit der Eigenschaft, dass \(v_i\) für jedes \(i ≥ 2\) genau einen Nachbar in \(v_1, \dots, v_{i-1}\) hat.

Korollar

  1. Sei G ein zusammenhängender Graph. Dann: \[G\text{ ist Baum } \eq |E(G)|=|V(G)| - 1\]
  2. Sei jetzt G ein Wald. Dann ist die Anzahl der Zusammenhangkomponente \[c(G) = n(G) - m(G)\]
  3. Insbesondere für jeden Wald G gilt: \[m(G) \leq n(G) - 1\]
Beweis

Nach Induktion: Einfügen einer neuen Kante erzeugt genau einen neuen Knoten.

\((\Rightarrow)\) If a tree \(G\) has only \(1\) vertex, it has \(0\) edges. Now, assume that any tree with \(k-1\) vertices has \(k-2\) edges. Let \(T\) be a tree with \(k\) vertices. Remove a leaf \(l\) to obtain a tree \(T'\) with \(k-1\) vertices. Then, \(T'\) has \(k-2\) edges, by the inductive hypothesis. The addition of \(l\) to \(T'\) produces a graph with \(k-1\) edges, since \(l\) has degree \(1\).

\((\Leftarrow)\) Conversely, let \(G\) be any connected graph with \(n\) vertices and \(n - 1\) edges. Let \(T\) be a spanning tree in \(G\). Since \(T\) has \(n - 1\) edges by the first implication, it follows that \(T = G\).

Corollary

If \(T\) is a tree and \(G\) is any graph with the minimum degree \(\delta(G) \geq |T| - 1\), then \(T\) is (isomorphic to) a subgraph of \(G\).

Bemerkung

With other words, the corollary means that any graph in which every vertex has degree \(\geq k - 1\) automatically contains every tree on k vertices as a subgraph.

Beweis

Map the vertices of \(T\) to \(G\) inductively, following their enumeration from Remark applied to \(T\).

Bemerkung

  • Für jeden Baum \(T\) ist die Cliquenzahl \(\omega(T)\) gegeben durch \[ \omega(T) \;=\; \min\{2,\,|T|\}. \]
  • Sei \(T\) ein Baum mit \(l\) Blättern. Dann ist die Unabhängigkeitszahl \(\alpha(T)\) mindestens \(l:\) \[ \alpha(T)\;\ge\;l, \] mit der einzigen Ausnahme \(T\cong K_{2}\), da in diesem Fall \(\alpha(T)=1\) (da die beiden Blätter benachbart sind).

Algorithmus 4.6: Berechnung der Unabhängigkeitszahl \(\alpha(T)\) in Bäumen

ProblemstellungGrundideeRekursive Berechnung Durch die post-order Bearbeitung (von den Blättern hinauf zur Wurzel) durch den Baum, bekommt man: \[ \boxed{A(r) \;=\;\alpha(T, c)\,.} \]

Damit lässt sich das Maximum‑Gewichtete‑Stabile‑Mengen‑Problem auf Bäumen in \(O(|V|)\) lösen.

Definition 4.8

Manchmal wählen wir einen Knoten als Wurzel eines Baumes. Ein Baum mit festgelegter Wurzel heißt Wurzelbaum (rooted tree). Gegeben einen Wurzelbaum mit Wurzel \(r\), können wir die Knoten nach ihrer Entfernung von \(r\) ordnen.
- Die Tiefe eines Knotens \(v\) ist die Länge des eindeutigen Pfades von \(r\) nach \(v\) in \(T\).
- Der Vorgänger eines Knotens \(v\neq r\) ist der Nachbar von \(v\), der eine geringere Tiefe besitzt.
- Die Kinder von \(v\) sind die übrigen Nachbarn von \(v\).

Definition 4.9

  • Ist \(G\) ein Graph mit den Knoten \(v_1,v_2,\dots,v_n \in V(G)\), so heißt die Folge
    \[ d_G(v_1),\;d_G(v_2),\;\dots,\;d_G(v_n) \]
    die Gradsequenz von \(G\).

  • Eine Folge \(d_1,d_2,\dots,d_n\in\mathbb{Z}_{+}\) nennt man ebenfalls Gradsequenz, wenn es einen Graphen \(G\) mit \(n\) Knoten existiert, der diese Folge als Gradsequenz besitzt.

Satz 4.10

Ein Tupel \((d_1,d_2,\dots,d_n)\in\mathbb{N}^n\) ist genau dann eine Gradsequenz eines Baumes, wenn \[ \sum_{i=1}^n d_i=2n-2. \]

Proof

Für die Erstellung solcher Gradfolgen siehe Prüfer Code.