Baumweite

Die Baumweite ist ein Begriff aus der Graphentheorie. Sie sagt aus, wie "baum-ähnlich" ein Graph ist. Da viele Algorithmen auf Bäumen (oder Baumzerlegungen) effizient laufen, die dies auf allgemeinen Graphen nicht tun, ist es interessant, die Baumweite zu kennen. Baum- und Pfadweite sind größtenteils analog zueinander.

Formale Definition

Eine Baumzerlegung von G = (V,E) ist ein Paar (X,T), wobei T = (I,F) ein Baum ist und $X = \{X_i|i \in I\}$ eine Familie von Untermengen der Knotenmenge V des Graphen ist, sodass gilt:

• $\bigcup_{i \in I} X_i = V$.
• Für alle Kanten $(v,w) \in E$ gibt es ein $i \in I$ mit $v,w \in X_i$.
• 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 Weite der Baumzerlegung (X,T) von G ist definiert als $\max_{i\in I} |X_i|-1$.

Die Baumweite eines Graphen G ist definiert als die kleinste Weite aller Baumzerlegungen von G.

Erläuterung

Verständlicher ausgedrückt verteilen wir die Knoten von G auf Taschen (Englisch: buckets oder bags), die in einer Baumstruktur angeordnet sind.

Dabei gelten folgende Regeln:

• Jeder Knoten aus V ist in mindestens einer Tasche,
• die beiden Endknoten jeder Kante sind zusammen in mindestens einer Tasche und
• für jeden Knoten v bilden die Taschen, die v enthalten, einen Unterbaum.

Die Weite einer Baumzerlegung ist die maximale Anzahl Knoten in einer einzelnen Tasche - 1. Die Subtraktion von 1 bewirkt, dass die Baumweite von Bäumen 1 beträgt. Ohne diese Subtraktion hätten Bäume Baumweite 2.

Baumweite spezieller Graphklassen

Das Bestimmen der Baumweite eines gegebenen Graphen ist unter allgemeinen Bedingungen ein NP-vollständiges Problem. Allerdings lassen sich die Baumweiten einiger Graphklassen nach oben abschätzen:

• Jeder Baum hat eine Baumweite von höchstens 1
• Serienparallele Graphen haben eine Baumweite von höchstens 2
• Halingraphen haben eine Baumweite von höchstens 3

Literatur

• Minoren, Bäume und WQO. Kapitel 10 in: Reinhard Diestel, Graphentheorie. Springer 2006.
• 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

Weblinks

• Baum- und Pfadweite — Intuitive Darstellung der Thematik (PDF-Datei; 400 kB)
• Nondeterministic Graph Searching: From Pathwidth to Treewidth (auf Englisch) — Folien unter anderem mit mehreren Zerlegungen.