Построение прямого и обратного остовов автоматами на графе

Аннотация

В работе представлен алгоритм параллельного исследования графа. Автомат на графе является аналогом машины Тьюринга - ячейки ленты соответствуют вершинам графа, где автомат может сохранять некоторую информацию, а движение по ленте соответствует движениям по дугам графа. Такая система может рассматриваться также как совокупность автоматов, размещенных в вершинах графа и взаимодействующих путем посылки сообщений по дугам. Каждый автомат изменяет свое состояние в соответствии с данными, сохраняемыми в вершине, а движение по дугам заменяется посылкой сообщений. Время работы предлагаемого алгоритма параллельного исследования графа ограничено сверху O(n/k+D), где n - число вершин графа, D - диаметр графа, максимальная длина простого пути (пути без самопересечений). В результате работы алгоритма строится два остова графа: прямой остов, корнем которого является корневая вершина графа, ориентированный от корня, и обратный остов, ориентированный к корню.