Coloration des sommets d'un graphe

Commençons par définir ce que l'on cherche à faire :

Le graphe discret par exemple admet une 1-coloration, 2-coloration, ..., jusqu'à une $n$-coloration :

On voit vite que ceci se généralise et que l'on a :

Notez que l'on a déjà vu un problème de coloration. En effet les nombres de Ramsey correspondent à la recherche de cliques de tailles donnée dans la 2-coloration d'un graphe complet.

Problème

Continuons notre exploration en essayant de chercher le nombre minimum de couleurs possible pour colorer les sommets d'un graphe. Les cycles paires admettent une 2-coloration (mais pas une 1-coloration puisqu'ils ont une arête) et les cycles impaires quant à eux uniquement une 3-coloration :

Et les cliques ?

Explicitons cette borne minimum de coloration :

On a déjà quelques $\chi$ pour des classes de graphes connus :

• $\chi(G) = 1$ si (et seulement si) $G$ est le graphe discret,
• $\chi(G) = 2$ si $G$ est un chemin ou un cycle de longueur pair,
• $\chi(G) = 3$ si $G$ est un chemin ou un cycle de longueur impair,
• $\chi(G) = v(G)$ si $G$ est le graphe complet.

Et une première borne évidente :

Le problème principal que l'on veut résoudre est celui-ci :

Sa version optimisation est celui-ci :

On remarque que $k$ fait parti du problème, ce n'est pas une entrée. Il existe donc un problème de reconnaissance différent pour chaque $k$. Il est clair qu'ils sont tous dans NP :

$k$-colorabilité ≤ $k+1$-colorabilité

Cela se gâte pour $k>2$. On va maintenant montrer la NP-complétude du problème de $k$-colorabilité pour $k>2$.

