In der Mathematik ist ein Spannbaum ein Untergraph eines ungerichteten Graphen, der alle Scheitelpunkte des ungerichteten Graphen enthält. Es ist ein grundlegendes Werkzeug, um schwierige Probleme in der Mathematik zu lösen, z. B. das Vierfarben-Kartenproblem und das Problem des reisenden Verkäufers. Normalerweise wird ein Spannbaum durch Verzweigung von einem der inneren Punkte gebildet, weshalb er als Baum bezeichnet wird.

Ausführliche Erklärung

Um einen Spannbaum zu visualisieren, stellen Sie sich zunächst ein ungerichtetes Diagramm vor: Zum Beispiel eine zufällige Sammlung von Punkten, die durch Linien verbunden sind. Die Verbindungen müssen ungerichtet sein. Das bedeutet, dass Sie auf den Linien in beide Richtungen fahren können, um von einem Punkt zum anderen zu gelangen. Jeder Punkt muss irgendwie mit dem Rest verbunden sein, und jeder Punkt kann mehrere Verbindungen haben.

Ein Spannbaum für diesen Graphen ist ein beliebiger Untergraph (ein Graph, der die gleichen Punkte verwendet), der alle Punkte berührt, obwohl er nicht die gleichen Linien verwenden muss.

Diagramm, Netzwerkbegriffe, Spanning Tree-Protokoll