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:
gesloten wandeling
Een gesloten wandeling begint en eindigt in dezelfde knoop. Je kunt de wandeling beginnen in om het even welke knoop.
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.
- 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.
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.