Problème — Colorier un graphe pour planifier des examens

Problème — Colorier un graphe pour planifier des examens.

Des examens doivent être placés sur des demi-journées ; deux examens passés par un même élève ne peuvent pas avoir lieu sur la même demi-journée. On représente les examens par les sommets d'un graphe non orienté, deux examens incompatibles étant reliés par une arête. Attribuer une demi-journée à chaque examen revient à colorier les sommets de sorte que deux sommets voisins n'aient jamais la même couleur ; on veut utiliser peu de couleurs.

• Écrire une fonction coloration_gloutonne(G, ordre) qui traite les sommets dans l'ordre de la liste ordre et donne à chacun la plus petite couleur (un entier $0,1,2,\dots$) non utilisée par ses voisins déjà coloriés.
• On considère le graphe ci-dessous, dans lequel chaque a${}_i$ est relié à chaque b${}_j$ pour $i\ne j$. Appliquer la fonction avec l'ordre a1, b1, a2, b2, a3, b3, puis avec l'ordre a1, a2, a3, b1, b2, b3.

G = {"a1": ["b2", "b3"], "a2": ["b1", "b3"], "a3": ["b1", "b2"],
     "b1": ["a2", "a3"], "b2": ["a1", "a3"], "b3": ["a1", "a2"]}

• Quel est le nombre minimal de couleurs pour ce graphe ? Que montre cet exemple ?