Возможность и сложность распознавания конечного графа коллективом агентов
Journal Title: Збірник наукових праць фізико-математичного факультету ДДПУ - Year 2010, Vol 1, Issue 10
Abstract
Рассматривается задача распознавания неизвестного графа коллективом агентов. Два агента-исследователя передвигаются по графу, изменяют и считывают метки на элементах графа и передают информацию агенту-экспериментатору, который строит представление исследуемого графа. Предложен алгоритм, который распознает любой конечный неориентированный граф. Для распознавания графа агентам требуется 2 различные краски, кубическое (от числа вершин графа) число шагов и квадратичная память. Метод основан на методе обхода графа в глубину.
Authors and Affiliations
А. В. Стёпкин
Keywords
Related Articles
- EP ID EP261781
- DOI -
- Views 68
- Downloads 0
Исследование сворачивания-разворачивания белков термофильных организмов с использованием метода Управляемой Молекулярной Динамики
В нашей работе исследовался один из белков (1csp), входящий в состав термофильных организмов /1/. Наиболее яркой особенностью этого белка является его пространственная структура – набор элементов β-структуры без каких-ли...
Наближення локально сумовних функцій малої гладкості операторами Валле Пуссена в інтегральній метриці
В роботi розглядаються питання наближення класiв Степанця L^ψ N операторами Вал- ле Пуссена в просторi L у випадку, коли множини L^ψ N складаються з функцiй малої гладкостi. Одержано асимптотичнi закони поведiнки верхнiх...
Вивчення явища заломлення світла і його законів в курсі фізики в закладах загальної середньої освіти
This article discusses the study of the phenomenon of light refraction and its laws on the course of physics in secondary schools. The authors offer material on this topic, which uses unconventional methodological techni...
Терминальное управление нелинейными системами с разрывами решений методом конечного состояния
Предложено обобщение метода конечного состояния для синтеза терминального управ- ления многомерными нелинейными дискретными системами. Описана модель конечного состояния, а также алгоритм непрерывного и дискретного управ...
k -КОЛЬОРОВI ХОРДОВI n-ДIАГРАМИ
В статтi розглядається клас k -кольорових хордових дiаграм з n хордами. Для натуральних k > 2 i 2n = k · p встановлено формули для пiдрахунку як числа неiзоморфних (з точнiстю до повороту), так i числа нееквiвалентних (в...