- Partager cette page :
- Version PDF
Séminaire de David Auger
Invariants linéaires et groupe de routage pour les marches de rotor dans les graphes orientés
Une marche de rotor (ou routage rotor) est un automate cellulaire où une ou plusieurs particules se déplacent le long des arcs d'un graphe selon des règles simples consistant à alterner le choix des arcs sortants à chaque passage sur un sommet.
Nous montrerons comment le problème ARRIVAL, consistant à déterminer quel sera l'état final de ce graphe au terme du processus de routage, peut être résolu dans des graphes simples par un calcul algébrique élémentaire. Afin de généraliser ce résultat à d'autres graphes, nous présenterons un cadre de routage dit linéaire généralisant les rotors classiques, ainsi que la notion de graphes de routage couplés, permettant de mettre en lumière les principes algébriques sous-jacents aux marches de rotor.
Nous montrerons comment le problème ARRIVAL, consistant à déterminer quel sera l'état final de ce graphe au terme du processus de routage, peut être résolu dans des graphes simples par un calcul algébrique élémentaire. Afin de généraliser ce résultat à d'autres graphes, nous présenterons un cadre de routage dit linéaire généralisant les rotors classiques, ainsi que la notion de graphes de routage couplés, permettant de mettre en lumière les principes algébriques sous-jacents aux marches de rotor.