Baumzerlegung (Graphentheorie)

In der Graphentheorie ist eine Baumzerlegung eine Abbildung eines Graphen in einen Baum, die dazu verwendet werden kann die Baumweite eines Graphen zu bestimmen und die die Berechnung von bestimmten Problemen auf Graphen beschleunigt.

Ein Graph (auch Originalgraph genannt um ihn eindeutig von seiner Baumzerlegung zu unterscheiden, da ein Baum auch ein Graph ist) mit acht Knoten und einer seiner Baumzerlegungen. Diese beinhaltet sechs Taschen, die die Knoten der Baumzerlegung sind. Die Knoten des Originalgraphen sind – zusammen mit dem Pfad, den sie in der Baumzerlegung bilden – farbig markiert. Die Taschen der Baumzerlegung sind als Kreise gezeichnet und beinhalten die Knoten des Originalgraphen.

Definition

Die Intuition hinter einer Baumzerlegung ist, dass die Knoten eines gegebenen Graphen $G$ als Subbaum der Baumzerlegung dargestellt werden und zwar so, dass Knoten in $G$ genau dann nebeneinander liegen, wenn ihre Subbäume der Baumzerlegung sich überschneiden. Das bedeutet, dass $G$ einen Subgraph des Schnittgraphen der Subbäume bildet. 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$

• sowie den Taschen $X=\{X_{i}~|~i\in I\}$, einer Familie von Untermengen der Knotenmenge $V$ des Graphen, 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, die zweite dass jede Kante (in Form von ihren beiden Knoten) in einer Tasche der Baumzerlegung vorkommen muss. Die dritte Bedingung besagt, dass der Schnitt von zwei Taschen auf einem Pfad in einer Tasche die zwischen ihnen auf dem Pfad liegt vorkommen 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 des Graphen gilt, dass die Taschen die v enthalten einen 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

• 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.