Corrigé Centrale 2026 Option informatique MP — Partie B, I.1-I.2 (Q9 à Q15) : Graphes bipartis et bicoloration exhaustive

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

Énoncé

Un graphe non orienté $G = (S, A)$ est sans boucle ; $de g (s)$ est le nombre d'arêtes contenant $s$ ; un cycle est un chemin de longueur au moins $3$ d'un sommet à lui-même, à sommets distincts (hors extrémités). Une coloration $c : S \to N$ est valide si $c (u) \neq = c (v)$ pour toute arête ${u, v}$ ; une $k$ -coloration prend ses valeurs dans $[[0, k - 1]]$ ; $G$ est $k$ -colorable s'il admet une $k$ -coloration valide. Types donnés par le sujet, et le graphe $G_{1}$ de la figure 2 :


type graphe = {nbr : int ; adj : int list array}
type col = int array
let g1 = {nbr = 6 ; adj = [|[3; 2; 4]; [2; 3]; [3; 0; 1; 5];
                            [0; 4; 2; 1]; [0; 3]; [2]|]};;

$G_{2}$ est 2-colorable, $G_{1}$ ne l'est pas. Une bicoloration est lue comme l'écriture binaire d'un entier, le sommet $0$ donnant le bit de poids faible : la coloration de la figure 3 est [|1; 1; 0; 1; 0; 0|], associée à $1 + 2 + 8 = 11$ .

Q9. Montrer qu'un graphe est 2-colorable si et seulement s'il est biparti.
Q10. Montrer qu'un graphe ayant un cycle impair n'est pas 2-colorable.
Q11. Montrer qu'un graphe sans cycle impair est 2-colorable (récurrence sur le nombre d'arêtes).
Q12. Écrire suivante : col -> bool, qui passe à la bicoloration de l'entier suivant (en place) et dit si elle existe ; temps constant dans le meilleur cas.
Q13. Écrire valide : graphe -> col -> bool.
Q14. En déduire bicolnaif : graphe -> bool * col par recherche exhaustive.
Q15. Complexité dans le pire cas de bicolnaif.

Corrigé

Dans toute la suite, $n = ∣ S ∣$ et $m = ∣ A ∣$ ; pour un graphe g, $n$ vaut g.nbr et la somme des longueurs des listes g.adj.(i) vaut $2 m$ (chaque arête ${u, v}$ figure dans la liste de $u$ et dans celle de $v$ ).

Q9. Un graphe $G = (S, A)$ est biparti s'il existe une partition $S = S_{0} ⊔ S_{1}$ telle que toute arête ait une extrémité dans $S_{0}$ et l'autre dans $S_{1}$ (aucune arête à l'intérieur de $S_{0}$ ni de $S_{1}$ ).

Si $c$ est une 2-coloration valide, posons $S_{i} = c^{- 1} ({i})$ pour $i \in {0, 1}$ : c'est une partition de $S$ , et pour toute arête ${u, v}$ , $c (u) \neq = c (v)$ avec $c (u), c (v) \in {0, 1}$ , donc l'une des extrémités est dans $S_{0}$ et l'autre dans $S_{1}$ . $G$ est biparti.
Réciproquement, si $S = S_{0} ⊔ S_{1}$ est une bipartition, la coloration $c (s) = i$ pour $s \in S_{i}$ est une 2-coloration, valide puisque les extrémités d'une arête sont dans des parties différentes.

Q10. Soit $s_{0}, s_{1}, \dots, s_{ℓ} = s_{0}$ un cycle de longueur $ℓ$ impaire et supposons qu'une 2-coloration valide $c$ existe. Montrons par récurrence sur $i \in [[0, ℓ]]$ que $c (s_{i}) \equiv c (s_{0}) + i (mod 2)$ . C'est vrai pour $i = 0$ ; si c'est vrai pour $i < ℓ$ , comme ${s_{i}, s_{i + 1}} \in A$ on a $c (s_{i + 1}) \neq = c (s_{i})$ , et les deux valeurs sont dans ${0, 1}$ , donc $c (s_{i + 1}) = 1 - c (s_{i}) \equiv c (s_{i}) + 1 \equiv c (s_{0}) + i + 1 (mod 2)$ . Pour $i = ℓ$ impair, $c (s_{ℓ}) \neq = c (s_{0})$ , alors que $s_{ℓ} = s_{0}$ : contradiction. Un graphe ayant un cycle impair n'est pas 2-colorable (c'est le cas de $G_{1}$ , qui contient le triangle $0 - 2 - 3$ ).

Q11. Montrons par récurrence sur $m \in N$ la propriété $P (m)$ : « tout graphe à $m$ arêtes sans cycle impair est 2-colorable ».

Initialisation. Si $m = 0$ , la coloration constante égale à $0$ est valide (il n'y a aucune arête à vérifier).

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 →