Colorez un graphe

Le service de scolarité doit placer les examens de fin de semestre. Deux matières qui ont des étudiants en commun ne peuvent pas avoir leur examen sur le même créneau. Combien de créneaux faut-il, au minimum ? Et comment répartir les examens ?

Ce problème, et beaucoup d’autres (fréquences radio, registres d’un processeur, Sudoku), est un problème de coloration de graphe. Il est simple à énoncer, redoutablement difficile à résoudre exactement, mais de bonnes heuristiques existent. C’est l’objet de ce chapitre.

Le fil rouge : un planning d’examens

Sept matières sont concernées : Graphes (G), Probabilités (P), Statistiques (S), Prolog (L), Apprentissage (A), Anglais (N) et Réseaux (R). On construit le graphe des incompatibilités : un sommet par matière, une arête entre deux matières qui ont au moins un étudiant en commun.

Les incompatibilités sont : G-P, G-S, G-L, P-S, P-A, S-A, L-A, L-R, A-N, N-R et S-N. Les couleurs du schéma montrent une solution à trois créneaux, que nous allons retrouver.

Stables, cliques et absorbants

Avant de colorier, trois notions structurent le raisonnement.

• Un stable (ou ensemble indépendant) est un ensemble de sommets deux à deux non adjacents. Dans notre graphe, $\lbrace A, G, R \rbrace$ est un stable : trois examens qui peuvent partager un créneau. Le nombre de stabilité $\alpha(G)$ est la taille du plus grand stable ; ici, $\alpha = 3$.
• Une clique est un ensemble de sommets deux à deux adjacents. $\lbrace G, P, S \rbrace$ est une clique : ces trois examens doivent être sur des créneaux tous différents. Le nombre de clique $\omega(G)$ est la taille de la plus grande clique ; ici, $\omega = 3$ (il y a trois triangles, $\lbrace G, P, S \rbrace$, $\lbrace A, P, S \rbrace$ et $\lbrace A, N, S \rbrace$, mais aucun groupe de quatre).
• Dans un graphe orienté, un ensemble $B$ est absorbant si tout sommet hors de $B$ a au moins un successeur dans $B$. Le nombre d’absorption $\beta(G)$ est la taille du plus petit absorbant. Exemple typique : placer le moins de casernes de pompiers possible pour que chaque quartier soit voisin d’une caserne.

Un stable peut partager un créneau ; une clique demande autant de créneaux que de sommets.

Stable et clique sont deux faces d’une même notion : un stable de $G$ est une clique du graphe complémentaire (celui qui relie exactement les paires non reliées dans $G$).

Colorier un graphe

Coloration et nombre chromatique

Une coloration des sommets attribue une couleur à chaque sommet de sorte que deux sommets adjacents aient des couleurs différentes. Chaque couleur définit donc un stable : colorier avec $k$ couleurs, c’est partitionner les sommets en $k$ stables. Le nombre chromatique $\chi(G)$ (lisez « khi ») est le plus petit nombre de couleurs possible.

Pour le planning, une couleur est un créneau, et $\chi(G)$ est le nombre minimal de créneaux.

Encadrer le nombre chromatique

Calculer $\chi(G)$ exactement est un problème NP-difficile : on ne connaît pas d’algorithme efficace pour les grands graphes. En revanche, on sait l’encadrer.

À retenir

$$\max\left(\omega(G),\; \left\lceil \frac{n}{\alpha(G)} \right\rceil\right) \;\leq\; \chi(G) \;\leq\; \Delta(G) + 1$$

• Minorant par la clique : les sommets d’une clique sont deux à deux adjacents, il leur faut des couleurs toutes différentes.
• Minorant par les stables : chaque couleur est un stable, qui contient au plus $\alpha$ sommets ; il faut donc au moins $n / \alpha$ couleurs.
• Majorant : $\Delta(G)$ est le degré maximal. En coloriant les sommets un par un, chaque sommet a au plus $\Delta$ voisins déjà coloriés, donc une couleur parmi $\Delta + 1$ reste toujours libre.

Exemple

