Eerder in het artikel grafen is uitgelegd wat een graaf is. Grafen kun je opdelen in verschillende categorieën één daarvan is de Eulergraaf. Deze graaf is vernoemd naar de bekende wiskundige Leonard Euler. Leonard Euler vroeg zich af of er ook een wandeling mogelijk was over al de 7 bruggen van koningsbergen. Hij wou bij die wandeling maar één keer over elke brug lopen en weer uitkomen bij zijn beginpunt. Verder in dit artikel komen we terug op de 7 bruggen van koningsbergen
Een graaf mag een Eulergraaf genoemd worden als je een route in de graaf kan maken met alle lijnen en punten in een graaf.Hieronder is een simpele graaf te zien met 3 punten en 3 lijnen.
Een eenvoudige Eulergraaf.
Dit is een Eulergraaf omdat we een route kunnen maken met alle lijnen en punten uit de graaf. De route wordt dan bijvoorbeeld: van punt A naar punt B, van punt B naar punt C en van punt C naar punt A.We zien dat we dus gebruik hebben gemaakt van alle lijnen en alle punten in de graaf.
De 7 bruggen van Koningsbergen
De oude stad Koningsbergen wordt gedeeld door de rivier de Pregel. In deze rivier liggen ook twee eilandjes die samen de stad koningsbergen vormen. De vier delen van de stad Koningsbergen zijn verbonden door 7 bruggen.
Plattegrond van de stad Koningsbergen.
De bewoners van Koningsbergen vroegen zich af of het mogelijk is een wandeling te maken die je precies eenmaal over elke brug stuurt en je uiteindelijk terugbrengt bij het startpunt van de wandeling. HeIaas lukte dit geen enkele inwoner van koningsbergen.
Pas in 1736 werd aangetoond door Leonard Euler dat deze route niet mogelijk was.Dit aantonen deed deze wiskundige met grafen. Hieronder is van de oude stad van Koningsbergen een graaf gemaakt. De punten A, B, C en D stellen de stukken land voor de lijnen tussen de punten stellen de bruggen voor.
De stad Koningsbergen als Eulergraaf.
Waarom is de route onmogelijk?
Wanneer we telleen hoeveel bruggen er van elk eilandje vertrekken, komen we tot de volgende getallen:
- Vanuit punt A vertrekken 3 lijnen
- Vanuit punt B vertrekken 5 lijnen
- Vanuit punt C vertrekken 3 lijnen
- Vanuit punt D vertrekken 3 lijnen
De wandeling over de 7 bruggen van Koningsbergen is niet mogelijk, omdat bij elk punt een oneven aantal lijnen vertrekt. Stel je voor dat we vanuit punt C onze route beginnen, we moeten in dit geval ook weer in punt C eindigen. Als we vanuit punt C naar punt A gaan, vanuit punt A naar Punt B gaan en vanuit punt B naar punt C gaan hebben we al een groot deel van onze route gelopen.
Weergave van deze route vanuit punt C
We zien dat we nu nog maar 4 bruggen moeten bewandelen, maar er is nog maar 1 lijn vanuit punt C.Dus zouden we nooit meer terug kunnen komen in punt C.
Wanneer zou de route wel mogelijk zijn?
De wandelroute zou wel afgelegd kunnen worden als er aan elk punt een even aantal lijnen zou liggen omdat je dan een aankomstpunt en een vertrekpunt hebt.Het volgende filmpje laat zien waarom het probleem van de zeven bruggen van Koningsbergen geen oplossing heeft.
Uitleg over Eulergrafen.