Spannbaum

Sei ein zusammenhängender, ungerichteter, kantengewichteter Graph. Ein azyklischer Teilgraph mit und , in dem alle Knoten miteinander verbunden sind, heißt Spannbaum.

Einfach gesagt

Ein Spannbaum ist ein Teilgraph, der alle Knoten erreichbar macht und unter diesen Teilgraphen derjenige mit den wenigsten Kanten. Um genau zu sein, Kanten, so dass ein Baum entsteht.

Siehe auch

• Aufspannender Teilgraph
• Minimaler Spannbaum

Beispiel

graph LR
A --- B
A --- C
B --- C
B --- D
C --- E
D --- E

Spannbaum:

graph LR
A --- B
B --- C
C --- E
B --- D