Een kleuring van een graaf \(G\) is een toekenning van kleuren (elementen van een bepaalde verzameling) aan de toppen van \(G\), één kleur per top, zodanig dat adjacente toppen een verschillende kleur krijgen. Wanneer \(k\) kleuren worden gebruikt, wordt dit een \(k\)-kleuring genoemd. Indien er een \(k\)-kleuring voor een graaf \(G\) bestaat, dan noemt men de graaf \(G\) \(k\)-kleurbaar.

Voorbeeld

Gegeven is de graaf in bovenstaande afbeelding. Deze graaf is 3-kleurbaar, de kleuren van de toppen zijn weergegeven in de figuur. Merk op dat er geen twee adjacente toppen zijn die dezelfde kleur hebben.

Gevraagd wordt nu om te bepalen of een graaf \(k\)-kleurbaar is. Ontwerp hiervoor een recursief backtracking algoritme.

Implementeer de gegeven interface Kleuring¹ in een klasse GraafKleuring. Implementeer hiervoor de methode public boolean kleuringMogelijk(UndirectedGraph<String> graaf, int aantalKleuren) die een graaf \(G\) en het aantal te gebruiken kleuren \(k\) als input krijgt. Als output geeft deze methode true terug indien \(G\) \(k\)-kleurbaar is en false indien dit niet zo is.

We maken bij deze oefening gebruik van de grafenbibliotheek graphlib, die o.a. de klasse UndirectedGraph bevat. De volledige API kan je hier² raadplegen. Een andere interessante klasse die je zou kunnen gebruiken in je algoritme is de klasse Node. Neem eerst en vooral eens de API door en stel eventueel vragen hierover voor je begint te programmeren.

Opmerkingen

• Om met de grafenbibliotheek te kunnen werken in IntelliJ moet je het bestand graphlib.jar³ toevoegen aan je project. Hiervoor ga je naar File -> Project Structure…. Vervolgens kies je Libraries en klik je op de knop met het plusteken (+). Kies voor Java en navigeer naar het gedownloade bestand graphlib.jar.
• Pas de graaf die als input wordt meegegeven aan het algoritme niet aan. Indien je dit wel doet, zullen de testen falen.

Gebruik eventueel de testklasse SimpleTest⁴ om je oplossing lokaal te testen. Je kan hierin eenvoudig extra testgevallen toevoegen.