DOI: 10.17587/prin.7.498-508

УДК: 004.4

Исследование графа автоматом

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

Модели, описывающие объекты и технологические процессы в виде графов и анализирующих их свойства автоматов, востребованы и активно используются при разработке аппаратных и программных средств различного назначения. Настоящая статья является первой в серии из трех публикаций, посвященных исследованию графов автоматами. Автомат двигается по ребрам графа, используя вершины графа как ячейки памяти для чтения/записи. Рассмотрены алгоритмы обхода графа (проход по всем ребрам) с оценкой их сложности в зависимости от вида графа и типа автомата. В последующих статьях будут представлены результаты по исследованию графов (в том числе недетерминированных или динамически меняющихся) коллективом автоматов.

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

Стр. 498–508