Возможность и сложность распознавания графов коллективом агентов
Journal Title: Збірник наукових праць фізико-математичного факультету ДДПУ - Year 2013, Vol 0, Issue 3
Abstract
В работе рассматривается задача распознавания конечного графа коллективом агентов. Два агента-исследователя одновременно передвигаются по графу, считывают и изменяют отметки на элементах графа, передают необходимую информацию агенту экспериментатору, который и распознает исследованный граф. Предложен алгоритм кубической (от числа вершин графа) временной и квадратической емкостной сложностей, который распознает любой конечный неориентированный граф без петель и кратных ребер. Для распознавания графа каждому агенту необходимо 2 различные краски (всего 3 краски). Метод основан на методе обхода графа в глубину.
Authors and Affiliations
А. В. Стёпкин
Keywords
Related Articles
- EP ID EP267088
- DOI -
- Views 88
- Downloads 0
Використання віртуальних лабораторних робіт при проведенні фізичного практикуму в 11 класі ЗОШ
Впровадження вiртуального лабораторного практикуму в навчальний процес, як пiдготовчого етапу до виконання робiт фiзичного практикуму з реальними фiзичними приладами, дозволяє пiдвищити ефективнiсть навчання та якiсть фо...
Про екологічне виховання учнів на уроках природничо-наукових дисциплін
Стаття присвячена актуальним питанням екологiчного виховання учнiв на уроках природничо-наукових дисциплiн.
Розгляд технології Passіve Optіcal Network для побудови оптичної мережі при вивченні дисципліни Комп’ютерні системи та мережі
The work outlines the specifics of the construction of optical computer networks using the Passive Optical Network technology in the study of the discipline «Computer Systems and Networks». The expediency of using the ha...
Образование дефектов в монокристаллах германия при импульсном лазерном воздействии
Выполнены структурные исследования на поверхности германия (Ge) в области действия импульса лазерного излучения в режиме свободной генерации ( λ = 0, 694 мкм) длитель- ностью τ = 1 мс и энергией в импульсе W = 6 Дж. Сним...
Возможность и сложность распознавания конечного графа коллективом агентов
Рассматривается задача распознавания неизвестного графа коллективом агентов. Два агента-исследователя передвигаются по графу, изменяют и считывают метки на элементах графа и передают информацию агенту-экспериментатору, к...