Zeven bruggen van Koningsbergen

Euler's analyse

Ten eerste wees Euler erop dat de keuze van de route binnen elke landmassa er niet toe doet. De enige belangrijke eigenschap van een route is de volgorde waarin de bruggen worden overgestoken. Dus veranderde hij het probleem in abstracte termen. Dit legde de basis van de grafentheorie. Hij verwijderde alle kenmerken behalve de lijst van landmassa's en de bruggen die hen verbinden. In de taal van de grafentheorie verving hij elke landmassa door een abstract "hoekpunt" of knooppunt. Vervolgens verving hij elke brug door een abstracte verbinding, een "edge". Een rand (weg) registreerde welke twee hoekpunten (landmassa's) met elkaar verbonden waren. Op deze manier vormde hij een grafiek.

→ →

De getekende grafiek is een abstract beeld van het probleem. De randen kunnen dus op elke manier verbonden worden. Alleen of twee punten verbonden zijn of niet is van belang. Het veranderen van het beeld van de grafiek verandert de grafiek zelf niet.

Vervolgens stelde Euler vast dat (behalve bij de eindpunten van de wandeling), telkens wanneer men een hoekpunt binnenkomt via een brug, men het hoekpunt verlaat via een brug. In elke wandeling van de grafiek is het aantal keren dat men een hoekpunt binnengaat gelijk aan het aantal keren dat men het verlaat. Als elke brug precies één keer is overgestoken, volgt daaruit dat voor elke landmassa (behalve voor de landmassa's die voor het begin- en eindpunt zijn gekozen) het aantal bruggen dat die landmassa raakt even moet zijn. Als er n bruggen zijn, wordt die landmassa namelijk precies 2n keer overgestoken. Alle vier de landmassa's in het oorspronkelijke probleem worden echter door een oneven aantal bruggen geraakt (één wordt door 5 bruggen geraakt, en elk van de andere drie door 3). Er zijn hoogstens twee landmassa's die het eindpunt van een wandeling kunnen zijn. Dus de stelling van een wandeling die elke brug eenmaal kruist leidt tot een tegenspraak.

In moderne taal toont Euler aan dat het al dan niet mogelijk zijn van een wandeling door een grafiek die elke rand één keer kruist, afhangt van de graden van de knopen. De graad van een knooppunt is het aantal ribben dat het knooppunt raakt. Euler toont aan dat een noodzakelijke voorwaarde voor de wandeling is dat de grafiek verbonden is en precies nul of twee knopen van oneven graad heeft. Dit resultaat van Euler werd later bewezen door Carl Hierholzer. Zo'n wandeling wordt nu een Eulerisch pad of Euler wandeling genoemd. Als er knopen van oneven graad zijn, dan zal elk Euleriaans pad bij één van hen beginnen en bij de andere eindigen. Aangezien de grafiek die het historische Königsberg voorstelt vier knopen van oneven graad heeft, kan deze geen Eulerisch pad hebben.

Eulers werk werd op 26 augustus 1735 gepresenteerd aan de Academie van St. Petersburg. Het werd gepubliceerd als Solutio problematis ad geometriam situs pertinentis (De oplossing van een probleem met betrekking tot de geometrie van de positie) in het tijdschrift Commentarii academiae scientiarum Petropolitanae in 1741. Het is beschikbaar in het Engels in The World of Mathematics.

Belang in de geschiedenis van de wiskunde

In de geschiedenis van de wiskunde wordt Eulers oplossing van het bruggenprobleem van Königsberg beschouwd als de eerste stelling van de grafentheorie. Grafentheorie is een onderwerp dat nu algemeen beschouwd wordt als een tak van de combinatoriek.

Huidige staat van de bruggen

Twee van de zeven oorspronkelijke bruggen werden verwoest tijdens het bombardement op Königsberg in de Tweede Wereldoorlog. Twee andere werden later afgebroken. Zij werden vervangen door een moderne snelweg. De drie andere bruggen zijn overgebleven, hoewel slechts twee ervan uit de tijd van Euler stammen (één werd in 1935 herbouwd). In 2000 waren er dus vijf bruggen in Kaliningrad.

In grafentheoretische termen hebben twee van de knooppunten nu graad 2, en de andere twee graad 3. Er is nu dus een Eulerisch pad mogelijk, maar omdat het op het ene eiland moet beginnen en op het andere eindigen, is het voor toeristen onpraktisch.

Verwante pagina's

• Icosiaans spel
• Hamiltoniaanse weg
• Water, gas en elektriciteit
• Reizende verkoper probleem