Het inkleuren van grafen is een traditioneel probleem met vele praktische toepassingen. Zij gegeven een graaf G (meestal zullen we een ongerichte graaf beschouwen). Een inkleuring van de graaf G met n kleuren is een toekenning van een "kleur" 0, ..., n-1 aan elke knoop zodanig dat voor elke verbinding in de graaf begin- en eindknoop een verschillende kleur hebben.

Een bipartiete graaf is per definitie een graaf die je met twee kleuren kan inkleuren. De roemruchte vierkleurenstelling zegt dat je elke planaire graaf met vier kleuren kan inkleuren.

Als je een grote graaf hebt is het niet zo simpel om een juiste inkleuring te vinden. Eén mogelijkheid is gebruik te maken van simulated annealing. De code daarvoor krijg je van ons netjes verpakt in een header file.

Het deficit van een kleurenaantal is het minimaal aantal fouten dat je met dit aantal kan bereiken (gegeven de graaf G, natuurlijk), waarbij een fout een verbinding is die twee knopen met dezelfde kleur verbindt.

Schrijf een programma dat, gegeven een graaf G, het deficit uitschrijft van kleurenaantallen beginnend bij 1, tot je een deficit van 0 bereikt. Omdat je werkt met simulated annealing krijg je maar een benaderde waarde voor het deficit. Probeer je programma zo te tunen dat een zo goed mogelijke benadering in een redelijke tijd bereikt wordt. Laat het programma los op de zoogdierengraaf uit een vorige opgave, en ook op de landengraaf uit een nog vorigere opgave.