2024 INP Option info MP — Corrigé

Partie I – Coloration de graphes

L’objectif de cette partie est de proposer une implémentation en Python d’une solution au problème de coloration d’un graphe.

I.1 – Définitions et propriétés

Soit {G=(S,A)} un graphe fini non orienté avec S son ensemble de sommets et A son ensemble d’arêtes. On suppose que le graphe est simple c’est-à-dire qu’il ne comporte pas de boucles et que chaque paire de sommets est reliée par au plus une arête. On note n, le cardinal de l’ensemble S .

Les sommets sont numérotés de 0 à {n-1}. Étant donné un entier naturel k, une k-coloration des sommets de G est une application {c:S\to\{0,1,\ldots,k-1\}} telle que pour chaque arête {x,y} d’extrémités x et y, {c(x)\ne c(y)}. Si {c(x)=i}, on considèrera que la couleur i est affectée au sommet x.

Si G admet une k-coloration, il est k-coloriable. On définit le nombre chromatique {\chi(G)} d’un graphe G fini par {\chi(G)=\min\{k\in\mathbb N,\ G\text{ est }k\text{-coloriable}\}}. Une clique est un sous-ensemble de sommets du graphe, adjacents 2 à 2. On dit qu’un graphe est complet si il est une clique. On notera {K_p} le graphe complet à p sommets.

On pose {\omega(G)=\max\{p\in\mathbb N\mid K_p\text{ est une clique de }G\}} , avec N l’ensemble des entiers naturels.

Figure 1

Q 1. Le graphe {G_1} de la figure 1 ci-dessus est-il 2-coloriable ? Justifier votre réponse.
Q 2. Pour un entier naturel {n\ge1}, déterminer le nombre chromatique du graphe {K_n}.
Q 3. Montrer que pour tout graphe G à n sommets, on a {\omega(G)\le\chi(G)\le n}.

Pour voir la suite de ce contenu, vous devez : Pour poursuivre votre exploration, vous pouvez :