Les problèmes de coloration
Définition : Coloration usuelle
On appelle coloriage ou coloration usuelle d'un graphe G=(X,E), une application φ de X dans l'ensemble des entiers telle que φ(x) ≠ φ(y) lorsque x et y sont adjacents.
Deux sommets adjacents ne peuvent pas être coloriés de la même couleur et tous les sommets doivent être coloriés.
Définition : Nombre chromatique d'un graphe
On appelle nombre chromatique d'un graphe G=(X,E), le plus petit nombre de couleurs nécessaires pour colorier ce graphe. Ce nombre est noté γ(X,E).
Le nombre chromatique est toujours compris entre 1 et le nombre de points.
Cliquer pour choisir entre les petits et les grands graphes et cliquer sur Précédent ou Suivant pour faire tourner les exemples.
Fondamental :
Le nombre chromatique d'un graphe est égal à 2 si et seulement si il n'existe pas de cycle de longueur impaire.
Fondamental :
Si un graphe contient un sous-graphe complet de p points, alors son nombre chromatique est supérieur ou égal à p.
Les arbres et les forêts qui sont des graphes qui ne contiennent pas de cycle sont 2-chromatiques et peuvent donc être coloriés avec seulement deux couleurs.
Remarque : Stables et coloration usuelle
On peut colorier tous les points d'un stable de la même couleur.
Définition : Problème de coloration
Le problème de coloration usuelle consiste à chercher à colorier un graphe en utilisant autant de couleur que son nombre chromatique, c'est-à-dire en utilisant le moins possible de couleurs.
Cliquez sur Anim, puis sélectionnez un graphe, puis sélectionnez une couleur, puis sélectionnez les points qui prennent cette couleur etc.
Cliquez sur OK pour vérifier si votre coloration est correcte. Vous pouvez la corriger et vérifiez à nouveau etc.
Cette animation n'a pas la prétention de vérifier si vous utilisez un nombre minimal de couleurs.
On ne résout donc pas le problème de coloration usuelle.
Dans le pire des cas, vous pouvez même donner une couleur différente à chaque point.
Fondamental : Complexité du problème de coloration usuelle
Le problème de coloration usuelle est NP-difficile au sens fort.
Tout algorithme qui colore un graphe avec un minimum de couleurs et en garantissant que ce nombre de couleurs est bien minimal a une complexité exponentielle sauf pour des graphes particuliers pour lesquels ce problème est plus facile.
Les algorithmes rapides de coloration sont donc des heuristiques qui ne garantissent pas l'optimalité du résultat.
Sauf pour des cas particuliers où on a su calculer facilement un minorant du nombre de couleurs et où on a effectivement réussi à colorier le graphe avec ce nombre de couleurs minimal (par exemple en détectant des cliques de taille p et en trouvant une coloration de p couleurs).
Les heuristiques les plus simples pour colorier des graphes commencent par chercher un stable et à colorier ses points, ensuite, on travaille sur le sous-graphe où les points coloriés ont été supprimés, puis on recherche un stable dans ce sous-graphe que l'on colorie dans une nouvelle couleur et on recommence ces opérations jusqu'à ce que tous les points du graphe soient coloriés.
Pour explorer l'espace des solutions d'un graphe à colorier de grande taille, on peut utiliser une métaheuristique basée sur l'exploration de voisinages, ou encore un algorithme évolutionnaire de type algorithme génétique.
Définition : Coloration d'une carte planaire
La coloration d'une carte planaire consiste à colorier les faces de cette carte planaire de telle sorte que deux faces qui ont une arête en commun n'ait pas la même couleur.
Fondamental : Théorème des quatre couleurs
On peut colorier les faces d'une carte planaire avec au plus quatre couleurs.
La démonstration de ce théorème est historique. Tout d'abord de nombreux chercheurs l'ont démontré sur de très nombreux cas particuliers, puis des chercheurs ont programmé sur un ordinateur la vérification que ce théorème était vrai pour les graphes qui restaient.
