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

Abstract

В работе рассматривается проблема распознавания конечного неориентированного графа коллективом агентов. Построен алгоритм распознавания неизвестных графов временная сложность которого равна O(n), а емкостная – O(n2 logn), где n - число вершин графа. Для распознавания графа каждому агенту, передвигающемуся по графу, необходимо 2 различные краски (всего 3 краски). Метод основан на методе обхода графа в глубину.