In het kaartenkleuren-probleem waarmee we in dit lesje gaan werken is het essentieel om het minimum aantal kleuren te vinden – 2,3 of 4 – dat nodig is om een bepaalde kaart in te kleuren.  Het vermoeden dat iedere kaart ingekleurd kan worden met maximaal 4 kleuren is voor het eerst beschreven in 1852, maar het bleef onbewezen tot 1976. De computerwetenschap zit nog vol met onopgeloste problemen, en wetende dat de vier-kleuren-stelling pas is bewezen na meer dan 120 jaar aandacht van vele onderzoekers is een aanmoediging voor diegenen die nu aan andere problemen werken waarvan de oplossing al decennia op zich laat wachten.

Kaarten kleuren hoort bij een algemene verzameling van problemen die aangeduid worden als “het kleuren van grafen”. Een graaf in de computerwetenschap is een abstracte representatie van relaties. Hierboven hebben we de kaart uit de eerste opdracht als graaf getekend. Landen zijn punten (knopen) geworden en de landen zijn verbonden door een lijn (kant) wanneer ze een grens delen.

Zoals al ter sprake kwam in activiteit 0 9 over Modderstad, wordt de term “graaf” in de computerwetenschap gebruikt voor figuren met cirkels, de knopen, die objecten weergeven met lijnen daartussen die een soort relatie tussen de knopen aangeven. De graaf hierboven laat de kaart van het begin van deze activiteit zien. De knopen zijn de landen en de lijnen laten zien dat deze landen een gezamenlijke grens hebben. Bij de graaf is het de bedoeling dat de knopen die door een lijn met elkaar verbonden zijn niet dezelfde kleur mogen krijgen volgens de kleurenregel die we gesteld hadden. Anders dan op een kaart, is er bij een graaf geen limiet aan kleuren die mogelijk nodig zijn, omdat er met behulp van lijnen veel meer relaties toegevoegd kunnen worden, het tweedimensionale karakter van een kaart beperkt zich in het weergeven van relaties. Het “graaf-kleur-probleem” is het minimum aantal kleuren te vinden dat nodig is voor een bepaalde graaf.

In de graaf hiernaast geven de knopen schoolvakken aan. Een lijn tussen de vakken betekent dat op zijn minst 1 leerling beide vakken volgt en deze vakken dus niet tegelijk gegeven kunnen worden. Door het zo weer te geven, wordt het maken van een schoolrooster precies hetzelfde probleem als het kleurprobleem, waar de verschillende kleuren nu verschillende tijdstippen aangeven. In de computerwetenschap krijgen graaf-kleur-algoritmes veel aandacht. Ze worden gebruikt voor veel dagelijkse problemen, hoewel ze waarschijnlijk nooit worden gebruikt bij het kleuren van kaarten! Onze arme cartograaf is maar verzonnen.

Er bestaan letterlijk duizend andere problemen die gebaseerd zijn op grafen. Sommige worden ergens anders in dit boek beschreven, zoals bij activiteit 9, de minimaal opspannende boom, en bij de dominerende verzamelingen bij activiteit 14. Grafen zijn een zeer algemene manier om data weer te geven en kunnen gebruikt worden om allerlei situaties schematisch weer te geven, zoals een kaart met wegen en kruispunten, verbindingen tussen atomen in een molecuul, computernetwerken, verbindingen tussen onderdelen op een printplaat en relaties tussen opdrachten bij een zeer groot project. Om deze reden vinden computerwetenschappers problemen die met een graaf weergegeven kunnen worden al heel lang zeer fascinerend.

Veel van deze problemen zijn erg ingewikkeld – het vraagstuk is niet per se ingewikkeld, maar ze kunnen heel veel tijd kosten om op te lossen. Neem bijvoorbeeld een op het oog niet eens zo heel groot probleem, het maken van het meest efficiënte rooster voor een school met 30 leraren en 800 leerlingen kan jaren, zelfs eeuwen in beslag nemen voor een computer, zelfs met het beste algoritme. De oplossing van dit probleem is allang irrelevant lang voordat de oplossing gevonden is en de kans is zelfs groot dat de computer al kapot is voor het een oplossing heeft gevonden! Zulke problemen worden in de praktijk alleen opgelost doordat we niet de allerbeste oplossing accepteren, maar een acceptabele oplossing ook wel goed vinden. Als we erop zouden staan dat we gegarandeerd de beste oplossing zouden willen, zou dit probleem onpraktische groot, oftewel onhandelbaar zijn.

De computertijd die we nodig hebben om kleurproblemen aan te pakken neemt exponentieel toe met de grootte van de graaf. Neem het kaartkleurprobleem. Dat kan opgelost worden door alle mogelijk manieren van kleuren toe te passen. We weten dat er een maximum van 4 kleuren nodig is, dus we moeten iedere combinatie van inkleuren van de 4 kleuren uit proberen. Als er een n aantal landen is, dan zijn er 4 tot de n-de combinaties mogelijk. En dit aantal groeit dus razendsnel, voor ieder land dat toegevoegd wordt maakt het aantal mogelijke combinaties al 4 keer zo groot en duurt het dus ook 4 keer zo lang om een oplossing te vinden. Zelfs als we een computer uitvinden die het probleem voor, laten we zeggen, 50 landen in een uur op kan lossen, heeft het toevoegen van 1 extra land 4 uur extra nodig en als we dan 10 landen toevoegen duurt het al meer dan een jaar om tot een oplossing te komen. Dit soort problemen verdwijnen niet door het simpel uitvinden van nog snellere computers, het probleem is te groot!

Graafkleuren is een goed voorbeeld van een probleem waar de tijd voor het vinden van een oplossing exponentieel groeit. Voor kleine voorbeelden van het probleem, zoals de kleine kaarten in deze activiteit, is het vrij gemakkelijk een optimale oplossing te vinden, maar zo gauw het aantal landen boven de 10 uitkomt wordt het al een hels karwei om dit met de hand te doen en met honderd of meer landen kan het zelfs voor een computer heel lang duren om alle combinaties uit te proberen om de kaart te kleuren en zo de meest optimale te vinden.

Veel dagelijkse problemen zijn precies zo, maar moeten sowieso opgelost worden. Computerwetenschappers gebruiken methoden die goede, maar niet perfecte, oplossingen geven. Deze heuristische technieken leveren vaak oplossingen die zeer dicht bij de optimale oplossing liggen, zijn vaak snel te berekenen en geven oplossingen die prima in het dagelijks leven te gebruiken zijn. Voor scholen is het in de meeste gevallen geen probleem om een klaslokaal meer te gebruiken dan in de optimale situatie en de arme cartograaf zal het vast niet verschrikkelijk vinden om een kleur te veel te gebruiken bij het inkleuren van een kaart.

Niemand heeft ooit bewezen dat er geen efficiënte manier is om dit soort problemen op te lossen met de computer, maar ook niemand heeft ooit bewezen dat er wel efficiënte manier is. Computerdeskundigen denken niet dat er ooit een efficiënte manier gevonden zal worden. We zullen nog meer over dit probleem leren in de volgende 2 activiteiten.

Geschikt voor leeftijd: 7 jaar en ouder

Download hier lesje 13: Onhandelbaarheid – kaarten kleuren