Pour les examens : $\omega = 3$, $n / \alpha = 7 / 3 \approx 2{,}33$, donc au moins 3 couleurs. Le degré maximal vaut $\Delta = 4$ (A et S), donc au plus 5. On sait déjà que $3 \leq \chi \leq 5$. Il suffit d’exhiber une coloration à 3 couleurs pour conclure que $\chi = 3$.

Les deux minorants et le majorant enferment χ entre 3 et 5 ; une coloration à 3 couleurs suffit alors à conclure.

Deux résultats célèbres complètent le tableau. Le théorème des quatre couleurs (démontré en 1976, avec l’aide d’un ordinateur) affirme que tout graphe planaire (qu’on peut dessiner sans croisement d’arêtes, comme une carte de pays voisins) est coloriable avec 4 couleurs. Et pour la coloration des arêtes (deux arêtes qui partagent un sommet doivent avoir des couleurs différentes), le théorème de Vizing dit que l’indice chromatique $q(G)$ vaut $\Delta$ ou $\Delta + 1$. Exemple d’usage : organiser un tournoi où chaque équipe joue au plus un match par journée ; les journées sont les couleurs des arêtes.

Des heuristiques gloutonnes

Le glouton simple, et ses limites

L’algorithme glouton parcourt les sommets dans un ordre donné et attribue à chacun la plus petite couleur non utilisée par ses voisins déjà coloriés. Il utilise toujours au plus $\Delta + 1$ couleurs, mais son résultat dépend énormément de l’ordre choisi : il existe des graphes à 2 couleurs où un mauvais ordre en fait utiliser $n / 2$ (vous en verrez un en exercice). Toute l’astuce est donc de bien choisir l’ordre.

Welsh-Powell : les plus contraints d’abord

L’heuristique de Welsh-Powell trie les sommets par degré décroissant, puis construit les couleurs une par une : on parcourt la liste et on donne la couleur 1 à chaque sommet non colorié qui n’a aucun voisin de couleur 1 ; puis on recommence avec la couleur 2, etc.

Exemple

Degrés : A 4, S 4, G 3, L 3, N 3, P 3, R 2. Ordre (égalités départagées par ordre alphabétique) : A, S, G, L, N, P, R.

• Couleur 1 : A ; S est voisin de A, on passe ; G n’est pas voisin de A, on le prend ; L, N, P sont voisins de A ; R n’est voisin ni de A ni de G, on le prend. Créneau 1 : $\lbrace A, G, R \rbrace$.
• Couleur 2 : S ; L n’est pas voisin de S, on le prend ; N et P sont voisins de S. Créneau 2 : $\lbrace S, L \rbrace$.
• Couleur 3 : N et P, qui ne sont pas voisins. Créneau 3 : $\lbrace N, P \rbrace$.

Trois couleurs : comme $\chi \geq 3$, c’est optimal.

Welsh-Powell parcourt la liste A, S, G, L, N, P, R et remplit une couleur à la fois : trois passes, donc trois créneaux.

DSatur : la saturation d’abord

L’heuristique DSatur (degré de saturation) choisit dynamiquement le prochain sommet : celui dont les voisins utilisent déjà le plus de couleurs différentes (le plus « coincé »), en départageant par le degré. Sur notre exemple, elle colorie A, puis S (voisin de A, saturation 1), puis N (voisin de A et S, saturation 2), et aboutit aussi à 3 couleurs. DSatur est exacte sur certaines familles de graphes (les graphes bipartis, par exemple) et donne en général de meilleurs résultats que Welsh-Powell.

DSatur choisit à chaque fois le sommet le plus contraint : A, puis S, puis N ; il aboutit lui aussi à trois couleurs.

def welsh_powell(voisins):
    """voisins : dictionnaire sommet -> ensemble de voisins. Renvoie sommet -> couleur."""
    ordre = sorted(voisins, key=lambda x: (-len(voisins[x]), x))    # degré décroissant
    couleur, c = {}, 0
    while len(couleur) < len(voisins):
        for x in ordre:
            if x not in couleur and all(couleur.get(y) != c for y in voisins[x]):
                couleur[x] = c
        c += 1                                                       # couleur suivante
    return couleur

