mini|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 als Teilbaum der Baumzerlegung so repräsentiert werden, dass sie in nur dann benachbart sind, wenn ihre Teilbäume sich schneiden. Das bedeutet, dass ein Teilgraph des Schnittgraphen der Teilbäume ist. Der vollständige Schnittgraph ist ein chordaler Graph.
Formale Definition Eine Baumzerlegung eines Graphen ist ein Paar , mit
einem Baum mit den Knoten und den Kanten und
einer Familie von Teilmengen 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 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:
Für alle Knoten des Graphen gilt, dass die Taschen, die enthalten, einen nichtleeren Teilbaum bilden. Für alle Kanten des Graphen gilt, dass die Teilbäume von und keinen leeren Schnitt haben.
Varianten Zusätzlich zur formalen Definition, können weitere Eigenschaften von der Baumzerlegung gefordert werden, um sie dann in Algorithmen oder Beweisen verwenden zu können. Allen Varianten ist gemein, dass sie aus einer beliebigen Baumzerlegung erstellt werden können; jedoch können verschiedene Varianten sich gegenseitig ausschließen.
Schöne Baumzerlegung Eine schöne Baumzerlegung (engl. nice tree decomposition) wird als Werkzeug benutzt, um NP-vollständige Probleme schnell zu lösen. Zentrale Eigenschaft ist, dass sich benachbarte Taschen um maximal einen Knoten unterscheiden und die Zerlegung ein binärer Wurzelbaum ist.
Eine Baumzerlegung mit Wurzel , des Graphen heißt schöne Baumzerlegung, wenn jede Tasche exakt eine der folgenden Eigenschaften hat:
Blatt (engl. Leaf): Hat keine Kind Knoten Vergessen (engl. Forget): hat exakt einen Kind Knoten mit und Hinzufügen (engl. Introduce): hat exakt einen Kind Knoten mit und Verbinden (engl. Join): hat exakt zwei Kind Knoten und mit .
Anschaulich handelt es sich um einen Baum mit einer Wurzel, wobei von einer Tasche zur nächsten Tasche, entweder ein Knoten hinzugefügt oder entfernt wird, oder eine Kopie für eine Verzweigung verwendet wird.
Der Begriff der schönen Baumzerlegung wird in der Literatur nicht einheitlich verwendet. Manchmal werden die Kriterien für eine sehr schöne Baumzerlegung aufgeführt und nur als schöne Baumzerlegung definiert.
Sehr schöne Baumzerlegung Eine sehr schöne Baumzerlegung (engl. very nice tree decomposition) ergänzt die schöne Baumzerlegung um eine weitere Eigenschaft.
Eine sehr schöne Baumzerlegung mit Wurzel des Graphen ist eine schöne Baumzerlegung, bei der alle Blätter des Baums nur einen Knoten enthalten:
Für alle Blätter gilt .
Anschaulich handelt es sich um eine schöne Baumzerlegung, bei der an den Blatt Knoten noch weitere Vergessen Knoten angefügt wurden, bis nur noch ein Knoten in einer Tasche ist.
Die sehr schön Baumzerlegung vereinfacht die Implementierung von Dynamischen Programmen, da die Veränderung zwischen zwei Taschen maximal ein Knoten ist und Blattknoten meist triviale Lösungen besitzen. Im Gegenzug ist die Anzahl an Taschen in nicht mehr ausschließlich durch beschränkt, sondern durch und . Dabei gibt die Anzahl der Knoten in wieder und die Weite der Baumzerlegung. Dies kann bei sehr großer Weite zu Laufzeitproblemen oder Speicherproblemen führen oder theoretische Ergebnisse, die ausschließlich von abhängen sollen, unmöglich machen. Literatur
Einzelnachweise
Kategorie:Grundbegriff (Graphentheorie) Kategorie:Bäume und Wälder Kategorie:Graphentheorie