Spannbaum

Ein Spannbaum eines Graphen $G$ ist ein spannender, zusammenhängender und azyklischer Untergraph $T\subseteq G$.
Er ist also ein Baum, der genau alle Knoten von $G$ enthält.

Jeder zusammenhängende Graph enthält mindestens einen Spannbaum. Spannbäume können systematisch z.B. durch Tiefensuche (DFS) oder Breitensuche (BFS) berechnet werden.

Links

• Baum und Wald
• Breitensuche
• DS_vollständiger_foliensatz.pdf