Het chromatisch getal van een graaf is het minimaal aantal kleuren dat nodig is om de toppen van de graaf te kleuren zodat geen twee adjacente toppen dezelfde kleur hebben. Voor de onderstaande graaf is dat bijvoorbeeld 3. Dit getal berekenen is een computationeel zwaar probleem, dus zullen we het hier benaderen met gretige algoritmen.
Implementeer de gegeven interface GreedyColouring1 in een klasse MyGreedyColouring.
Hiervoor schrijf je een methode public HashMap<Node<Integer>,Integer> greedyColouring(UndirectedGraph<Integer> graph) die een toppenkleuring berekent waarvan het aantal gebruikte kleuren een goede benadering (ondergrens) is van het chromatische getal van deze graaf. (De kleurklasses worden dus voorgesteld door gehele getallen.)
Schrijf hiervoor minstens twee gretige heuristieken, die elk op een verschillende manieren kleuren toekennen aan de toppen, en later de kleur van een top niet meer wijzigen. Voor elke graaf bereken je al je heuristieken en geeft dan de beste terug.
Zoals steeds kan je met behulp van de klasse SimpleTest2 jouw code lokaal testen. De documentatie over de gebruikte grafenbibliotheek3 vind je hier4.