| Résumé | We consider the model of exploration of an undirected graph
G by a single agent which is called the rotor-router mechanism or
the Propp machine (among other names).
Let $pi_v$ indicate the edge adjacent to a node v which
the agent took on its last exit from v.
The next time when the agent enters node v,
first a "rotor" at node v advances pointer $pi_v$ to
the edge $next(pi_v)$ which is next after the edge $pi_v$ in a fixed cyclic
order of the edges adjacent to v.
Then the agent is directed onto edge $pi_v$ to move to the next node.
It was shown before that after initial O(mD) steps,
the agent periodically follows one established Eulerian cycle, that is,
in each period of 2m consecutive steps the agent traverses
each edge exactly twice, once in each direction.
The parameters m and D are the number of edges in G and the diameter of G.
We investigate the robustness of such exploration
in presence of faults in the pointers $pi_v$ or dynamic changes in the
graph.
We show that after the exploration establishes an Eulerian cycle,
(i) if at some step the values of
k pointers $pi_v$ are arbitrarily changed, then a new Eulerian
cycle is established
within O(km) steps;
(ii) if at some step k edges are added to the graph,
then a new Eulerian cycle is established
within O(km) steps;
(iii) if at some step an edge is deleted from the graph, then
a new Eulerian cycle is established
within $O(gamma m)$ steps, where $gamma$ is the smallest number of edges
in a cycle in graph G containing the deleted edge.
Our proofs are based on the relation between Eulerian cycles and
spanning trees known as the "BEST" Theorem (after de Bruijn, van
Aardenne-Ehrenfest, Smith and Tutte).
|