Возможность и сложность распознавания графов коллективом агентов
Journal Title: Збірник наукових праць фізико-математичного факультету ДДПУ - Year 2013, Vol 0, Issue 3
Abstract
В работе рассматривается задача распознавания конечного графа коллективом агентов. Два агента-исследователя одновременно передвигаются по графу, считывают и изменяют отметки на элементах графа, передают необходимую информацию агенту экспериментатору, который и распознает исследованный граф. Предложен алгоритм кубической (от числа вершин графа) временной и квадратической емкостной сложностей, который распознает любой конечный неориентированный граф без петель и кратных ребер. Для распознавания графа каждому агенту необходимо 2 различные краски (всего 3 краски). Метод основан на методе обхода графа в глубину.
Authors and Affiliations
А. В. Стёпкин
Keywords
Related Articles
- EP ID EP267088
- DOI -
- Views 86
- Downloads 0
Про екологічне виховання учнів на уроках природничо-наукових дисциплін
Стаття присвячена актуальним питанням екологiчного виховання учнiв на уроках природничо-наукових дисциплiн.
Психологічні особливості динаміки професійної самосвідомості майбутніх вчителів математики у процесі навчальної діяльності
Дане дослiдження присвячене вивченню психологiчних особливостей динамiки професiйної самосвiдомостi майбутнього вчителя математики у процесi навчальної дiяльностi, проводиться емпiрична перевiрка ефективностi запропонова...
Організація самостійної роботи студентів гуманітарних спеціальностей при вивченні дисципліни «Інформатика та ТЗН»
Робота присвячена проблемі формування навичок до самостійної роботи у студентів гуманітарних спеціальностей при вивченні дисципліни «Інформатика та ТЗН».
Алгоритм Форда-Фалкерсона
В роботi наведено реалiзацiю методу Форда-Фалкерсона для знаходження максимального потоку у транспортнiй мережi засобами мови програмування Pascal. Для реалiзацiї методу Форда-Фалкерсона використовується метод обходу гра...
Асимптотичні формули для відхилень подвійних операторів Фейєра
Отриманi асимптотичнi формули для верхнiх граней вiдхилень подвiйних операторiв Фейєра на класах перiодичних функцiй.