wandelingen langs een graaf

wandeling

Een wandeling is een aaneenschakeling van bogen tussen knopen van een graaf. Een Eulerwandeling in een graaf is een wandeling die elke boog in de graaf precies één keer doorloopt. Je mag hierbij meer dan één keer langs eenzelfde knoop passeren. Dit kan op twee manieren: met een open wandeling of een gesloten wandeling.

Open wandeling

Een open wandeling begint en eindigt in twee verschillende knopen:
Image

gesloten wandeling

Een gesloten wandeling begint en eindigt in dezelfde knoop. Je kunt de wandeling beginnen in om het even welke knoop.
Image

graad van een knoop

De graad van het koopvan de graaf is het aantal bogen dat samenkomt in de knoop. Of een Eulerwandeling wel of niet mogelijk is, hangt af van deze graden.
  • Een knoop met even graad kan je steeds gebruiken om aan te komen en te vertrekken
  • Een knoop met een oneven graad kan je enkel gebruiken om aan te komen of te vertrekken. Maar je kunt maar hoogstens 2 knopen gebruiken om je wandeling te starten of te eindigen.
Een Eulerwandeling is dus enkel mogelijk als er nul of twee knopen met een oneven graad zijn.
  • Zijn er twee knopen met oneven graad, dan moet de wandeling starten in de ene oneven knoop en eindigen in de andere. Je krijgt een open wandeling.
  • Zijn er geen knopen met oneven graad, dan kan de wandeling overal beginnen en eindigt de wandeling steeds waar hij begonnen is. Je krijgt een gesloten wandeling.
In Königsberg zijn er meer dan twee knopen zijn met een oneven graad. Een Eulerwandeling is dus niet mogelijk.

De graden in Königsberg

Je kunt in de applet verbindingen leggen of verbreken door er op te klikken. Tussen elke twee knopen kan je maximum twee verbindingen leggen. Leg eventuele nieuwe bruggen of sluit er af en probeer met zo weinig mogelijk ingrepen een Eulerwandeling mogelijk te maken in de stad. Creëer in volgende applet een graaf met een gesloten of open wandeling en test door een startpunt te kiezen en daarna het rode punt te verslepen de voorwaarden uit om een Eulerwandeling te hebben.