aretes = ["GP", "GS", "GL", "PS", "PA", "SA", "LA", "LR", "AN", "NR", "SN"]
voisins = {x: set() for x in "GPSLANR"}
for u, v in aretes:
    voisins[u].add(v)
    voisins[v].add(u)
print(welsh_powell(voisins))   # A, G, R -> 0 ; S, L -> 1 ; N, P -> 2

networkx propose les mêmes heuristiques (sa fonction ne renvoie qu’une coloration, pas une preuve d’optimalité) :

import networkx as nx

G = nx.Graph([tuple(a) for a in aretes])
print(nx.greedy_color(G, strategy="largest_first"))        # esprit Welsh-Powell
print(nx.greedy_color(G, strategy="saturation_largest_first"))   # DSatur

Piège

Une heuristique qui trouve $k$ couleurs prouve seulement que $\chi \leq k$. Pour affirmer que $k$ est optimal, il faut un minorant : une clique de taille $k$, ou l’argument $n / \alpha$. Sans minorant, « Welsh-Powell donne 4 couleurs » ne dit pas si 3 suffiraient.

Où rencontre-t-on la coloration ?

• Attribution de fréquences : des émetteurs radio trop proches (par exemple à moins de 100 km) interfèrent s’ils utilisent la même fréquence. On relie les émetteurs trop proches, et le nombre minimal de fréquences est le nombre chromatique. C’était le thème d’un exercice de devoir surveillé.
• Allocation de registres : un compilateur doit ranger les variables d’un programme dans un petit nombre de registres du processeur. Deux variables « vivantes » en même temps ne peuvent pas partager un registre : on colorie le graphe d’interférence.
• Emplois du temps, Sudoku (un Sudoku est une coloration à 9 couleurs d’un graphe de 81 sommets, partiellement pré-coloriée), affectation de quais dans une gare.

En entretien

« Je modéliserais les conflits par un graphe et je chercherais une coloration : le nombre de couleurs est le nombre de créneaux. Le problème exact est NP-difficile, donc j’utiliserais une heuristique gloutonne comme DSatur, et je vérifierais la qualité avec un minorant, la taille d’une clique. »

En résumé

• Un stable est un ensemble de sommets non adjacents ($\alpha$ = taille max), une clique un ensemble de sommets deux à deux adjacents ($\omega$ = taille max).
• Une coloration donne des couleurs différentes aux sommets adjacents ; chaque couleur est un stable. Le nombre chromatique $\chi$ est le minimum de couleurs.
• On encadre : $\max(\omega, \lceil n / \alpha \rceil) \leq \chi \leq \Delta + 1$. Le calcul exact est NP-difficile.
• Les heuristiques gloutonnes dépendent de l’ordre : Welsh-Powell (degré décroissant) et DSatur (saturation décroissante) donnent de bons résultats.
• Un graphe planaire se colorie avec 4 couleurs ; l’indice chromatique (coloration des arêtes) vaut $\Delta$ ou $\Delta + 1$.

Exercices

Exercice · Des fréquences pour cinq émetteurs

facile

Cinq émetteurs radio V, W, X, Y, Z interfèrent deux à deux dans les cas suivants : V-W, V-X, W-X, X-Y, Y-Z. Combien de fréquences faut-il au minimum ? Proposez une attribution.

Voir la solution

V, W et X sont deux à deux en conflit : c’est une clique de taille 3, donc il faut au moins 3 fréquences. Trois suffisent : V → f1, W → f2, X → f3, Y → f1 (Y n’est en conflit qu’avec X et Z), Z → f2 (en conflit seulement avec Y). On vérifie chaque conflit : V-W (f1, f2), V-X (f1, f3), W-X (f2, f3), X-Y (f3, f1), Y-Z (f1, f2). Donc $\chi = 3$.

En code

Python

from itertools import product

emetteurs = ["V", "W", "X", "Y", "Z"]
conflits = [("V", "W"), ("V", "X"), ("W", "X"), ("X", "Y"), ("Y", "Z")]

def premiere_coloration(k):
    """Essaie toutes les attributions de k fréquences et renvoie la première valide."""
    for couleurs in product(range(1, k + 1), repeat=len(emetteurs)):
        f = dict(zip(emetteurs, couleurs))
        if all(f[u] != f[v] for u, v in conflits):
            return f
    return None

