In der Mathematik ist ein aufspannender Baum ein Teilgraph eines ungerichteten Graphen, der alle Eckpunkte des ungerichteten Graphen enthält. Es ist ein grundlegendes Werkzeug, das verwendet wird, um schwierige Probleme in der Mathematik wie das Problem der vierfarbigen Karte und das Problem des Handlungsreisenden zu lösen. Üblicherweise entsteht ein aufspannender Baum durch Verzweigung von einem der inneren Punkte, weshalb er auch als Baum bezeichnet wird.
Ausführliche Erklärung
Um einen aufspannenden Baum zu visualisieren, stellen Sie sich zunächst einen ungerichteten Graphen vor: zum Beispiel eine zufällige Ansammlung 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 aufspannender Baum für diesen Graphen ist ein beliebiger Teilgraph (ein Graph, der dieselben Punkte verwendet), der alle Punkte berührt, aber nicht dieselben Linien teilen muss.
Graph, Netzwerkbegriffe, Spanning Tree Protocol
