Exemple du coloriage de la carte

Il s'agit de colorier les différentes régions d'une carte de sorte que si deux régions sont voisines alors elles sont de couleurs différentes. On peut montrer que le nombre maximal de couleurs nécessaires pour colorier une carte plane est 4.

Ce problème est un cas particulier du coloriage des sommets d'un graphe (deux sommets adjacents du graphe doivent toujours être de couleurs différentes). Il s'agit d'un problème NP-complet: il n'existe pas d'algorithme polynomial déterministe pour résoudre ce problème. De nombreux cas concrets se ramènent à ce problème: problème des examens, d'emploi du temps, de classification, ...

Formalisation du problème:



Christine SOLNON
Thu Jul 10 10:26:38 METDST 1997