Monsieur A donne rendez-vous à ses amis: B, C , D et E.
Pour cela il a peint les routes en rouge et bleu comme indiqué, et
a dit à chacun: "Prends la route Bleu, puis de nouveau la Bleu,
la Rouge, encore la Rouge, la Bleu puis finalement la Rouge et
tu seras arrivé."On peut vérifier que chacun, suivant l'instruction donnée par Monsieur A arrive bien à bon port.
Plus formellement, étant donné un graphe orienté D de degré sortant constant 2, une bonne coloration des arcs de D est une coloration de ses arcs en 2 couleurs : rouge (noté R) et bleu (noté B) telle que chaque sommet soit début d'un arc rouge et d'un arc bleu. On considère des mots sur les deux lettres R et B. Appliquer un mot w sur un sommet x du digraphe revient à se placer sur x et à suivre lettre après lettre les arcs dont la couleur correspond à la lettre courrante. Le sommet d'arrivée est appelé image de x par w. Dans l'exemple précédent, on a appliqué le mot BBRRBR à chacun des sommets. Appliquer un mot w à un ensemble de sommets X revient à appliquer w à chacun des sommets de X. L'ensemble des images de ces sommets est appelé image de X par w. Enfin, un mot w est dit contractant, si l'image de V, ensemble de tous les sommets du graphe, par w est constitué d'un seul sommet (ce qui est le cas sur l'exemple précédent).
La Conjecture du Problème de "Road Coloring" affirme que, à une famille d'exception près, quelsoit le digraphe D choisi au départ avec degré sortant constant, D admet toujours une bonne coloration de ses arcs qui possède un mot contractant.
Cette Conjecture est ouverte depuis 1970. Elle est résolue dans le cas où D possède un circuit de longueur un entier premier (O'Brien, 1981) et aussi dans le cas où D est eulérien (Kari 2001).
Le but de ce TER est, d'une part, d'implémenter (de préférence en C/C++) les deux cas de résolution connus ainsi que le calcul d'invariants de graphes autour de cette question. D'autre part, il est attendu de faire un état de l'art concernant le problème du Road Coloring.