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

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

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:

  1.  .
  2. Für alle Kanten   gibt es ein   mit  .
  3. 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:

  1. Für alle Knoten v des Graphen gilt, dass die Taschen die v enthalten einen Teilbaum bilden.
  2. Für alle Kanten   des Graphen gilt, dass die Teilbäume von   und   keinen leeren Schnitt haben.

Literatur

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.