Сложность восстановления графов, являющихся квазикольцами и квазидеревьями

Abstract

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

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

The modifications of the reconstruction a graph algorithm by agent moving moving through his edges, read and modify marks on the elements of the graph are analyzed. Found and research operations on graphs. The resulting graph of these operations is reconstructed with the use of stone, which is the sum of the number of stones needed to reconstruct the original components.