Wiskundeforum

Goedendag,

Voor school heb ik een opdracht gekregen om een zo efficiënt mogelijke pijpleidingen netwerk te ontwerpen om bier van een bierbrouwerij naar de 20 dichtstbijzijnde steden/dorpen te vervoeren. Dit moet gedaan worden met behulp van grafentheorie.
Weliswaar heb ik totaal geen ervaring met het gebruiken van de grafentheorie en heb du ook geen idee hoe ik dit aan moet pakken.
Ik zit in de 5e klas van het gymnasium en heb wiskunde B en wiskunde D. Deze praktische opdracht is 20% van mijn schoolexamen en heb echt hulp nodig. Hopelijk kan iemand mij zo spoedig mogelijk uitleggen hoe ik dit aan kan pakken.

Met vriendelijke groeten,

Timothy

Kijk eens naar deze pagina:
https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
(in het Engels, maar wel heel duidelijk)

De knopen zijn de plaatsen, in 1 daarvan staat de brouwerij.
De afstanden vormen de kanten van de graaf (edges).
Je zoekt nu de minimaal opspannende boom vanuit de brouwerij.

Kom je hiermee verder?

Dankjewel, ik zal kijken hoe ver ik hiermee kom.

Hier een mooi overzicht in het Nederlands:
http://www.win.tue.nl/~jessers/aansluit ... steweg.pdf

Jij kan daarvan hoofdstuk 1 (algemene definities) en hoofdstuk 2 (kortste bomen) waarschijnlijk goed gebruiken.
In jouw probleem werk je met ongerichte grafen: alle verbindingen tussen steden kan je in 2 richtingen (heen en weer, van A naar B en van B naar A) gebruiken.
Gerichte grafen gaan over verbindingen met eenrichtingsverkeer, dat kan je dus overslaan.

Het project is volledig afgerond.
Arie dankjewel voor je hulp. je bent echt mijn held <3