Baumweite

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.

Der Begriff wurde 1972 von Umberto Bertelè und Francesco Brioschi eingeführt, unabhängig von Rudolf Halin 1976 und erneut unabhängig von Neil Robertson und Paul Seymour 1984.