Оценки времени установления автоматом свойств графа быть деревом и псевдодеревом

В данной работе рассматриваются автоматы, осуществляющие обход связных плоских простых неориентированных графов с целью установления их свойств. Приводится алгоритм, с использованием которого автомат с двумя красками может установить, является ли граф, обход которого он совершает, деревом или псевдодеревом, и определяются оценки для числа шагов, которое должен совершить автомат.