Waar gaat het over?
Een graaf is een schematische weergave van knooppunten en verbindingen tussen die punten. Hier zie je een graaf met 5 punten (A t/m E) en daartussen een aantal verbindingen (twee richtingsverkeer) of wegen (éénrichtingsverkeer).
Hoe werkt het?
De graaf kun je vertalen in een matrix. Als 1 staat voor "verbinding" en 0 voor "geen verbinding", dan is de verbindingsmatrix `C` voor deze graaf: `C = ((0,0,0,0,1),(0,0,1,1,1),(0,1,0,0,1),(0,1,0,0,1),(1,1,1,1,0))`.
De matrix `C^2` geeft dan de verbindingen met één tussenstation weer. Omdat `C+C^2` geen nullen meer bevat kun je in deze graaf van elk punt naar een ander punt komen in hoogstens twee stappen.
Wie en wanneer?
Rond 1735 kreeg Leonhard Euler (1700 - 1783) het Koningsberger bruggen probleem voorgelegd: "Is het mogelijk zo rond te wandelen tussen de stadsdelen van Koningsbergen, dat je elk van de zeven bruggen over de rivier de Pregel precies één keer over gaat en in een ander stadsdeel eindigt dan je begint?"
Euler loste dit probleem op. Sinds J.J. Silvester in 1878 het begrip graaf heeft ingevoerd, wordt daar een graaf bij gebruikt.
Je onderscheidt dan 'even' en 'oneven' knooppunten, afhankelijk van het aantal lijnen in een knooppunt. Euler toonde aan dat om alle lijnen in een graaf precies één keer achter elkaar te kunnen doorlopen het aantal oneven knooppunten 2 moet zijn.
Meer over grafen:
> In Wikipedia (NL)
> Het handelsreizigers probleem
> Kortste pad algoritme
Op school:
> Grafen en matrices
> Kortste route probleem
In bedrijf:
Beroepen waar grafen wordt gebruikt.