paden langs een graaf

pad

Een pad is een aaneenschakeling van lijnen tussen punten van een graaf. Een Eulerpad in een graaf is een pad dat elk punt in de graaf precies één keer doorloopt. Dit kan op twee manieren: met een open pad of een gesloten pad.

Open pad

Een open pad begint en eindigt op twee verschillende punten:
Image

gesloten pad

Een gesloten pad begint en eindigt in hetzelfde punt. Je kunt het pad beginnen op om het even welk punt.
Image

graad van een punt

De graad van het punt van de graaf is het aantal lijnen dat samenkomt in het punt. Of een Eulerpad wel of niet mogelijk is, hangt af van deze graden. Een Eulerpad is slechts mogelijk wanneer er nul of twee punten van oneven graad zijn.
  • Zijn er twee punten van oneven graad, dan moet de wandeling starten in het ene oneven punt en eindigen in het andere oneven punt. Je krijgt een open pad.
  • Zijn er geen punten van oneven graad, dan kan de wandeling overal beginnen en eindigt de wandeling waar hij begonnen is. Je krijgt een gesloten pad.
Geen van beide is mogelijk in Königsberg omdat er meer dan twee punten zijn met een oneven graad.

De graden in Königsberg

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