Анотація. Розглянуто задачу розпізнавання скінченних неорієнтованих графів колективом агентів. Два агента-дослідника одночасно рухаються графом, зчитують та змінюють помітки елементів графа, передають необхідну інформацію агенту-експериментатору, який будує уявлення про досліджуваний граф. Запропоновано алгоритм розпізнавання лінійної (від числа вершин графа) часової та квадратичної ємнісної складностей. Розроблено процедуру оптимізації розбиття графа на частини для розпізнавання різними агентами. Для розпізнавання два агенти, що рухаються графом, використовують по дві різні фарби (усього три фарби). Алгоритм базується на методі обходу графа в глибину.
Ключові слова: розпізнавання графа, колектив агентів, обхід графа.
Стёпкин Андрей Викторович,
ассистент кафедры Донбасского государственного педагогического университета, Славянск, Украина,
e-mail: stepkin.andrey@rambler.ru.