Theorie

Voor deze les is het belangrijk om eerst de theorie van zowel les 3 als van les 4 te bestuderen. Het is ook aangeraden om de bijbehorende theorie al te hebben bestudeerd voor dat je met de opdrachten begint. Hieronder vind je een samenvatting van de theorie uit het boek. 

 

Theorie A : Een boom en een gewogen graaf

We kunnen bij elke lijn van een graaf getallen zetten. Deze getallen kunnen bijvoorbeeld kosten of afstand betekenen. Wanneer bij elke lijn een getal hoort dan noemen we de graaf een gewogen graaf.


Een boom is een graaf die geen kringen bevat. Er is sprake van een kring in een graaf als je vanuit een knooppunt terug kunt keren in datzelfde knooppunt zonder een pad twee keer te gebruiken

 

Thoerie B : Edsger Dijkstra

Robert Prim was niet de enige die het algoritme had ontdekt. In dezelfde tijd ontdekte de Nederlander Edsger Dijkstra hetzelfde algoritme zonder ooit van Robert gehoord te hebben. Ook Nederland was zo'n rijk en modern land. Helaas was het land in 1953 met een grote storm overstroomd. Om dit soort overstromingen in de toekomst te voorkomen, bouwden we de Deltawerken: zes enorm dammen die ons tegen het zeewater verdedigen. Maar voor zulke bouwwerken zijn ingewikkelde berekeningen nodig en zoiets als een rekenmachine bestond nog niet. Edsger bouwde daarom mee aan de ARMAC, de eerste Nederlandse computer. Het ding was zo groot als een kleine huiskamer en had een geheugen van ongeveer 100 kB. Edsger wilde de bedrading van de computer zo efficiënt mogelijk maken en vond daarvoor hetzelfde algoritme van Prim uit. Het algoritme mag dan niet naar Edsger vernoemd zijn, maar Edsger gebruikte zijn ontdekking om vervolgens een tweede algoritme uit te vinden. Dit algoritme van Dijkstra vindt de kortste route tussen twee punten en wordt vandaag nog door iedere routeplanner gebruikt.

Het algoritme

Het woord algoritme komt van “dixit algorismi” wat Latijn is voor “Al-Khwarizmi heeft gezegd”. Al-Khwarizmi was een Arabische wiskundige uit de negende eeuw. Zijn uitleg over rekenen met Hindoe-Arabische cijfers werd erg populair en hieruit volgde het woord algorism. Dit betekende een stappenplan voor het doen van rekenkunde. Ons moderne woord algoritme is hiervan afgeleid en heeft een veel ruimere betekenis gekregen.

Een algoritme is een stappenplan die je volgt om een doel te bereiken. Een recept voor het bakken van een appeltaart is een algoritme maar ook een stappenplan om de richtingscoëfficiënt bij een lineaire lijn te vinden is een algoritme.

Dijkstra’s methode

Dit onderstaande stukje komt uit het originele wiskundige artikel van Edsger Dijkstra. Hij beschrijft hier het algoritme (zoals ook Prim dat gevonden heeft).

 

Voorbeeld
We kiezen knoop D om mee te starten:             

I: leeg
II: {AD, BD, CD1, CD2}
III: {AB, AC, BC}
A: {D}
B: {A, B, C}

AD wordt vervangen door AB. En DC1, DC2 worden vervangen door BC.

                                                     
I: {BD}
II: {AB, BC}
III: {AC, DA,DC1, DC2}
A: {B, D}
B: {A, C}

I: {AB, BD}
II: {BC}
III: {BC, CD1, CD2}
A: {A, B, D}
B: {C}
           
I: {AB, BD, BC}
II: leeg
III: {AC, AD, CD1, CD2}
A: {A, B, C, D}
B: leeg
           
De minimaal opspannende boom bestaat uit takken AB, BC en BD en heeft een totale lengte van

AB + BC + BD = 10

Uitleg grafentheorie (deel 3) https://www.youtube.com/embed/9cn0C4nCu50