On a vu précédemment que le problème de reconnaissance est polynomial (et même linéaire) pour les graphes 2-colorable et pour les graphes 1-colorable (c'est le graphe discret). De plus, vous aller le montrer, on peut facilement réduire la reconnaissance d'un graphe $k$-parti à un cas particulier de la reconnaissance d'un graphe $(k+1)$-parti :

3-colorable est NP-Complet

Pour terminer, il nous reste à montrer que 3-colorable est NP-complet.

Nous allons pour cela utiliser un gadget sous la forme du graphe ci-dessous :

L'intérêt de ce graphe est qu'il est trois colorable, et de plein de façons différente :

Sauf une seule, lorsque les 3 sommets ne faisant pas parti d'un triangle sont de la même couleur que celle du sommet formant le bas du dernier triangle :

C'est cette propriété que l'on va utiliser pur prouver la NP-complétude de la 3 coloration d'un graphe.

La réduction de la preuve de la proposition précédente est plus complexe que toutes celles que l'on a fait jusqu'à présent, Le gadget utilisé n'étant pas trivial. Montrons ce qu'il donne sur notre exemple fil rouge des réduction depuis 3-SAT :

• $G_1$ :
• $C_1$ :
• $C_2$ :
• $C_3$ :
• $C_4$ :

Ce qui donne le graphe final :

Ce graphe est 3-colorable (on a associé une couleur à chaque stable) :

Graphes bi-parti

Le problème de la 2-colorabilité définit une classe très importante de graphe, les graphes bi-partis :

Par exemple le graphe suivant :

La réduction pour montrer que 3-colorable est NP-Complet ne fonctionne pas pour la 2-colorabilité, savoir si un graphe est 2-colorable est même rapide en utilisant un algorithme de marquage qui associe une couleur à chaque sommet.

On considère que le graphe est connexe dans l'algorithme suivant. S'il ne l'est pas on le relance sur chacune des parties connexes.

Initialisation :

    On possède deux couleurs.
    Soit x un sommet du graphe que l'on marque avec une couleur

Boucle principale :

    tant qu'il existe x, un sommet marqué non examiné:

        examiner x
        pour chaque voisin y de x :
            si y est marqué avec la couleur de x:
                FIN : le graphe n'est pas biparti
            sinon si y n'est pas marqué:
                marquer y avec la couleur différente de celle de x
    
    FIN : le graphe est biparti et la couleur des sommets determine les 2 stables

1. on voit bien tous les sommets car connexe : on le fait par récurrence sur la longueur du chemin entre $x$ et $y$
2. chaque couleur est obligatoire
3. linéaire n+m si on utilise un parcours en profondeur (les éléments marqués sont dans une pile).

L'algorithme fonctionne clairement si le graphe est bi-parti puisque par composante connexe il n'y a qu'une seule possibilité de bi-partition une fois 1 élément assigné :

La réciproque est également vraie :

Si l'algorithme s'arrête en répondant NON, c'est qu'il existe un voisin $y$ du sommet examiné $x$ marqué avec la même couleur. Il existe donc un chemin entre le premier élément marqué de l'algorithme, disons $x_0$, et $x$ alternant de couleur en couleur :

Si $y$ est marqué c'est qu'on la déjà vu, disons en examinant le sommet $x' \neq x$. Il existe donc aussi un chemin alternant de couleurs entre $x_0$ et $x'$ qui est de couleur différente de $x$ :

On se trouve donc globalement dans une situation où il existe un chemin alternant les couleurs entre $x_0$ et un chemin alternant les couleurs entre $x$ et entre $x_0$ et $x'$. Ces deux chemins sont de parité différente puisque $x$ et $x'$ sont de couleurs différentes :

En remontant ces deux chemins jusqu'au premier élément en commun (il existe puisque $x_0$ fait parti des deux chemins) on obtiendra alors forcément un cycle de longueur impaire :

On en conclut :

Cette alternance de couleur est appelé chaîne de Kempe et est un outil très puissant en coloration de graphe.

Enfin l'algorithme nous donne une caractérisation des graphes bi-partis :

Les graphes bi-parti sont une classe de graphes très générale. On les retrouve un peu partout dans des preuves, en support à des algorithmes généraux, etc car de nombreux problèmes NP-complets en général sont polynomiaux pour eux (par exemple la coloration...).

Un algorithme glouton

L'algorithme est tout simple :

Les couleurs sont des entiers. On associe à chaque sommet la couleur valant le plus petit entier strictement positif non encore affecté à un de ses voisins (ceux étant avant lui dans l'ordre).

Ce qui donne le code :

Soit v_1, ... v_n un ordonnancement des sommets de G


pour chaque i de 1 à n:
    c(v_i) = min N^+ \ { { c(v_j) | v_iv_j ∈ E, j < i} }

Une fois l'ordre choisi la complexité de l'algorithme est linéaire en la taille du graphe $\mathcal{O}(m + n)$ puisque pour chaque sommet on examine tous ses voisins. . Bien sur, cet ordre est primordial puisqu'il peut trouver un bon coloriage comme un coloriage moins bon.

Par Exemple pour le graphe ci-après :

Si on prend l'ordre alphabétique on obtient un 4 coloriage :

Alors que l'on peut avoir un 3 coloriage :

Ce qui est le minimum (puisqu'il existe un cycle impair il n'et pas bi-parti).

TBD algo avec un tableau : On garde un tableau avec les sommets dont la couleur vaut l'index. on parcours tous les voisins et on met T[i] = id nœud courant. puis on regarde si T[1] vaut l'id du nœud courant, si oui on passe à 2 et sinon on met 1 comme couleur au nœud courant.

La propriété que suit cet algorithme est, quelque soit l'ordre :

Cette propriété nous donne une borne de la colorabilité d'un graphe :

Cette borne est atteinte, on l'a vue, pour les graphes complets et les cycles impair... Et, on le montrera plus tard, c'est les seuls fois.

Algorithme de Welch-Powel

L'algorithme de Welch-Powel choisi pour l'ordre celui du nombre de degré décroissants. Avec cet ordre on cherche à minimiser $\min({\delta(v_i), i-1}$ :

• lorsque $i$ est petit $\delta(v_i)$ est grand
• lorsque $i$ est grand et $\delta(v_i)$ est petit

La complexité augmente puisque trouver l'ordre rajoute une complexité de $\mathcal{O}(n\ln(n))$, pour une complexité totale de $\mathcal{O}(n\ln(n)+m)$ Notez que même si cet ordre est raisonnable et permet souvent de trouver un bon coloriage il peut tout de même se tromper pour des cas simples :

Algorithme DSATUR

L'algorithme DSATUR est une optimisation de l'algorithme de Welch-Powel. Il choisi à chaque étape le sommet le plus contraint.

On appelle contrainte d'un sommet le nombre de couleurs différentes de ses voisins.

L'algorithme DSATUR prend à chaque étape un sommet ayant le plus grand degré parmi les sommets les plus contraints.

Cette variante fonctionne maintenant avec les cycles pair et même avec tous les graphes bi-parti. Le choix du sommet est cependant maintenant en $\mathcal{O}(n)$ ce qui fait passer la complexité totale en $\mathcal{O}(n^2+m)$

TBD optimisation avec les tas de Fibonacci ?

Avec note exemple, l'ordre est encore différent :

Ordre aléatoire

Quelque soit l'optimisation il n'est pas à performance garantie, on peut forger des exemples qui rendent une coloration non optimale. De là comme l'algorithme va vite utiliser plusieurs ordre aléatoire puis prendre le meillleur donne souvent de bon résultats. Ceci est lié à un résultat curieux que nous ne démontrerons pas :

Coloration par composition de graphes

La coloration des sommets d'un graphe étant lié aux arêtes voisines commençons par une proposition qui va nous permettre de ne considérer par la suite que des graphes connexes :

Cet proposition toute simple montre que l'on peut parfois utiliser des colorations de sous-graphes pour trouver une solution sur le graphe tout entier.

Attention cependant, cela ne marche pas toujours. Il n'est par exemple pas possible de se restreindre (comme on en aurait envie) à une clique de taille maximum de $G$ (puisque $\omega(G) \leq \chi(G)$ pour tout graphe $G$) puis d'étendre sa coloration à tout le graphe. Cela ne marche pas : graphe de Mycielski est sans triangle (donc avec $\omega(G) = 2$) dont le nombre chromatique peut être aussi grand qu'on veut !

La figure c-après montre les graphes $M_2$, $M_3$ et $M_4$ :

Cette famille de graphe es sans triangle :

On a donc $\omega(M_k) = 2$ pour tout $k$ mais :

Coller plusieurs graphes ensemble pour en former un plus gros peut se faire de multiples façons. Nous allons en montrer trois, classiques, mais il doit en exister bien d'autres.

$G_1 + G_2$

Commençons par la plus simple, qui ne rajoute aucune arête entre les deux graphes que l'on compose :

À vous pour le coloriage :

$G_1 \vee G_2$

On peut aussi utiliser l'approche opposée, qui consiste à ajouter toutes les arêtes possibles entre les deux graphes :

À vous pour le coloriage :

$G_1 \square G_2$

Enfin, de façon plus subtile :

À vous pour le coloriage :

Cette décomposition se révèle puissante pour la coloration en décomposant un graphe donné en "patterns". Commençons par un petit échauffement :

Pour aborder une composition un peu plus dure :

Pour finir, la composition $\times$ des graphes (le produit tensoriel) a fait l'objet d'une grosse conjecture qui est maintenant prouvée fausse :

Applications

Résoudre des sudoku

Faire des plans de table

TBD ou résoudre des problèmes d'emploi du temps. p45 https://mathweb.ucsd.edu/~gptesler/154/slides/154_graphcoloring_20-handout.pdf

Optimiser la compilation de programmes

p4 http://o.togni.u-bourgogne.fr/CMGraphesCh3.pdf et p49 https://mathweb.ucsd.edu/~gptesler/154/slides/154_graphcoloring_20-handout.pdf

Attention

TBD à ne pas tout modéliser par des couleurs. à 5min45 https://www.youtube.com/watch?v=y4RAYQjKb5Y

On le verra le problème général de la coloration est NP-complet donc ne modélisez pas par un problème NP-complet un problème simple. Les taxis, on l'a vu se résolvent facilement par un algorithme glouton ! Ca arrive plus souvent qu'pon ne le pense, doc faite attention lorsque vous modélisez votre problème : essayez d'être le plus précis possible.