Wat is precies een elementair circuit?

We hebben de volgende definitie meegekregen: Een elementair circuit is een lus zonder knoopherhalingen.

Ik heb het vermoeden dat dit een generalisatie is van een hamilton path is. Klopt dit? En zo ja, is een pad van A naar B dus altijd een elementair circuit?

Alvast bedank,
Vincent v/d Meer

Vincen
Student universiteit - dinsdag 23 september 2003

Antwoord

Je kunt inderdaad zeggen dat een Hamiltoncircuit een elementair circuit is dat alle knopen bevat, dus een specifiek elementair circuit.
Een pad van A naar B is zeker niet altijd een elementair circuit. Ten eerste is het geen circuit (tenzij A=B) en ten tweede kan een pad best vaker door eenzelfde knoop gaan.
groet,

dinsdag 23 september 2003

©2001-2024 WisFaq