In de wiskunde is een spanningboom een subafbeelding van een niet-gerichte grafiek die alle hoekpunten van de niet-gerichte grafiek bevat. Het is een fundamenteel hulpmiddel om moeilijke problemen in de wiskunde op te lossen, zoals het vierkleurenkaartprobleem en het probleem van reizende verkopers. Meestal is een spanning tree gevormd door vertakking van een van de innerlijke punten, dat is waarom het wordt beschreven als een boom.

Gedetailleerde uitleg

Om een ​​spanningboom te visualiseren, moet u eerst een niet-gerichte grafiek weergeven: bijvoorbeeld een willekeurige verzameling punten verbonden door lijnen. De verbindingen moeten ongericht zijn; wat betekent dat je in beide richtingen op de lijnen kunt reizen om van het ene punt naar het andere te gaan. Elk punt moet op de een of andere manier met de rest zijn verbonden, en elk punt kan meerdere verbindingen hebben.

Een spanningboom voor deze grafiek is elke subafbeelding (een grafiek die dezelfde punten gebruikt) die alle punten raakt, hoewel het niet allemaal dezelfde lijnen hoeft te delen.

Grafiek, Netwerktermen, Spanning Tree-protocol