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. Ein verwandter Begriff ist die Pfadweite.

Formale Definition[Bearbeiten | Quelltext bearbeiten]

Eine Baumzerlegung von ist ein Paar , wobei ein Baum ist und eine Familie von Untermengen der Knotenmenge des Graphen ist, sodass gelten:

  • .
  • Für alle Kanten gibt es ein mit .
  • Für alle gilt: wenn auf dem Pfad von zu in ist, dann .

Die Baumweite der Baumzerlegung von ist definiert als und die Baumweite eines Graphen ist definiert als die kleinste Baumweite aller Baumzerlegungen von .

Die Subtraktion von 1 bewirkt, dass die Baumweite von genau dann 1 beträgt, wenn ein Baum ist (ohne diese Subtraktion hätten Bäume Baumweite 2).

Erläuterung[Bearbeiten | Quelltext bearbeiten]

Wir verteilen die Knoten von G auf Taschen (Englisch: buckets oder bags), die in einem Baum angeordnet sind, wobei folgende Regeln gelten:

  • Jeder Knoten aus ist in mindestens einer Tasche
  • Die beiden Endknoten jeder Kante sind zusammen in mindestens einer Tasche
  • Für jeden Knoten bilden die Taschen, die enthalten, einen Unterbaum

Eigenschaften[Bearbeiten | Quelltext bearbeiten]

Komplexität[Bearbeiten | Quelltext bearbeiten]

Das Entscheidungsproblem, ob ein gegebener Graph G eine Baumweite kleiner k, mit k konstant besitzt, ist NP-vollständig. Ein Graph mit beschränkter Baumweite lässt sich jedoch in linearer Zeit (linear in Anzahl der Knoten und in exponentieller Abhängigkeit von der konstanten Baumweite) erkennen.

Schranken[Bearbeiten | Quelltext bearbeiten]

Es gelten folgende Schranken für Baumweiten:

  • Jeder Baum mit mindestens 2 Knoten hat eine Baumweite von genau 1.
  • Serienparallele Graphen haben eine Baumweite von höchstens 2.
  • Halingraphen haben eine Baumweite von höchstens 3.
  • Die Baumweite planarer Graphen ist nicht nach oben beschränkt. Dies wird deutlich am Beispiel der -Gittergraphen. Diese besitzen eine Baumweite von .
  • Die Baumweite ist größer gleich der Größe der maximalen Clique minus 1.

Literatur[Bearbeiten | Quelltext bearbeiten]

  • Reinhard Diestel: Graphentheorie. 4. Auflage. Springer-Verlag, Berlin Heidelberg 2010, ISBN 978-3-642-14911-5.
  • 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 | Quelltext bearbeiten]