Распознавание конечных графов тремя агентами

Abstract

В статье рассматривается проблема распознавания конечных графов тремя агентами. Два агента-исследователя передвигаются по графу, считывают, анализируют и изменяют метки элементов графа, передают информацию о своих передвижениях агенту-экспериментатору, который и распознает исследуемый граф. Предложен алгоритм временной сложности О(n³) и емкостной – О(n²), который распознает любой конечный неориентированный граф. При распознавании каждый агент использует две различные краски (всего три краски). Метод основан на методе обхода графа в глубину.

У статті розглядається проблема розпізнавання скінченних графів трьома агентами. Два агенти-дослідники рухаються графом, зчитують, аналізують та змінюють помітки елементів графа, передають інформацію про свої переміщення агенту-експериментатору, який розпізнає досліджуваний граф. Запропоновано алгоритм часової складності О(n³) та ємнісної – О(n²), який розпізнає будь-який скінченний неорієнтований граф. Для розпізнавання кожному агенту необхідно дві різні фарби (усього три фарби). Метод базується на методі обходу графа в глибину.

The Problem of finite graphs exploration by three agents is considered in this work. Two agents-researchers move on graph, they read, analyze and change marks of graph elements, transfer the information about their movements and colorings to the agent-experimenter. It builds explored graph representation. The algorithm with О(n³) time (n is amount of nodes of graph) and О(n²) space complexities is proposed. It recognizes any finite non-oriented graph. For graph exploration each agent needs two different marks (three colors in total). The method is based on the depth-first traversal method.