Базовый алгоритм восстановления конечного графа

Abstract

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

Розглядається задача відновлення графа агентом, який переміщується по його ребрах, що прочитує ізмінює мітки на елементах графа. Запропоновано базовий метод відновлення. Алгоритм потребує 2 різні фарби і кубічного, від числа вершин графа, числа кроків. Знайдено модифікації алгоритму, які знижують верхню оцінку часової складності. Знайдено операції над графами, результуючий граф яких має верхню оцінку складності виконання базового алгоритму не гірше, ніж вихідний.

The problem of reconstructing a graph agent moving through his edges, read and modify marks on the elements of the graph. We propose a basic method of reconstruction. The algorithm requires 2 different colors and cube of the number of vertices number of steps. Found modification of the algorithm, which lowers the upper bound of time complexity. Found the operation on graphs, the resulting graph which has an upper bound for the complexity of the basic algorithm is not worse than the original.