Spannbaum
Teilgraph eines ungerichteten Graphen mit allen Knoten, Begriff aus der Graphentheorie / aus Wikipedia, der freien encyclopedia
Liebe Wikiwand-AI, fassen wir uns kurz, indem wir einfach diese Schlüsselfragen beantworten:
Können Sie die wichtigsten Fakten und Statistiken dazu auflisten Minimaler Spannbaum?
Fass diesen Artikel für einen 10-Jährigen zusammen
ZEIGE ALLE FRAGEN
Ein Spannbaum (auch aufspannender Baum oder Gerüst genannt; englisch spanning tree, manchmal fälschlich als „spannender Baum“ übersetzt) ist in der Graphentheorie ein Teilgraph eines ungerichteten Graphen, der ein Baum ist und alle Knoten dieses Graphen enthält.[1] Spannbäume existieren nur in zusammenhängenden Graphen.
In einem vollständigen Graphen findet man nach der Cayley-Formel verschiedene Spannbäume. Im nebenstehenden Beispiel des sind es Stück.