ENS Informatique Fondamentale (Maths Info) MP MPI 2026Sujet

Reconfiguration dans les graphes

Le sujet comporte 12 pages, numérotées de 1 à 12.

Début de l'épreuve.

• -La partie I fournit des conditions suffisantes sur l'existence de transformations entre deux colorations.
• -La partie II étudie le graphe des colorations d'un graphe G donné, un objet qui capture les transformations possibles entre colorations, et vise à montrer que cet objet capture toutes les informations sur G.
• -La partie III étudie les transformations entre colorations d'un point de vue probabiliste, dans le but de générer aléatoirement uniformément des colorations d'un graphe fixé.
• -La partie IV vise à construire un algorithme efficace pour tester l'existence de transformations entre deux ensembles dominants donnés, dans une classe restreinte de graphes.
• -La partie V considère la variante où on colore les arêtes d'un graphe au lieu de ses sommets, et utilise des transformations pour obtenir une borne sur le nombre total de couleurs nécessaires pour colorer des graphes dans ce cadre.

Notations et définitions

• -Un graphe G est défini comme une paire (V(G), E(G)) où V(G) est un ensemble fini de sommets et E(G) est un ensemble de parties de taille 2 de V(G) appelées arêtes. Quand aucune ambiguité n'est possible, on s'autorise à écrire respectivement V et E à la place de V(G) et E(G), et n et m à la place de |V(G)| et |E(G)|.
• -Lorsque {x, y} ∈ E, on dit que x et y sont adjacents, et on notera xy l'arête {x, y}. L'arête xy est incidente à x et y.
• -Le voisinage N(v) d'un sommet v est l'ensemble {w ∈ V|{v, w} ∈ E}. Le degré deg(v) de v est |N(v)|. Le degré maximum Δ(G) de G est max_(v ∈ V(G))deg(v).
• -On supposera que les graphes sont représentés sous forme de liste d'adjacence, c'est-àdire comme un tableau associant à chaque sommet la liste de ses voisins.
• -
  Un sous-graphe H de G est un graphe vérifiant V(H) ⊆ V(G) et E(H) ⊆ E(G). Il est de plus induit si E(H) contient exactement les arêtes de E(G) entre deux sommets de V(H). On note alors H = G[V(H)].
  

  (a) Un graphe G
  

  (b) Un sous-graphe induit de G
  

  (c) Un sous-graphe de G non-induit
• -Si X est un ensemble de sommets de G, G − X est le graphe induit par V(G)∖X. Si X = {v}, on notera G − v au lieu de G − {v}.
• -Une composante connexe d'un graphe G est un sous-graphe induit par n'importe quel ensemble non vide X de sommets minimal par inclusion vérifiant N(x) ⊆ X pour tout x ∈ X.
• -Un cycle de longueur k est un graphe à k sommets u_1, …, u_k et contenant les k arêtes u_1 u_2, …, u_(k − 1)u_k, u_k u_1.
• -Un chemin de longueur k est un graphe à k + 1 sommets u_1, …, u_(k + 1) et contenant les k arêtes u_1 u_2, …, u_k u_(k + 1).
• -Un sous-ensemble X de sommets de G est une clique si les sommets de X sont deux à deux reliés par une arête. Autrement dit, pour toute paire x, y ∈ X avec x ≠ y, on a {x, y} ∈ E.
• -Un sous-ensemble X de sommets de G est un ensemble indépendant si aucune arête ne relie deux sommets de X. Autrement dit, pour toute paire x, y ∈ X avec x ≠ y, {x, y} ∉ E.

• -Une k-coloration de G est une fonction γ de V dans {1, …, k} telle que, pour toute paire de sommets x, y telle que {x, y} ∈ E, on a γ(x) ≠ γ(y). Le plus petit entier k tel qu'il existe une k-coloration de G est appelé le nombre chromatique de G et est noté χ(G). Un graphe est k-colorable s'il en existe une k-coloration.
• -Un graphe G est biparti si χ(G) ⩽ 2. En particulier, un graphe biparti ne peut pas contenir de cycle impair comme sous-graphe.
• -Deux graphes (V, E) et (V^′, E^′) sont isomorphes s'il existe une bijection f : V → V^′ telle que pour tout u, v ∈ V, uv ∈ E si et seulement si f(u)f(v) ∈ E^′.

Partie I

Question I.1. Montrer que le graphe suivant est 2-dégénéré.

Question I.2. Quelle est la dégénérescence du graphe suivant?

Partie II

Partie III

Entrée: Une 
k-coloration 
γ de 
G
Sortie: Une 
k-coloration de 
G
    Sélectionner au hasard un sommet 
v ∈ V(G) uniformément.
    Sélectionner au hasard une couleur 
r ∈ {1, …, k} uniformément et indépendamment de 
v.
    si 
v n'a pas de voisin 
w tel que 
γ(w) = r alors
        
γ(v):=r
    renvoyer 
γ

Partie IV

Entrée: Un graphe 
G sans 
K_(t, t), un sous-ensemble 
X de 
V(G)
    
Y:=X
    
S:=∅
    tant que 
G a un sommet 
v ∉ S tel que 
|(N(v) ∪ {v}) ∩ Y| ≥ ⌊|Y|/k⌋ faire
        
S:=S ∪ {v}
        
Y:=(N(v) ∪ {v}) ∩ Y

Partie V

• - γ^′^–(u) = γ¯(u), et
• - a ∈ γ^′^–(v), et
• - γ^′^–(w) = γ¯(w) pour tout w ∈ V∖{u, v} sauf au plus un, qui vérifie alors (γ^′^–(w)∖γ¯(w)) ∪ (γ¯(w)∖γ^′^–(w)) = {a, b}.