WisFaq!

Lijngraaf en pad

Wie kan me uitleggen wat een lijngraaf, de lengte van een pad met n punten zijn? Graag met voorbeelden.

saskia de graaf
14-9-2003

Antwoord

Je hebt een graaf G, met punten en lijnen.
Hiervan kun je de lijngraaf L als volgt maken:
De punten van L zijn de lijnen van G, dat wil zeggen: elke lijn van G correspondeert met een punt van zijn lijngraaf.
Twee punten van L worden door een lijn verbonden, als in graaf G de corresponderende lijnen een punt gemeenschappelijk hebben.
Voorbeeld:

De lengte van een pad in een graaf is het aantal lijnen in dat pad. Bijvoorbeeld (zie plaatje) in graaf G is er een pad langs de lijnen 4, 6 en 8. Dit pad heeft 4 punten en 3 lijnen. De lengte van het pad is 3. Zo zijn er nog veel meer paden.
groet,

Anneke
15-9-2003