die minimale Weite einer Baumzerlegung eines Graphen.

Dabei besteht eine Baumzerlegung eines Graphen G aus einem BaumT und einer Familie {E_t|t ∈ E(T)} von Eckenmengen E_t ⊆ E(G), die folgende Bedingungen erfüllen:

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 K₄ 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}