Graph automata were first introduced by P. Rosenstiehl [10], under the name of intelligent graphs, surely because a network of finite automata is able to know some properties about its own structure. Hence P. Rosenstiehl created some algorithms that find Eulerian paths or Hamiltonian cycles in those graphs, with the condition that every vertex has a fixed degree [11]. Those algorithms are called “myopic” since each automaton has only the knowledge of the state of its immediate neighborhood. This hypothesis seems to be absolutely essential for the modelisation of the physical reality. A. Wu and A. Rosenfeld ([12] [13]) developed ideas of P. Rosenstiehl, using a simpler and more general formalism: the d-graphs. For each of these authors, a graph automata is formed by synchronous finite automata exchanging information according to an adjacent graph.