\require{AMSmath}

Wat is een duale graaf?

Wat is een duale graaf?

sisi
Leerling bovenbouw havo-vwo - woensdag 18 februari 2004

Antwoord

Dag sisi,

Een duale graaf G* kan geconstrueerd worden uit de oorspronkelijke graaf G. Dit gaat als volgt:

Kies in elk gebied van de oorspronkelijke graaf G een punt (let speciaal op het "buitengebied" van G). Deze punten vormen de knooppunten van G*.
Twee knooppunten van G* worden verbonden als de corresponderende gebieden in G een gemeenschappelijke grenslijn hebben. Dit gebeurt zodanig dat die gemeenschappelijke grenslijn precies éénmalig wordt gesneden, en geen punt gemeen heeft met de andere oorspronkelijke takken.
Als een tak de grenslijn is tussen twee dezelfde gebieden (zie tekening hieronder als voorbeeld), dan krijgt G* een lus die de betreffende tak precies éénmaal snijdt., en ook geen punten gemeen heeft met de andere takken van de oorspronkelijke graaf.

En waarom doen mensen dit? Wel, soms kan je verrassende eigenschappen van de graaf ontdekken, met behulp van deze duale graaf (de details zal ik je sparen ).

Erica
woensdag 18 februari 2004

©2001-2024 WisFaq