k = 1
while premiere_coloration(k) is None:      # plus petit k qui marche : le nombre chromatique
    k += 1
print(k, premiere_coloration(k))   # 3 {'V': 1, 'W': 2, 'X': 3, 'Y': 1, 'Z': 2}

R

emetteurs <- c("V", "W", "X", "Y", "Z")
conflits <- rbind(c("V", "W"), c("V", "X"), c("W", "X"), c("X", "Y"), c("Y", "Z"))

colorations_valides <- function(k) {
  # toutes les attributions de k fréquences, une par ligne
  f <- as.matrix(expand.grid(rep(list(1:k), length(emetteurs))))
  colnames(f) <- emetteurs
  ok <- apply(f, 1, function(ligne) all(ligne[conflits[, 1]] != ligne[conflits[, 2]]))
  f[ok, , drop = FALSE]
}

k <- 1
while (nrow(colorations_valides(k)) == 0) k <- k + 1   # nombre chromatique
k                                   # 3
colorations_valides(3)[1, ]         # V 3, W 2, X 1, Y 2, Z 1 (une solution parmi d'autres)

Exercice · Le glouton piégé par l'ordre

moyen

On considère le graphe à six sommets $a_1, a_2, a_3, b_1, b_2, b_3$ où $a_i$ est relié à $b_j$ si et seulement si $i \neq j$.

1. Quel est son nombre chromatique ?
2. Appliquez le glouton simple dans l’ordre $a_1, b_1, a_2, b_2, a_3, b_3$. Combien de couleurs obtenez-vous ?
3. Que donne Welsh-Powell ici ? Que faut-il en conclure ?

Voir la solution

1. Aucune arête ne relie deux $a$ ni deux $b$ : le graphe est biparti, et 2 couleurs suffisent (tous les $a$ en couleur 1, tous les $b$ en couleur 2). Comme il a des arêtes, $\chi = 2$.
2. $a_1$ reçoit 1. $b_1$ n’est pas voisin de $a_1$ : il reçoit 1. $a_2$ est voisin de $b_1$ (couleur 1) : il reçoit 2. $b_2$ est voisin de $a_1$ (1) mais pas de $a_2$ : il reçoit 2. $a_3$ est voisin de $b_1$ (1) et $b_2$ (2) : il reçoit 3. $b_3$ est voisin de $a_1$ (1) et $a_2$ (2) : il reçoit 3. Résultat : 3 couleurs au lieu de 2. Avec $k$ paires construites de la même façon, ce glouton utiliserait $k$ couleurs pour un graphe 2-coloriable.
3. Tous les sommets ont le même degré (2), donc le tri par degré ne départage rien : selon l’ordre des égalités, Welsh-Powell peut tomber dans le même piège. Conclusion : une heuristique gloutonne n’offre aucune garantie d’optimalité. DSatur, lui, colorie correctement tout graphe biparti.

En code

Python

voisins = {f"a{i}": {f"b{j}" for j in (1, 2, 3) if j != i} for i in (1, 2, 3)}
for i in (1, 2, 3):
    voisins[f"b{i}"] = {f"a{j}" for j in (1, 2, 3) if j != i}

def glouton(voisins, ordre):
    """Chaque sommet reçoit la plus petite couleur absente chez ses voisins déjà coloriés."""
    couleur = {}
    for x in ordre:
        prises = {couleur[y] for y in voisins[x] if y in couleur}
        couleur[x] = min(c for c in range(1, len(ordre) + 1) if c not in prises)
    return couleur

mauvais = glouton(voisins, ["a1", "b1", "a2", "b2", "a3", "b3"])
bon = glouton(voisins, ["a1", "a2", "a3", "b1", "b2", "b3"])
print(mauvais, max(mauvais.values()))   # a1, b1 -> 1 ; a2, b2 -> 2 ; a3, b3 -> 3 : 3 couleurs
print(max(bon.values()))                # 2 : le même glouton, dans un autre ordre, est optimal

R

