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.