Problème — Colorier un graphe, et casser les symétries

1. Le compteur.

(* Nombre de colorations propres de adj avec au plus k couleurs.
   Précondition : adj est une matrice d'adjacence n x n symétrique, k >= 1.
   Complexité : O(k^n) au pire. *)
let colorier adj k =
  let n = Array.length adj in
  let coul = Array.make n (-1) in
  let total = ref 0 in
  let rec explorer s =
    if s = n then incr total
    else
      for c = 0 to k - 1 do
        let ok = ref true in
        for j = 0 to s - 1 do
          if adj.(s).(j) && coul.(j) = c then ok := false done;
        if !ok then begin
          coul.(s) <- c; explorer (s + 1); coul.(s) <- (-1)
        end
      done
  in explorer 0; !total

Terminaison : variant $n-s$. Correction : l'invariant est que $\mathtt{coul}(\mathrm{0..}s-1)$ est une coloration propre du sous-graphe induit par les $s$ premiers sommets ; le test le préserve, et à $s=n$ on a une coloration propre complète.

2. L'élagage par symétrie. Si $(c_0,\dots ,c_{n-1})$ est une coloration propre et $\sigma$ une permutation des couleurs, alors $(\sigma (c_0),\dots ,\sigma (c_{n-1}))$ en est une autre. Ces colorations sont la même à renommage près. On n'en garde qu'une : celle où les couleurs apparaissent dans l'ordre $0,1,2,\dots$ Concrètement, le sommet $s$ ne peut recevoir qu'une couleur déjà employée, ou la première couleur neuve :

(* plafond = 1 + (plus grande couleur déjà employée), borné par k *)
let plafond =
  let m = ref 0 in
  for j = 0 to s - 1 do if coul.(j) + 1 > !m then m := coul.(j) + 1 done;
  min k (!m + 1)
in
for c = 0 to plafond - 1 do (* ... *) done

Le premier sommet ne reçoit alors que la couleur $0$, le deuxième la couleur $0$ ou $1$, et ainsi de suite.

3. La mesure sur le graphe de Petersen :

Ce que le tableau dit. À $k=2$, aucune coloration : Petersen contient des cycles impairs, il n'est pas biparti. À $k=3$, il y en a : son nombre chromatique vaut donc $3$.

Le facteur d'élagage est $24=4!$ à $k=4$ et $6=3!$ à $k=3$ sur le nombre de solutions — ce qui se vérifie exactement : $12960=540\times 24$ et $120=20\times 6$. Sur le nombre de nœuds, le facteur est $24$ et $5,9$.

La leçon, et elle dépasse la coloration. Une symétrie du problème est une redondance de l'arbre de recherche : $k!$ branches y calculent la même chose sous des noms différents. La casser ne demande ni structure ni heuristique — seulement de normaliser l'ordre dans lequel les objets interchangeables apparaissent. C'est le même procédé qu'à l'exercice 14.6 sur les lettres répétées, et l'un des élagages les plus rentables qui soient : il est exact, il est gratuit, et son gain est un facteur factoriel.

Et si l'on ne veut que le nombre chromatique, on n'énumère pas : on essaie $k=1,2,3,\dots$ et l'on s'arrête au premier qui donne une solution, en abandonnant l'exploration dès la première trouvée. Le graphe de Petersen répond alors en $5$ puis $9$ nœuds.