This article is cited in 2 papers

Part 3. Mathematical models

Automaton analysis of the properties of a graph to be a tree and a pseudo-tree

A. A. Demidova

Lomonosov Moscow State University

Abstract: In this paper, we investigate the use of automata with erasable colors to determine the properties of connected planar undirected simple graphs. The following facts are proved: two erasable colors are enough for automata to determine whether the graph is a tree or a pseudo-tree.

Keywords: Automata, graphs, trees, pseudotrees.