Baumzerlegung (Graphentheorie)

Ein Graph mit acht Knoten und eine seiner Baumzerlegungen. Diese hat sechs Taschen mit je drei Knoten, die als Kreise in den Knoten des Baumes dargestellt sind. Die Knoten des Originalgraphen sind – zusammen mit dem Pfad, den sie in der Baumzerlegung bilden – farbig markiert. Die Weite dieser Baumzerlegung beträgt zwei.

In der Graphentheorie ist eine Baumzerlegung eine Abbildung eines Graphen in einen Baum, die dazu dient, seine Baumweite zu bestimmen. Die Baumzerlegung eines Graphen kann genutzt werden, um bestimmte algorithmische Probleme auf diesem Graphen effizient zu lösen.

Definition

Die Intuition hinter einer Baumzerlegung ist, dass die Knoten des gegebenen Graphen $G$ als Teilbaum der Baumzerlegung so repräsentiert werden, dass sie in $G$ nur dann benachbart sind, wenn ihre Teilbäume sich schneiden. Das bedeutet, dass $G$ ein Teilgraph des Schnittgraphen der Teilbäume ist. Der vollständige Schnittgraph ist ein chordaler Graph.

Formale Definition

Eine Baumzerlegung eines Graphen $G=(V,E)$ ist ein Paar $(T,X)$, mit

• einem Baum $T=(I,F)$ mit den Knoten $I$ und den Kanten $F$ und

• einer Familie von Teilmengen der Knotenmenge des Graphen $X=\{X_i|X_i\subseteq V,i\in I\}$, wobei jedes $X_i$ als Tasche (engl. bag) bezeichnet wird

sodass folgendes gilt:

1. $\bigcup _{i\in I}{X}_i=V$.
2. Für alle Kanten $(v,w)\in E$ gibt es ein $i\in I$ mit $v,w\in X_i$.
3. Für alle $i,j,k\in I$ gilt: wenn $j$ auf dem Pfad von $i$ zu $k$ in $T$ ist, dann $X_i\cap X_k\subseteq X_j$.

Die erste Bedingung bedeutet, dass jeder Knoten in mindestens einer Tasche enthalten sein muss. Die zweite fordert, dass es auch für jede Kante eine Tasche geben muss, die beide Endknoten enthält. Die dritte Bedingung besagt, dass der Schnitt von zwei Taschen auch in jeder Tasche, die im Baum auf dem Pfad zwischen ihnen liegt, enthalten sein muss. Intuitiv bedeutet diese letzte Bedingung, dass Knoten zusammenhängend in den Taschen vorkommen.

Alternativ zu obigen drei Bedingungen lassen sich auch folgende zwei fordern:

1. Für alle Knoten $v\in V$ des Graphen gilt, dass die Taschen, die $v$ enthalten, einen nichtleeren Teilbaum bilden.
2. Für alle Kanten $(v,w)\in E$ des Graphen gilt, dass die Teilbäume von $v$ und $w$ keinen leeren Schnitt haben.

Literatur

• Vorlage:Literatur
• Vorlage:Literatur
• Vorlage:Literatur