Возможность и сложность распознавания графов тремя агентами

Рассматривается проблема распознавания конечных графов тремя агентами. По- строен алгоритм распознавания неориентированных графов, временная и емкостная сложности которого равны O(n2). При распознавании два агента, передвигающи- еся по графу, используют по две различные краски (всего три краски). Алгоритм основан на методе обхода графа в глубину.