Matrices en grafen > Totaalbeeld
123456Totaalbeeld

Achtergronden

Rond 1735 kreeg de Zwitserse wiskundige Leonhard Euler (1700 - 1783) het volgende vraagstuk voorgelegd: "Is het mogelijk zo rond te wandelen tussen de verschillende stadsdelen van Koningsbergen (nu Kaliningrad in Rusland), dat je elk van de zeven bruggen over de rivier de Pregel precies één keer over gaat?" Dit is het beroemde Koningsberger bruggenprobleem.

Euler pakte dit probleem systematisch aan en loste het op. Sinds J.J. Silvester in 1878 het begrip graaf heeft ingevoerd, wordt dit probleem opgelost door er een graaf bij te maken.
Je onderscheidt dan "even" en "oneven" knooppunten, afhankelijk van het aantal verbindingslijnen dat in een knooppunt samenkomt. Euler toonde aan dat om alle verbindingen in een graaf precies één keer achter elkaar te kunnen doorlopen het aantal oneven knoopppunten of 2 moet zijn.

De graaf die past bij het Koningsberger bruggenprobleem heeft vier oneven knooppunten en dus is de beschreven rondwandeling niet mogelijk.

verder | terug