Abstract:
In this paper, we consider automata that traverse connected plane simple undirected graphs in order to establish their properties. An algorithm is presented, using which an automaton with two colors can determine whether the graph it traverses is a tree or a pseudotree, and upper bounds are determined for the number of steps that the automaton must make.