sommets <- c("a1", "a2", "a3", "b1", "b2", "b3")
adj <- matrix(FALSE, 6, 6, dimnames = list(sommets, sommets))
for (i in 1:3) for (j in 1:3) if (i != j) adj[paste0("a", i), paste0("b", j)] <-
  adj[paste0("b", j), paste0("a", i)] <- TRUE

glouton <- function(adj, ordre) {
  # chaque sommet reçoit la plus petite couleur absente chez ses voisins déjà coloriés
  couleur <- setNames(rep(NA, length(ordre)), ordre)
  for (x in ordre) {
    prises <- couleur[adj[x, ordre]]
    couleur[x] <- min(setdiff(seq_along(ordre), prises))
  }
  couleur
}

glouton(adj, c("a1", "b1", "a2", "b2", "a3", "b3"))   # 1 1 2 2 3 3 : 3 couleurs
max(glouton(adj, c("a1", "a2", "a3", "b1", "b2", "b3")))   # 2 : optimal dans cet ordre

Exercice · Prouver le majorant

difficile

Démontrez que tout graphe de degré maximal $\Delta$ vérifie $\chi(G) \leq \Delta + 1$. Donnez un graphe pour lequel cette borne est atteinte, et un autre pour lequel elle est très mauvaise.

Voir la solution

On colorie les sommets un par un, dans n’importe quel ordre, en donnant à chacun la plus petite couleur parmi $\lbrace 1, \dots, \Delta + 1 \rbrace$ que n’utilise aucun de ses voisins déjà coloriés. Un sommet a au plus $\Delta$ voisins, donc au plus $\Delta$ couleurs sont interdites : il en reste toujours au moins une de libre. La coloration obtenue est valide et utilise au plus $\Delta + 1$ couleurs.

La borne est atteinte pour le graphe complet $K_n$ ($\Delta = n - 1$, $\chi = n$) et pour un cycle de longueur impaire ($\Delta = 2$, $\chi = 3$). Elle est très mauvaise pour une étoile à $n$ branches : un centre relié à $n$ feuilles, soit $\Delta = n$, alors que $\chi = 2$ (le centre d’une couleur, toutes les feuilles de l’autre). Le théorème de Brooks affine d’ailleurs la borne : pour un graphe connexe qui n’est ni complet ni un cycle impair, $\chi \leq \Delta$.

En code

Python

from itertools import product

def chi(n, aretes):
    """Nombre chromatique par force brute (petits graphes seulement)."""
    k = 1
    while not any(all(c[u] != c[v] for u, v in aretes) for c in product(range(k), repeat=n)):
        k += 1
    return k

def delta(n, aretes):
    return max(sum(x in a for a in aretes) for x in range(n))   # degré maximal

exemples = {
    "K5": (5, [(u, v) for u in range(5) for v in range(u + 1, 5)]),
    "cycle C5": (5, [(i, (i + 1) % 5) for i in range(5)]),
    "étoile à 6 branches": (7, [(0, i) for i in range(1, 7)]),
}
for nom, (n, aretes) in exemples.items():
    print(nom, "Delta + 1 =", delta(n, aretes) + 1, " chi =", chi(n, aretes))
# K5 Delta + 1 = 5  chi = 5
# cycle C5 Delta + 1 = 3  chi = 3
# étoile à 6 branches Delta + 1 = 7  chi = 2

R

chi <- function(n, aretes) {
  # nombre chromatique par force brute (petits graphes seulement)
  k <- 1
  repeat {
    colorations <- as.matrix(expand.grid(rep(list(1:k), n)))
    if (any(apply(colorations, 1, function(c) all(c[aretes[, 1]] != c[aretes[, 2]])))) return(k)
    k <- k + 1
  }
}
delta <- function(aretes) max(table(aretes))           # degré maximal

K5 <- t(combn(5, 2))
C5 <- cbind(1:5, c(2:5, 1))
etoile <- cbind(1, 2:7)                                # centre 1, six feuilles
for (g in list(K5, C5, etoile)) cat("Delta + 1 =", delta(g) + 1, " chi =", chi(max(g), g), "\n")
# K5 : 5 et 5 ; C5 : 3 et 3 ; étoile à 6 branches : 7 et 2