Corrigé Centrale 2026 Option informatique MP — Partie B, II (Q28 à Q30) : 3-coloration par retour sur trace

Sujet officiel du concours Centrale, session 2026, épreuve Option informatique MP. Corrigé rédigé par Ibrahim Alame.

Énoncé

On ne sait pas résoudre 3-COLORATION en temps polynomial dans le cas général ; on procède par retour sur trace. Une coloration (type col = int array) est initialisée à $- 1$ pour chaque sommet ; $- 1$ signifie « pas encore de couleur » et est compatible localement avec toutes les couleurs. Le type graphe est celui de la partie I.

Q28. Écrire partial : graphe -> col -> int -> bool, qui décide si la coloration est localement valide entre le sommet donné (supposé coloré) et ses voisins.
Q29. Écrire backtracking : graphe -> bool * col, qui décide si un graphe (supposé connexe) admet une 3-coloration valide et en renvoie une le cas échéant.
Q30. Complexité temporelle dans le pire cas de cette stratégie.

Corrigé

Q28. Le sommet $s$ étant coloré, $c (s) \neq = - 1$ : un voisin non coloré ( $c (v) = - 1$ ) est donc automatiquement différent, et il suffit de tester $c (v) \neq = c (s)$ pour tout voisin $v$ .


let partial (g : graphe) (c : col) (s : int) : bool =
  let rec verifie l =
    match l with
    | [] -> true
    | v :: r -> c.(v) <> c.(s) && verifie r
  in
  verifie g.adj.(s)

La fonction renvoie true ssi aucun voisin de $s$ n'a la couleur de $s$ ; l'opérateur && étant paresseux, on s'arrête au premier conflit. Coût : $O (1 + de g (s))$ .

100 % gratuit

La suite du corrigé est sur Adloun

Le corrigé rédigé en entier, question par question, et le tuteur pour poser des questions sur ce sujet.

Voir le corrigé complet, gratuitement

Inscription gratuite en 30 secondes (e-mail, nom d'utilisateur, mot de passe, classe ou profil), sans carte bancaire : arrivée directe sur le corrigé.

Toutes les parties de l'épreuve

Corrigé complet gratuit →