Coloriage des routes

Le coloriage des routes est un problème combinatoire qui relève à la fois de la théorie des graphes et en théorie des automates. Il s'agit d'une propriété de synchronisation dans un réseau routier. La question est de savoir si l'on peut « colorier » les routes d'un réseau routier (ou, de manière équivalente, colorier les arcs d'un graphe fini) de telle sorte que, quel que soit le point de départ, en suivant la séquence de routes de même nom (ou de même couleur), on arrive au même point d'arrivée. Le problème du coloriage des routes et la conjecture correspondante (la conjecture du coloriage des routes) ont d'abord été formulés par Adler et Weiss^[1] en 1970. Le théorème correspondant, le théorème du coloriage des routes, a été démontré par Avraham Trahtman en 2009^[2].

Exemple

L'image à droite montre un graphe orienté avec huit sommets, où chaque sommet a degré sortant 2. Dans cet exemple, les sommets ont aussi degré entrant 2, mais ceci n'a pas d'influence sur la suite. Les arcs sont colorés en bleu (Modèle:Bleu) ou en rouge (Modèle:Rouge). La propriété de synchronisation dit que, si on suit des arcs d'une séquence fixe de couleurs, alors on arrive toujours au même sommet, quel que soit le point de départ. Ainsi :

en suivant dans l'ordre les neuf arcs du chemin de couleurs « Modèle:Bleu Modèle:Rouge Modèle:Rouge Modèle:Bleu Modèle:Rouge Modèle:Rouge Modèle:Bleu Modèle:Rouge Modèle:Rouge », on arrive au sommet jaune, et ceci quel que soit le sommet de départ.
de même, en suivant dans l'ordre les neuf arcs du chemin de couleurs « Modèle:Bleu Modèle:Bleu Modèle:Rouge Modèle:Bleu Modèle:Bleu Modèle:Rouge Modèle:Bleu Modèle:Bleu Modèle:Rouge », on arrive au sommet vert, quel que soit le sommet de départ.

Le théorème du coloriage affirme que, pour une certaine catégorie de graphes, il est toujours possible de créer un coloriage avec cette propriété.

Description formelle

Soit $G$ un graphe orienté fortement connexe fini, dont tous les sommets ont même degré sortant $k$ . Soit $A$ un alphabet à $k$ lettres. Un coloriage synchronisant^[3] (aussi connu sous le terme collapsible coloring en anglais) de $G$ ' est un étiquetage des arcs de $G$ avec les lettres de $A$ tel que

chaque sommet possède exactement un arc sortant portant une lettre donnée et que,
pour chaque sommet $s$ du graphe, il existe un mot $w$ sur $A$ tel que tous les chemins de $G$ étiquetés par $w$ mènent à $s$ .

La terminologie de coloriage synchronisant est due à la relation entre cette notion et celle de mot synchronisant dans la théorie des automates finis^[4] : Le graphe avec son étiquetage est le graphe d'un automate fini déterministe complet. La condition de synchronisation se traduit par l'existence d'un mot $w \in A^{*}$ tel que $q \cdot w = s$ pour tout sommet $q$ de $G$ . Un tel mot est dit synchronisant.

Pour qu'un tel coloriage puisse exister, une condition nécessaire est que le graphe $G$ est Modèle:Lien^[5]Modèle:,^[6]. Le théorème du coloriage énonce que cette apériodicité est aussi une condition suffisante pour l'existence d'un tel coloriage :

Modèle:Théorème

Relation avec les automates

Synchronisation

Le graphe avec son étiquetage est le graphe d'un automate fini déterministe complet sur l'alphabet $A$ des couleurs. Une suite de couleurs est un mot $w \in A^{*}$ , et l'existence d'un mot synchronisant revient à l'existence d'un mot $w \in A^{*}$ tel que $q \cdot w = s$ pour un sommet $s$ et tout sommet $q$ de $G$ . Il est commode d'utiliser la notation que voici : pour un ensemble $P$ de sommets et un mot $w$ , on note $P \cdot w = {p \cdot w ∣ p \in P}$ ; c'est l'ensemble des sommets atteints à partir d'un somme de $P$ par un chemin étiqueté par $w$ . Un mot synchronisant est un mot $w$ tel que $Q \cdot w$ est un singleton. On appelle rang d'un mot $w$ le nombre d'éléments de $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].

