Coloration de graphe
| Sommaire |
Définition
Il existe deux façons de colorer un graphe.
- La première consiste à attribuer à chaque sommet une couleur sans que deux sommets reliés par une arête soient de la même couleur. C'est cette notion qui est utilisée dans le théorème des quatre couleurs et ses dérivés. Le nombre minimal de couleurs est appelé nombre chromatique qui se note γ(G). Il s'agit d'un problème classique en théorie des graphes.
- La seconde consiste au contraire à affecter certains sommets d'une couleur et à propager celle-ci. C'est la méthode dite du graphe chromatique qui est utilisée pour optimiser la génération de code sur une machine comportant un grand nombre de registres. Les méthodes de graphe chromatique permettent parfois de gagner un facteur de vitesse de 3 et plus sur un programme.
Propriétés
- Déterminer le nombre chromatique d'un graphe est un problème NP-Complet dans le cas général. Il existe cependant des algorithmes polynomiaux pour certaines familles de graphes.
- Pour tout graphe biparti, γ(G) = 2
- Soit un graphe G=(S,A), γ(G) peut-être de façon équivalente définit comme étant le plus petit entier r tel qu'il existe un homomorphisme de S vers Kr.
- Si D est le degré maximal du graphe, c'est-à-dire le plus grand degré parmi les degrés des sommets, alors le nombre chromatique est inférieur ou égal à 1 + D. Le nombre chromatique est aussi supérieur ou égal à l'ordre du plus grand sous-graphe complet du graphe.
Méthodes
Algorithme de Welsh et Powell
- Repérer le degré de chaque sommet.
- Ranger les sommets par ordre de degrés décroissants. (dans certains cas plusieurs possibilités)
- Attribuer au premier sommet (A) de la liste une couleur.
- Suivre la liste en attribuant la même couleur au premier sommet (B) qui ne soit pas adjacent à (A).
- Suivre (si possible) la liste jusqu'au prochain sommet (C) qui ne soit adjacent ni à A ni à B.
- Continuer jusqu'à ce que la liste soit finie.
- Prendre une deuxième couleur pour le premier sommet (D) non encore colorié de la liste.
- Répéter les operations 4 à 6.
- Continuer jusqu'à avoir colorié tous les sommets.
Cette méthode n'aboutit pas forcément à une coloration minimale. Il faut donc observer si on peut faire mieux (c'est-à-dire avec moins de couleurs).
Partition en sous-graphes stables
Un sous-graphe stable est un sous-graphe dont les sommets ne sont pas adjacents. Ses sommets peuvent donc être colorés de la même couleur. Le but est de trouver un nombre minimal de sous-graphes stables pour utiliser le moins de couleurs possible.
Applications
Le théorème des quatre couleurs
- Peut-on colorier une carte avec quatre couleurs de sorte que deux pays ayant une frontière commune (autre que réduite à un point) n'aient jamais la même couleur?
On ne trouvait pas de contre-exemple de cette affirmation empirique. Restait à la démontrer.
Une démonstration publiée en 1879 par Kempe, s'est révélée comporter une erreur. Il a fallu attendre près d'un siècle de recherche pour voir aboutir une démonstration valide.
En 1976, deux américains Kenneth Appel et Wolfgang Haken affirment avoir démontré le théorème des quatre couleurs. Leur démonstration partage la communauté scientifique : pour la première fois, en effet, la démonstration exige l'usage de l'ordinateur pour étudier les 1200 cas critiques. Le problème de la validation du théorème se trouve alors déplacé vers le problème de la validation :
- d'une part de l'algorithme d'exploration
- d'autre part de son implémentation sous forme de programme
Depuis 1976, l'algorithme d'Appel et Haken a été repris et simplifié par d'autres chercheurs. D'autres programmes informatiques, écrits de façon indépendante du premier, aboutissent au même résultat. Il existe ainsi une version entièrement formalisée de la preuve, formulée avec Coq.
Organisation
Permet d'optimiser :
- exemple 1 : Organiser un examen suivant les matières que doit passer chaque étudiant. Comment mettre en parallèle plusieurs épreuves sans léser un candidat ?
- exemple 2 : Optimiser l'utilisation des machines de travail. Comment mettre en parallèle des fabrications utilisant plusieurs machines ?
- exemple 3 : Problème d'incompatibilité. Comment faire cohabiter des personnes ou animaux en tenant compte de leur incompatibilité?