Corrigé de l'exercice 2

• X = {X1, X2, ..., X14}

  (On associe une variable Xi différente par région i à colorier.)

• pour tout Xi élément de X, D(Xi) = { bleu, rouge, vert, jaune }

  (Chaque région peut être coloriée avec une des 4 couleurs.)

• C = { Xi ≠ Xj / Xi et Xj sont 2 variables de X correspondant à des régions voisines }

  (2 régions voisines doivent être de couleurs différentes.)

Pour être plus précis, on peut définir explicitement les relations de voisinage entre régions, par exemple à l'aide d'un prédicat voisines/2, tel que voisines(X,Y) soit vrai si X et Y sont deux régions voisines. Ce prédicat peut être défini en extension, en listant l'ensemble des couples de régions ayant une frontière en commun :

voisines(X,Y) <=> (X,Y) élément-de {(1,7), (1,9), (1,10), (1,11), (1,12), (1,13), (2,8), (2,12), (2,14), (3,7), (3,10), (3,14), (4,9), (4,11), (4,14), (5,8), (5,11), (5,12), (6,7), (6,13), (6,14), (7,1), (7,3), (7,6), (7,10), (7,13), (7,14), (8,2), (8,5), (8,12), (9,1), (9,4), (9,10), (9,11), (10,1), (10,3), (10,7), (10,9), (10,14), (11,1), (11,4), (11,5), (11,9), (11,12), (12,1), (12,2), (12,5), (12,8), (12,11), (12,13), (12,14), (13,1), (13,6), (13,7), (13,12), (13,14), (14,2), (14,3), (14,4), (14,6), (14,7), (14,10), (14,12), (14,13)}

C = { Xi ≠ Xj / Xi et Xj sont 2 variables différentes de X et voisines(Xi,Xj) = vrai }

Ce problème de coloriage d'une carte est un cas particulier du problème du coloriage des sommets d'un graphe (deux sommets adjacents du graphe doivent toujours être de couleurs différentes). De nombreux problèmes "réels" se ramènent à ce problème de coloriage d'un graphe : problème des examens, d'emploi du temps, de classification, ...