Baumweite

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.