DOI: 10.17587/prin.8.16-25

УДК: 004.4

Исследование ориентированного графа коллективом неподвижных автоматов

И. Б. Бурдонов, д-р физ.-мат. наук, вед. науч. сотр., igor@ispras.ru, А. С. Косачев, канд. физ.-мат. наук, вед. науч. сотр., kos@ispras.ru, Институт системного программирования РАН, Москва

Настоящая работа — третья в серии статей, посвященных исследованию графов автоматами. В первых двух работах были описаны автоматы, а также коллектив автоматов, которые двигались по дугам графа, обменивались между собой сообщениями по независимой от графа сети связи, в данной статье описаны автоматы, которые не двигаются, находятся в вершинах графа и обмениваются сообщениями, пересылаемыми по дугам графа. Кроме исследования графа, также рассмотрена задача параллельных вычислений на графе, в том числе динамически меняющемся.

Ключевые слова: ориентированный граф, упорядоченный граф, нумерованный граф, динамический граф, исследование графа, параллельные вычисления, автомат, робот, полуробот

Стр. 16–25