09 Minimaal opspannende bomen

Modderstad – Minimaal opspannende bomen

Waar gaat activiteit 9 over?

Stel dat je voor een nieuwe stad moet bedenken hoe het water, de elektriciteit en het gas naar alle huizen moet worden gebracht. Ieder huis apart verbinden met de elektriciteitscentrale is nogal omslachtig, veel beter is het om een netwerk aan te leggen dat voor alle huizen een verbinding met de centrale waarborgt. Het maakt daarbij niet echt uit dat sommige huizen een veel langere route naar de elektriciteitscentrale krijgen, zolang ze verbonden zijn is er stroom!

De opdracht om een netwerk te maken waarbij de totale lengte zo min mogelijk is wordt wel het probleem van een minimaal opspannende boom genoemd.

Minimaal opspannende bomen zijn niet alleen nuttig voor netwerken van gas en energie; ze helpen ook bij het oplossen van problemen in computernetwerken, telefoonnetwerken, oliepijpleidingen en routenetwerken van luchtvaartmaatschappijen. Hoewel je bij dat laatste voorbeeld, waarbij je de beste routes ontwerpt voor reizigers, je ook rekening moet houden met de kosten van de individuele reiziger. Niemand wil uren omreizen omdat het iets goedkoper is. Het vinden van de oplossing met het minimale totaal van wegen is in het geval van vliegroutes niet voldoende omdat het geen rekening houdt met de wens bepaalde wegen sowieso op te nemen.

Je kunt minimaal opspannende bomen ook gebruiken bij andere problemen die als graaf kunnen worden gerepresenteerd. Bijvoorbeeld bij het handelsreizigersprobleem waarbij je zoekt naar een rondreis langs alle steden in het netwerk.

Er zijn efficiënte algoritmes (methodes) om in een willekeurige graaf een minimaal opspannende boom te vinden. Een eenvoudige methode is die waarbij je begint met geen enkele weg en vervolgens steeds de kortste nog niet gebruikte verbinding toevoegt die het netwerk laat groeien met een punt dat nog niet verbonden was. Deze methode heet Kruskals algoritme omdat J.B. Kruskal in 1956 er als eerste over publiceerde.

Er zijn nog vele problemen met grafen, waaronder het handelsreizigersprobleem, waar informatici nog altijd op zoek zijn naar snellere methodes die de best mogelijke oplossing vinden.

Geschikt voor leeftijd: 9 jaar en ouder

Download lesje 9: Modderstad – Minimaal opspannende bomen