Overeenkomst van vlakke graaf en kleurenprobleem

Wij moeten voor de praktische opdracht van wiskunde de volgende vraag beantwoorden:
Wat is een vlakke graaf en hoe kan het probleem van het kleuren van landkaarten gekoppeld worden aan een graaf.
Wij weten al wel wat een vlakke graaf is maar wij hebben geen idee hoe je die kunt koppelen een het kleuren van landkaarten.

Wij hopen dat u ons hiermee kunt helpen.
Alvast bedankt

Marly
Leerling bovenbouw havo-vwo - vrijdag 18 maart 2005

Antwoord

Laat de knopen overeenkomen met de landen in de landkaart, en verbindt 2 knopen met elkaar als de overeenkomende landen aan elkaar grenzen. Als alle landen een aaneengesloten geheel vormen (dus geen exclaves hebben), zal de resulterende graaf een vlakke graaf zijn (waarom?). Geef kleuren aan de knopen in de graaf.

Ik hoop dat je hiermee gered bent.

AE
vrijdag 18 maart 2005

©2001-2024 WisFaq