Baumweite

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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[Bearbeiten]

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[Bearbeiten]

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[Bearbeiten]

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:

Literatur[Bearbeiten]

  • 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[Bearbeiten]