Стьопкін А. В. Розпізнавання графів за допомогою колективу агентів.

Диссертационная работа посвящена проблеме анализа свойств конечных простых неориентированных графов - проблеме распознавания графа при помощи коллектива агентов, а именно исследованию самого процесса распознавания графа с целью повышения эффективности его распознавания. При этом одним из центральных моментов исследования является изучение сложности коммуникации между агентами. Предложен новый метод распознавания графа, при помощи построения на его вершинах неявной нумерации, путем разметки элементов графа с помощью красок. На основе этого метода разработан базовый алгоритм, в котором каждый агент-исследователь использует две различные краски (всего три краски). В этом алгоритме впервые, наряду с временной T n , емкостной S n сложностями и числом переходов по ребрам, совершаемых агентами-исследователями, исследуется коммуникационная сложность K n - сложность, определяемая количеством и объемом сообщений, которыми нужно обменяться агентам-исследователям с агентом-экспериментатором для распознавания графа. Базовый алгоритм распознавания имеет кубические, от числа вершин графа, временную и коммуникационную сложности, квадратичную емкостную сложность и кубическую верхнюю оценку числа переходов по ребрам, совершаемых агентами-исследователями.