Coloriage des routes

Le graphe avec son étiquetage est le graphe d'un automate fini déterministe complet sur l'alphabet ${\displaystyle A}$ des couleurs. Une suite de couleurs est un mot ${\displaystyle w\in A^{*}}$, et l'existence d'un mot synchronisant revient à l'existence d'un mot ${\displaystyle w\in A^{*}}$ tel que ${\displaystyle q\cdot w=s}$ pour un sommet ${\displaystyle s}$ et tout sommet ${\displaystyle q}$ de ${\displaystyle G}$. Il est commode d'utiliser la notation que voici : pour un ensemble ${\displaystyle P}$ de sommets et un mot ${\displaystyle w}$, on note ${\displaystyle P\cdot w=\{p\cdot w\mid p\in P\}}$ ; c'est l'ensemble des sommets atteints à partir d'un somme de ${\displaystyle P}$ par un chemin étiqueté par ${\displaystyle w}$. Un mot synchronisant est un mot ${\displaystyle w}$ tel que ${\displaystyle Q\cdot w}$ est un singleton. On appelle rang d'un mot ${\displaystyle w}$ le nombre d'éléments de ${\displaystyle Q\cdot w}$. Un mot synchronisant est donc un mot de rang 1. Un automate qui possède un mot synchronisant est dit lui-même synchronisant ou aussi synchronisé[3].

Automate de départ.

Le calcul des rangs s'illustre bien par un jeu à jetons[7]. Au départ, chaque état contient un jeton. À l'application d'une lettre R ou B, les jetons se déplacent d'un état au suivant selon la couleur. Après une séquence de lettres ${\displaystyle w}$, chaque état contient des jetons dont le nombre est le nombre d'états qui sont envoyés sur cet état par ${\displaystyle w}$. Le fait qu'à la fin tous les jetons se trouvent dans un même état exprime précisément que le mot employé est synchronisant.

Au départ, chaque état contient un jeton. La lettre B donne la deuxième distribution, la lettre R la troisième, enfin B la dernière : le mot BRB est synchronisant.

Dans un cas particulier, un argument simple donne une démonstration simple : c'est le cas où il y a une boucle autour d’un sommet dans le graphe. Soit ${\displaystyle r}$ un tel sommet. Comme le graphe est fortement connexe, il existe un arbre recouvrant, enraciné en ${\displaystyle r}$, avec tous les arcs dirigés vers ${\displaystyle r}$. Il suffit de colorer les arcs de cet arbre par la même couleur R pour obtenir un coloriage synchronisant : la suite de ${\displaystyle n}$ arcs R, où ${\displaystyle n}$ est le nombre de sommets, mène de tout sommet à ${\displaystyle r}$. Cette idée simple devient, plus élaborée, une des bases de la démonstration donnée par Trahtman.

Une extension de ce cas est le résultat de O'Brian : si le graphe est sans arcs multiples et a un circuit dont la longueur est un nombre premier, alors il possède un coloriage synchronisant avec toutes les flèches de ce circuit de même couleur.

Culik, Karhumäki et Kari[10] ont défini une opération de réduction qui permet, dans certains cas, de démontrer le résultat par récurrence ; c'est la notion de paire stable.

Deux états ${\displaystyle s}$ et ${\displaystyle t}$ forment une paire stable si, pour tout mot ${\displaystyle x}$, il existe un mot ${\displaystyle y}$ tel que le produit ${\displaystyle xy}$ mène ${\displaystyle s}$ et ${\displaystyle t}$ dans le même état. Dans un automate synchronisant, toute paire d’états est stable. Si ${\displaystyle (s,t)}$ est une paire stable, alors toute paire ${\displaystyle (s\cdot w,t\cdot w)}$ est stable ; de plus, si ${\displaystyle (s,t)}$ et ${\displaystyle (t,r)}$ sont deux paires stables, alors ${\displaystyle (s,r)}$ est une paire stable : la relation ${\displaystyle s\equiv t}$ si ${\displaystyle (s,t)}$ est donc une relation d’équivalence, et de fait une congruence (si ${\displaystyle s\equiv t}$ alors ${\displaystyle s\cdot x\equiv t\cdot x}$). L'énoncé est :

Un corollaire est de Kari[9] :

Si l’automate obtenu en fusionnant les paires stables possède un coloriage synchronisant, alors l’automate de départ en possède un également.

La preuve de Trahtman est constructive et donne un algorithme qui permet de synchroniser le graphe en temps polynomial. L’algorithme de Trahtman est cubique en la taille du graphe. L’algorithme peut être vu comme suit : on cherche une paire stable de sommets ${\displaystyle (s,t)}$, on fusionne la paire, on cherche un coloriage synchronisant du graphe plus petit obtenu, puis on remonte le coloriage au graphe de départ : si dans le graphe de départ, il y a une flèche ${\displaystyle (s,c,t)}$ et pas d’arc ${\displaystyle ({\bar {s}},c,{\bar {t}})}$ dans le quotient, il existe un arc ${\displaystyle ({\bar {s}},d,{\bar {t}})}$ dans le graphe quotient pour une couleur ${\displaystyle d\neq c}$ ; on échange les couleurs ${\displaystyle c}$ et ${\displaystyle d}$ des arcs partant de ${\displaystyle s}$.

Pour trouver une paire stable, on considère le graphe composé des arcs d’une couleur fixée R. C’est un graphe fonctionnel, avec un arc et un seul sortant de chaque sommet. Chaque composante connexe, appelée un amas (en anglais cluster), est formée d’un circuit et d’un ensemble d’arborescences greffées sur ce circuit. Le niveau d’un sommet est sa distance à un sommet du circuit. Un sommet maximal est un sommet de niveau maximal. C'est une feuille d'une arborescences (sauf si tous les sommets sont de niveau 0).

L'observation cruciale de Trahtman est la suivante :

Si tous les sommets maximaux appartiennent à une même arborescence, alors le graphe possède une paire stable. Soit ${\displaystyle r}$ la racine ce cette arborescence. Cette paire est composée du sommet précédent ${\displaystyle r}$ dans le circuit de l’amas, et du sommet précédent ${\displaystyle r}$ dans l’arborescence, sur le chemin du sommet maximal vers ${\displaystyle r}$.

Les sommets ${\displaystyle p}$ et ${\displaystyle q}$ sont maximaux, le sommet ${\displaystyle s}$ ne l'est pas.

La preuve du théorème se poursuit par une série d'échanges (flips en anglais) qui consistent à échanger les couleurs des arcs sortant d'un sommet pour raccourcir ou briser les circuits et pour diminuer les niveaux des sommets.