Coloration de graphe
Le problème de coloriage de graphes, pour un graphe G non orienté, consiste à attribuer une couleur à chaque sommet de telle sorte qu’une même couleur ne soit pas attribuée à deux sommets adjacents.
Lorsque le graphe est planaire, cela revient au problème de coloriage d’une carte géographique. Le problème de la coloration d’un graphe se pose dans de nombreux domaines pratiques tels que correspondance de motif, la planification sportive, la conception des plans sièges, d’examen horaires, la planification des taxis, et la résolution de Sudoku.
Le nombre minimum de couleur nécessaire pour colorier le graphe G est appelé nombre chromatique de G, et est noté X(G).
Le problème de trouver le nombre chromatique d’un graphe est un problème Np-complet. Le problème de coloriage d’un graphe avec un nombre limité de couleurs – est-il possible de colorier le graphe avec x couleurs, si oui comment ? – est lui aussi un problème Np-complet.
Un graphe planaire est au plus 4-chromatique.
Une chaîne est au plus 2-chromatique.
Un cycle est au plus 3-chromatique.
Une clique de taille n est n-chromatique.
Exemple: Un ensemble donné de tâches doit être affecté à des intervalles de temps, chaque tâche nécessite un seul intervalle. Les tâches peuvent être planifiées dans n’importe quel ordre, mais des paires de tâches peuvent être en conflit dans le sens où elles ne peuvent pas être affectées au même intervalle de temps, par exemple parce qu’elles reposent toutes deux sur une ressource partagée. Le graphique correspondant contient un sommet pour chaque travail et une arête pour chaque paire de tâches en conflit. Le nombre chromatique du graphique est exactement le minimum requis, le temps optimal pour terminer tous les travaux sans conflits.
Problème : cliques
Étant donnés un graphe non orienté G, une clique est un sous-ensemble de sommets qui sont tous connectés deux à deux par des arêtes. En d’autre terme, il s’agit d’un sous-graphe complet.
Trouver une clique w d’ordre k dans un graphe est un problème Np-complet.
Le graphe suivant possède une clique d’ordre 5 :
Problème : stables
Étant donné un graphe non orienté G, un stable est un sous-ensemble de sommets qui ne sont pas connectés deux à deux par des arêtes. Trouver un stable d’ordre k revient à trouver une clique d’ordre k dans le graphe inverse, c’est-à-dire qu’il possède une arête si elle n’existe pas dans le graphe d’origine, et inversement.
Trouver une stable a d’ordre k dans un graphe est un problème Np-complet.
Relation entre les trois problèmes et heuristiques
Nous avons les trois propositions suivantes :
- a(G)=w(non G)
- w(G) = a(non G)
- X(G) >= w(G)
Un stable S de G est dit maximal par inclusion s’il n’existe pas de stable S’ de G tel que S soit strictement contenu dans S’. Une clique K est maximale par inclusion s’il n’existe pas de cliques K’ de G tel que K soit strictement contenu dans K’.
Par cette définition, on en déduit qu’un stable d’ordre maximum est aussi un stable maximal par inclusion, la réciproque n’est pas vrai. L’heuristique classique pour obtenir un stable de grande taille est de chercher un stable maximal par inclusion.
L’algorithme de Brélaz est un algorithme glouton qui permet de connaître une borne maximale du nombre chromatique d’un graphe. Son principe est simple et procède de façon itérative.
Tant qu’il existe un sommet non colorié, nous choisissons le sommet non colorié ayant le plus grand nombre de voisins coloriés avec des couleurs différentes. Ce sommet est alors colorié avec la plus petite couleur possible (les couleurs sont triées dans un ordre croissant arbitraire). Si toutes les couleurs existantes sont déjà utilisées par un voisin, on ajoute une nouvelle couleur à notre palette (ajout d’une couleur d’une valeur supérieur à toutes les autres existantes).
La notion de stable peut aussi fournir des indications sur la coloration d’un graphe. En effet, nous pouvons supposer que dans un stable, tous les sommets possèdent la même couleur. La coloration en k couleurs revient à trouver une partition de l’ensemble des sommets en k stables.
L’algorithme de Welsh et Powell se base sur cette proposition :
- Classer les sommets du graphe dans l’ordre décroissant de leur degré
- En parcourant la liste dans l’ordre, attribuer une couleur non utilisée au premier sommet non colorié p, et attribuer cette couleur à chaque sommet suivant non colorié tel qu’il ne soit pas adjacent au sommet p.
- Revenir à 2 s’il reste des sommets non coloriés dans la liste. Sinon renvoyer la liste.
Exemple
Pour voir la connexion entre le Sudoku et la coloration des graphes, nous allons d’abord décrire le graphe du Sudoku, que nous appellerons par commodité S. Le graphe S a 81 sommets, chaque sommet représentant une cellule. Lorsque deux cellules ne peuvent pas avoir le même nombre (soit parce qu’elles sont dans la même rangée, dans la même colonne, ou dans la même boîte), nous mettons une arête reliant les sommets correspondants du graphe Sudoku S.
Par exemple, puisque les cellules a3 et a7 sont dans la même rangée, il y a un arête joignant leurs sommets correspondants; il y a aussi un arête reliant a1 et b3 (ils sont dans la même case), et ainsi de suite. Chaque sommet du graphique Sudoku a un degré 20, et le graphique a un total de 810 arêtes. S est trop grand être pour dessiner, mais nous pouvons avoir une idée de la structure de S en regardant un dessin partiel. Le dessin montre les 81 sommets de S, mais seulement deux (a1 et e5) ont leur ensemble complet d’arêtes incidentes.
La deuxième étape de la conversion d’un puzzle de Sudoku en un problème de coloration de graphes consiste à attribuer des couleurs aux nombres 1 à 9. Cette affectation est arbitraire et n’est pas un ordre de priorité des couleurs comme dans l’algorithme glouton.
Une fois que nous avons le graphe Sudoku et une attribution de couleurs aux numéros 1 à 9, n’importe quel puzzle de Sudoku peut être décrit par un graphique de Sudoku où certains des sommets sont déjà colorés (ceux correspondant aux données). Pour résoudre le puzzle du Sudoku, tout ce que nous avons à faire est de colorier le reste des sommets en utilisant les neuf couleurs.
FR 
EN 
ES