Распознавание графов с помощью трёх агентов
Journal Title: Збірник наукових праць фізико-математичного факультету ДДПУ - Year 2015, Vol 0, Issue 5
Abstract
Рассматривается задача распознавания графов с помощью трёх агентов. Два агента- исследователя перемещаются по графу, считывают и изменяют метки в вершинах, ребрах и инциденторах графа. Агент-экспериментатор получает от этих агентов информацию об их перемещении и метках, и на этой основе распознает исследуемый граф с точностью до отметок на графе. Предложен алгоритм распознавания квадратичной (от числа вершин графа) временной сложности, квадратичной емкостной сложности и коммуникационной сложности равной O((n²) · log(n)), при этом верхняя оценка числа ребер, посещенных агентами исследователями равна O(n²). Для распознавания агентам требуется по две различные краски (всего три краски). Алгоритм основан на методе обхода графа в глуби- ну.
Authors and Affiliations
А. В. Степкин
Keywords
Related Articles
- EP ID EP263101
- DOI -
- Views 61
- Downloads 0
ФОРМУВАННЯ СОЦIАЛЬНОЇ КОМПЕТЕНТНОСТI СПОСОБОМ ГРУПОВОЇ ДIЯЛЬНОСТI НА УРОКАХ ФIЗИКИ
На протязi багатьох рокiв педагоги намагалися з’єднати навчання i виховання. Але фiзика вважалась такою наукою,де важливим було отримання знань.Своєю статею ми намагаємося показати, що i на точних науках iснує можливiсть...
Організація роботи з обдарованими дітьми в умовах звичайного учнівського колективу
The article highlights the main features of a gifted child and, taking into account these features, outlines general, justified and appropriate approaches to the organization of work with gifted children in physics class...
Використання проектних технологій на уроках математики
Робота присвячена використанню проектних технологій на уроках математики.
РАСПОЗНАВАНИЕ КОНЕЧНЫХ ГРАФОВ КОЛЛЕКТИВОМ АГЕНТОВ.
В работе рассматривается задача распознавания конечных графов тремя агентами. Предложен алгоритм квадратических (от числа вершин графа) временной и емкостной сложностей, который распознает любой конечный неориентированны...
Використання комп’ютерних технологій в процесі викладання астрономії
Розглянутi питання пiдвищення мотивацiї навчання, активiзацiї розумової дiяльностi, творчого мислення учнiв шляхом впровадження комп’ютерних технологiй у процес викладання астрономiї. Наведено ряд методичних рекомендацiй...