Возможность и сложность распознавания графов коллективом агентов
Journal Title: Збірник наукових праць фізико-математичного факультету ДДПУ - Year 2013, Vol 0, Issue 3
Abstract
В работе рассматривается задача распознавания конечного графа коллективом агентов. Два агента-исследователя одновременно передвигаются по графу, считывают и изменяют отметки на элементах графа, передают необходимую информацию агенту экспериментатору, который и распознает исследованный граф. Предложен алгоритм кубической (от числа вершин графа) временной и квадратической емкостной сложностей, который распознает любой конечный неориентированный граф без петель и кратных ребер. Для распознавания графа каждому агенту необходимо 2 различные краски (всего 3 краски). Метод основан на методе обхода графа в глубину.
Authors and Affiliations
А. В. Стёпкин
Keywords
Related Articles
- EP ID EP267088
- DOI -
- Views 87
- Downloads 0
Використання систем комп’ютерної математики при розв’язанні завдань теорії графів
У статтi обговорюються особливостi систем комп’ютерної математики при розв’язаннi завдань теорiї графiв. Наводяться загальнi характеристики систем комп’ютерної матема- тики для вирiшення задач дискретної оптимiзацiї. Пре...
Використання віртуальних лабораторних робіт при проведенні фізичного практикуму в 11 класі ЗОШ
Впровадження вiртуального лабораторного практикуму в навчальний процес, як пiдготовчого етапу до виконання робiт фiзичного практикуму з реальними фiзичними приладами, дозволяє пiдвищити ефективнiсть навчання та якiсть фо...
Ідемпотенти вінцевих голоморфів напівгруп
У роботі описуються ідемпотенти вінцевого голоморфу напівгрупи з нульовим множенням (правих нулів, лівих нулів) та симетричної напівгрупи.
Дослідження проблеми стійкості криптографічних систем
Побудовано обчислювально захищену криптосистему, яку протестовано на повідомлені довжиною в 1028⋅ k (k = 1, 5, 10, 20, 100) символів. Показано залежність часу роботи алгоритмів шифрування ( ) TC , дешифрування (T C) D та...
Приближение периодических функций многих переменных
Получены элементы суммирующих треугольных матриц операторов повторных методов Валле Пуссена.