paden en cykels
pad
Een pad van een knoop A naar een knoop B in een graaf is een opeenvolging van bogen in een graaf waarop je van A naar B kunt wandelen zonder dat je onderweg meer dan één keer eenzelfde knoop of boog passeert. M.a.w.: een pad is een wandeling waarin alle knopen en bogen verschillend zijn.
Zo kan je in onderstande graaf op verschillende manieren van A naar B wandelen.
Links zie je het pad (A, C, E, B) met lengte 3, rechts het pad (A, D, F, E, B) met lengte 4.
Opmerking: Een pad met lengte k heeft k verschillende bogen en k+1 verschillende knopen.
cykel
Een cykel is een gesloten pad. Met andere woorden beginpunt en eindpunt zijn gelijk.
Op onderstaande afbeelding zie je hoe je van A naar A kunt wandelen zonder meer dan één keer dezelfde knoop of boog te passeren.
Experimenteer zelf
Experimenteer zelf in onderstaande applet: Creëer een graaf met de versleepbare lijnstukken en probeer paden en cykels te definiëren in je graaf.
Het versleepbare groene punt laat een spoor achter, dat je kunt wissen met de knop wis spoor.
Tip:
- Versleep eerst het punt naar het gewenste startpunt,
- wis daarna het spoor
- en definieer tenslotte het pad of de cykel door het punt te verslepen op het gewenste traject.
Kortste pad
Een bekende toepassing is het bepalen van het kortste pad tussen twee knopen. Hiervoor bestaan algoritmes Je leert er meer over in het GeoGebraboek Kortste pad.