ResearchBib Share Your Research, Maximize Your Social Impacts
Sign for Notice Everyday Sign up >> Login

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

Journal: Збірник наукових праць фізико-математичного факультету ДДПУ (Vol.-, No. 3)

Publication Date:

Authors : ;

Page : 104-113

Keywords : распознавание графа; обход в глубину; агент-исследователь; агент-экспериментатор;

Source : Downloadexternal Find it from : Google Scholarexternal

Abstract

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

Last modified: 2018-02-21 05:10:13