Direkt zum Inhalt

Lexikon der Mathematik: Baumweite

die minimale Weite einer Baumzerlegung eines Graphen.

Dabei besteht eine Baumzerlegung eines Graphen G aus einem Baum T und einer Familie {Et|tE(T)} von Eckenmengen EtE(G), die folgende Bedingungen erfüllen:

  • E(G)=∪tE(T)Et.
  • Für jede Kante k = uv des Graphen gibt es ein tE(T), so daß u, vEt.
  • Liegt für drei Ecken t1, t2, t3E(T) die Ecke t3 auf dem (eindeutigen) Weg in T von t1 nach t2, dann gilt \({E}_{{t}_{1}}\cap {E}_{{t}_{2}}\subseteq {E}_{{t}_{3}}\).
  • Als Weite der Baumzerlegung definiert man die Zahl \begin{eqnarray}\max \{|{E}_{t}|-1|t\in E(T)\}.\end{eqnarray}

    Die Baumweite eines Graphen ist genau dann kleiner oder gleich 1, wenn er ein Wald ist.

    Die Baumweite eines Graphen ist genau dann kleiner oder gleich 2, wenn er den vollständigen Graphen K4 nicht als Minor enthält (diese Graphen sind auch als „series-parallel graphs“ bekannt).

    Die Bestimmung der Baumweite eines Graphen ist ein NP-schweres Problem. Einen Graphen mit

    Baumweite ≤ k bezeichnet man auch als partiellen-k-Baum oder Teil-k-Baum. Die kantenmaximalen partiellen-k-Bäume nennt man k-Bäume.

    Ist der Baum T in einer solchen Zerlegung ein Weg, so spricht man auch von einer Wegzerlegung.

    Die Baumweite eines Graphen G ist ebenfalls gleich dem Minimum über ω(H) − 1 für alle chordalen Graphen H, die G als Teilgraphen enthalten. Dabei bezeichnet ω(H) die Cliquenzahl von H.

    Der Begriff der Baumweite ist sehr wichtig für die Theorie der Minoren von Graphen und dient oft zum Beweis struktureller Aussagen über Graphen. Darüber hinaus ist er von algorithmischem Interesse, da viele NP-schwere Probleme sich für Graphen beschränkter Baumweite effizient lösen lassen.

    Eine der wesentlichen Aussagen über die Baumweite eines Graphen ist, daß diese genau dann groß ist, wenn der Graph ein Gitter großer Ordnung als Minor enthält. Ein Gitter ist dabei ein Graph mit der Eckenmenge \begin{eqnarray}\{(i,j)|1\le i,j\le n\}\end{eqnarray} und der Kantenmenge \begin{eqnarray}\{(i,j)(i+1,j),(j,i)(j,i+1)|1\le i\le n-1,1\le j\le n\}.\end{eqnarray}

    Schreiben Sie uns!

    Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

    • Die Autoren
    - Prof. Dr. Guido Walz

    Partnerinhalte

    Bitte erlauben Sie Javascript, um die volle Funktionalität von Spektrum.de zu erhalten.