Discrete wiskunde en algoritmen
Discrete wiskunde en algoritmen toetst het werken met grafen, matrices, algoritmen en rekenen in eindige structuren. Je moet een probleem vertalen naar een graaf, een algoritme stap voor stap uitvoeren en de uitkomst interpreteren.
Kernregels
- Graaf: knopen en ribben; de graad is het aantal ribben bij een knoop.
- Eulerroute: precies 0 of 2 knopen met oneven graad; Eulercircuit: alle graden even.
- Hamiltonroute: bezoekt elke knoop precies één keer; dat is een ander probleem dan Euler.
- Boom: samenhangend en acyclisch; een boom met n knopen heeft n−1 ribben.
- Dijkstra: kies steeds de kleinste voorlopige afstand en werk alleen met niet-negatieve gewichten.
- Modulair rekenen: a≡b (mod m) als m | (a−b).
Uitgewerkt voorbeeld
Neem knopen A, B, C, D met ribben A–B (2), A–C (5), B–C (1), B–D (4), C–D (1). Dijkstra vanaf A: A=0; B=2; C=3 via B; D=4 via C. De kortste route A–D is dus A–B–C–D met lengte 2+1+1=4. De route A–C–D heeft lengte 6 en A–B–D heeft lengte 6. Dijkstra vindt de kortste afstand, maar niet automatisch alle kortste routes; noteer daarom je tussenstanden.
Valkuilen
- Euler en Hamilton door elkaar halen.
- Bij Dijkstra een knoop definitief maken voordat alle buren zijn bijgewerkt.
- Een graaf met negatieve gewichten met Dijkstra behandelen.
- Bij een boom het aantal ribben verkeerd tellen.
- Een matrixvermenigvuldiging uitvoeren alsof de volgorde niet uitmaakt.