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.

Inhaltsverzeichnis

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


Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Cliquenweite — Die Cliquenweite ist ein Begriff aus der Graphentheorie und ordnet jedem ungerichteten Graphen     eine natürliche Zahl zu. Sie ist daher ein Graphparameter. Auf Graphen mit beschränkter Cliquenweite lassen sich viele NP vollständige… …   Deutsch Wikipedia

  • Parametrisierter Algorithmus — Die parametrisierte Algorithmik ist ein relativ junges Teilgebiet der theoretischen Informatik, in dem genauer untersucht wird, welche Instanzen von NP vollständigen Problemen effizient zu lösen sind. Dabei wird untersucht, von welchen Faktoren… …   Deutsch Wikipedia

  • FPT — Die parametrisierte Algorithmik ist ein relativ junges Teilgebiet der theoretischen Informatik, in dem genauer untersucht wird, welche Instanzen von NP vollständigen Problemen effizient zu lösen sind. Dabei wird untersucht, von welchen Faktoren… …   Deutsch Wikipedia

  • Baum (Datenstruktur) — Ein Baum ist in der Graphentheorie ein spezieller Graph, mit dem sich eine Monohierarchie modellieren lässt. Je nachdem, ob die Kanten des Baums eine ausgezeichnete Richtung besitzen, lassen sich graphentheoretische Bäume unterteilen in… …   Deutsch Wikipedia

  • Baum (Informatik) — Ein Baum ist in der Graphentheorie ein spezieller Graph, mit dem sich eine Monohierarchie modellieren lässt. Je nachdem, ob die Kanten des Baums eine ausgezeichnete Richtung besitzen, lassen sich graphentheoretische Bäume unterteilen in… …   Deutsch Wikipedia

  • Baumstruktur — Ein Baum ist in der Graphentheorie ein spezieller Graph, mit dem sich eine Monohierarchie modellieren lässt. Je nachdem, ob die Kanten des Baums eine ausgezeichnete Richtung besitzen, lassen sich graphentheoretische Bäume unterteilen in… …   Deutsch Wikipedia

  • Dateibaum — Ein Baum ist in der Graphentheorie ein spezieller Graph, mit dem sich eine Monohierarchie modellieren lässt. Je nachdem, ob die Kanten des Baums eine ausgezeichnete Richtung besitzen, lassen sich graphentheoretische Bäume unterteilen in… …   Deutsch Wikipedia

  • Baum (Graphentheorie) — Ein Baum ist in der Graphentheorie ein spezieller Graph, mit dem sich eine Monohierarchie modellieren lässt. Je nachdem, ob die Kanten des Baums eine ausgezeichnete Richtung besitzen, lassen sich graphentheoretische Bäume unterteilen in… …   Deutsch Wikipedia

  • Baumzerlegung — ist: das Aufarbeiten eines Baumes, siehe Fälltechnik. ein Begriff aus der Graphentheorie, siehe Baumweite. Diese Seite ist eine Begriffsklärung zur Unterscheidung mehrerer mit demselben Wort bezeic …   Deutsch Wikipedia

  • Pfadweite — Die Pfadweite ist ein Begriff aus der Graphentheorie. Sie sagt aus, wie „pfad ähnlich“ ein Graph ist. Da viele Algorithmen auf Pfaden (oder Pfadzerlegungen) effizient laufen, die dies auf allgemeinen Graphen nicht tun, ist es interessant, die… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”