Eine numerische Messgröße dafür, wie nah ein ungerichteter Graph an einem Baum ist; sie wird als Minimum über allen Baumentzippungen (tree decompositions) des Maximums der Sackgrößen minus eins definiert. Kleine Baumweite bedeutet, dass der Graph durch kleine überlappende Knotenmengen in Baumform organisiert werden kann.

Prinzip

Organisiere den Graphen als Baum von überlappenden Knotenmengen (Säcken) und verwende die größte Sackgröße als Kostengröße; die Minimierung dieses Maximums erfasst die kleinste notwendige lokale Interaktionsgröße zur Rekonstruktion der globalen Struktur.

Demonstration

Ein Baum oder Wald hat Baumweite 1 (Säcke enthalten höchstens zwei Knoten); ein Pfad hat Baumweite 1, ein Zyklus hat Baumweite 2, und der vollständige Graph K_n hat Baumweite n−1; viele dynamische Programmieralgorithmen laufen in Zeit, die exponentiell in der Baumweite, aber polynomial in der Graphgröße ist.

Fehlanwendung

Grad, Arborizität oder Pathwidth mit Baumweite gleichzusetzen und anzunehmen, ein kleiner Maximalgrad impliziere kleine Baumweite, oder Treewidth-basierte Algorithmen anzuwenden, ohne eine gültige Baumentzippung begrenzter Weite zu erzeugen.

Konsequenz

Hat ein Graph beschränkte Baumweite, so sind viele im Allgemeinen schwierige Probleme (Färbung, Hamilton-Varianten, Constraint-Satisfaction) mittels fixed-parameter- oder polynomieller Algorithmen parameterisiert durch die Baumweite lösbar; die strukturelle Graphentheorie liefert Decompositions- und Minor-Sätze im Zusammenhang mit Baumweite.

Umkehrung

Die Umkehrperspektive sind Graphen mit großer Baumweite (z. B. Expander), die sich nicht in kleine Säcke zerlegen lassen und starke globale Konnektivität zeigen; große Baumweite erschwert lokale dynamische Programmierung, signalisiert jedoch kombinatorische Komplexität.

Abgrenzung

Definiert für ungerichtete Graphen über Tree Decompositions; Erweiterungen für gerichtete Graphen und Hypergraphen existieren, benötigen jedoch andere Formulierungen; Baumweite ist minorsinvariant, misst aber nicht in jedem Sinn Sparsity und unterscheidet sich von verwandten Invarianten wie Pathwidth oder Tree-Depth.

Semantische Spannung

Spannung besteht gegenüber Pathwidth, Tree-Depth und Dichtigkeitsmaßen: Pathwidth schränkt die Form der Zerlegung stärker ein, Tree-Depth misst höhenähnliche Komplexität, Dichte/Arborizität beschreiben die Kantendistribution; jede Größe betont andere strukturelle Aspekte.

Synthese

Baumweite fasst die globale Komplexität eines Graphen durch die Größe lokal überlappender Teile zusammen, die als Baum organisiert sind: Minimiere die maximale Sackgröße in einer Tree Decomposition; ist dieser Wert klein, lassen sich viele globale Probleme durch lokal-arboreszentes Vorgehen lösen.