Jetons

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 Modèle:Rouge ou Modèle:Bleu, les jetons se déplacent d'un état au suivant selon la couleur. Après une séquence de lettres $w$ , chaque état contient des jetons dont le nombre est le nombre d'états qui sont envoyés sur cet état par $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.

Preuves

Avant la démonstration de Trahtman en 2009, des cas particuliers ont été prouvés, notamment par O'Brien^[8] et par Jarkko Kari^[9].

Un cas simple

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 $r$ un tel sommet. Comme le graphe est fortement connexe, il existe un arbre recouvrant, enraciné en $r$ , avec tous les arcs dirigés vers $r$ . Il suffit de colorer les arcs de cet arbre par la même couleur Modèle:Rouge pour obtenir un coloriage synchronisant : la suite de $n$ arcs Modèle:Rouge, où $n$ est le nombre de sommets, mène de tout sommet à $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.

Paire stable

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

Modèle:Théorème Un corollaire est de Kari^[9] : Modèle:Théorème 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.

Preuve de Trahtman (esquisse)

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 $(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 $(s, c, t)$ et pas d’arc $(\bar{s}, c, \bar{t})$ dans le quotient, il existe un arc $(\bar{s}, d, \bar{t})$ dans le graphe quotient pour une couleur $d \neq c$ ; on échange les couleurs $c$ et $d$ des arcs partant de $s$ .

Pour trouver une paire stable, on considère le graphe composé des arcs d’une couleur fixée Modèle:Rouge. 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 $r$ la racine ce cette arborescence. Cette paire est composée du sommet précédent $r$ dans le circuit de l’amas, et du sommet précédent $r$ dans l’arborescence, sur le chemin du sommet maximal vers $r$ .

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.

Développements

Trahtman a présenté en 2010^[11] un algorithme au colloque CSR ; Marie-Pierre Béal et Dominique Perrin ont décrit un algorithme en temps quadratique pour trouver un coloriage synchronisant^[12]. Les relations avec la conjecture de Cerny sur la longueur d'un mot synchronisant sont détaillés dans le chapitre de Béal et Perrin du livre Combinatorics, automata and number theory^[3]

Articles connexes

Notes

Modèle:Traduction/Référence Modèle:Références

Références

Articles

Modèle:Ouvrage.

Modèle:Article.

Modèle:Article.

Modèle:Article.

Modèle:Chapitre.

Modèle:Article.

Modèle:Chapitre.

Modèle:Article.

Modèle:Chapitre.Modèle:Plume

Modèle:Article.

Présentations

Modèle:Portail

↑ Modèle:Harvsp
↑ Modèle:Harvsp.
↑ ^3,0 ^3,1 et ^3,2 Modèle:Harvsp.
↑ Modèle:Harvsp.
↑ Un graphe orienté est apériodique s'il n'existe pas d'entier >1 qui divise les longueurs de tous ses circuits ou si, de manière équivalente, le pgcd des longueurs de ses chemin est 1.
↑ Modèle:Harvsp.
↑ Modèle:Harvsp.
↑ Modèle:Harvsp.
↑ ^9,0 et ^9,1 Modèle:Harvsp.
↑ Modèle:Harvsp.
↑ Modèle:Harvsp.
↑ Modèle:Harvsp.

[1] Modèle:Harvsp

[2] Modèle:Harvsp.

[CANT-3] 3,0 ^3,1 et ^3,2 Modèle:Harvsp.

[4] Modèle:Harvsp.

[5] Un graphe orienté est apériodique s'il n'existe pas d'entier >1 qui divise les longueurs de tous ses circuits ou si, de manière équivalente, le pgcd des longueurs de ses chemin est 1.

[6] Modèle:Harvsp.

[mpb-7] Modèle:Harvsp.

[8] Modèle:Harvsp.

[kari_2003-9] 9,0 et ^9,1 Modèle:Harvsp.

[10] Modèle:Harvsp.

[11] Modèle:Harvsp.

[12] Modèle:Harvsp.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

Coloriage des routes

Sommaire

Exemple

Description formelle