Baumzerlegung (Graphentheorie)

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.

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

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

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

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

sodass folgendes gilt:

1. ${\displaystyle \bigcup _{i\in I}X_{i}=V}$.
2. Für alle Kanten ${\displaystyle (v,w)\in E}$ gibt es ein ${\displaystyle i\in I}$ mit ${\displaystyle v,w\in X_{i}}$.
3. Für alle ${\displaystyle i,j,k\in I}$ gilt: wenn ${\displaystyle j}$ auf dem Pfad von ${\displaystyle i}$ zu ${\displaystyle k}$ in ${\displaystyle T}$ ist, dann ${\displaystyle 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 ${\displaystyle v\in V}$ des Graphen gilt, dass die Taschen, die ${\displaystyle v}$ enthalten, einen nichtleeren Teilbaum bilden.
2. Für alle Kanten ${\displaystyle (v,w)\in E}$ des Graphen gilt, dass die Teilbäume von ${\displaystyle v}$ und ${\displaystyle w}$ keinen leeren Schnitt haben.

• Reinhard Diestel: Graphentheorie. 5. Auflage. Springer-Verlag, Berlin, Heidelberg 2010, ISBN 978-3-96134-004-0, 10. Minoren, S. 287–330. 
• Frank Gurski, Irene Rothe, Jörg Rothe, Egon Wanke: Exakte Algorithmen für schwere Graphenprobleme. Springer-Verlag, Berlin, Heidelberg 2010, ISBN 978-3-642-04499-1. 
• Hans L. Bodlaender: Fixed-Parameter Tractability of Treewidth and Pathwidth. In: Bodlaender H.L., Downey R., Fomin F.V., Marx D. (Hrsg.): The Multivariate Algorithmic Revolution and Beyond. LNCS 7370. Springer, Berlin, Heidelberg 2012, ISBN 978-3-642-30890-1, S. 196–227, doi:10.1007/978-3-642-30891-8_12.