Minimaal opspannende boom
- Auteur:
- chris cambré
Versleep een of meerdere punten in de applet en zie hoe de Minimaal opspannende boom verandert.
De minimaal opspannende boom vormt een netwerk waarin alle knopen van de graaf zijn opgenomen zodat het totale gewicht van de graaf (hier de lengte van de lijnstukken) minimaal is.
Merk op dat, net zoals bij het berekenen van het kortste pad, GeoGebra zuiver meetkundig werkt. Het verslepen van punten in de constructie wijzigt wezenlijk de opgave en kan tot andere oplossingen leiden, wat atypisch is voor grafen.
Opgaven om de minimale opspannende boom te berekenen, worden dan ook doorgaans voorgesteld door de lengtes van de bogen willekeurig te tekenen, maar ze een gewicht te geven. We spreken van van gewogen grafen.
Zie verder als achtergrond de artikels van de Technische Universiteiten van Delft en Eindhoven.