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.
Definition
[Bearbeiten | Quelltext bearbeiten]Die Intuition hinter einer Baumzerlegung ist, dass die Knoten eines gegebenen Graphen als Subbaum der Baumzerlegung dargestellt werden und zwar so, dass Knoten in genau dann nebeneinander liegen, wenn ihre Subbäume der Baumzerlegung sich überschneiden. Das bedeutet, dass einen Subgraph des Schnittgraphen der Subbäume bildet. Der vollständige Schnittgraph ist ein chordaler Graph.
Formale Definition
[Bearbeiten | Quelltext bearbeiten]Eine Baumzerlegung eines Graphen ist ein Paar , mit
- einem Baum mit den Knoten und den Kanten
- sowie den Taschen , einer Familie von Untermengen der Knotenmenge des Graphen, wobei jedes als Tasche (engl. bag) bezeichnet wird
sodass folgendes gilt:
- .
- Für alle Kanten gibt es ein mit .
- Für alle gilt: wenn auf dem Pfad von zu in ist, dann .
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:
- Für alle Knoten v des Graphen gilt, dass die Taschen die v enthalten einen Teilbaum bilden.
- Für alle Kanten des Graphen gilt, dass die Teilbäume von und keinen leeren Schnitt haben.
Literatur
[Bearbeiten | Quelltext bearbeiten]- 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.