paden en cykels

Figuur 21: Een graaf met daarin o.a. een pad abdi en een cykel hfdgh

Een Pad tussen twee punten van een graaf G is een opeenvolging van punten en lijnen van G tussen de opeenvolgende punten, waarin elk punt hooguit één keer voorkomt. We noteren een pad door middel van het rijtje opeenvolgende punten.

Een cykel is een graaf G bestaat uit een pad P = u ... v in G met tenminste drie punten plus de lijn vu van G tussen de twee eindpunten van P. We noteren een cykel door middel van de notatie van P = u ... v, met daaraan toegevoegd een herhaling van het punt u, dus door u ... vu.

opdracht 13

Vormen de gekleurde lijnen in figuur 22 een cykel? Zo nee, waarom niet?

figuur 22

opdracht 14

Probeer in de graaf uit figuur 21 een cykel te vinden met tien punten. Let op, je mag elk punt dus maar één keer gebruiken, behalve het begin- en eindpunt.