Реферат по теме выпускной работы

Содержание

• Введение
• 1. Актуальность темы
• 2. Цель и задачи исследования, планируемые результаты
• 3. Основные определения
• 4. Обзор существующих алгоритмов по восстановлению графов
• 4.1 Бесконечное исследование графов
• 4.2 Алгоритм распознавания конечных графов тремя агентами
• 4.3 Восстановление графа с использованием пометки одного типа
• 4.4 Детерминированная разметка графа
• 5. Алгоритм распознавания графов коллективом агентов
• Выводы
• Список источников

Введение

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

В мире существует огромное количество различного рода сред, требующих изучения. Исследование среды – это своего рода дискретная система, представленная как модель взаимодействия управляющей и управляемой системы, взаимодействие которых зачастую представляется как процесс перемещения управляющего автомата по графу управляемой системы. В качестве модели рабочей среды мобильных роботов рассматриваются конечные связные неориентированные графы, вершины которых помечены одним цветом.

Исследованию графа при помощи одного агента посвящено много работ, получено множество результатов о возможности и сложности такого распознавания. Однако остается малоисследованным распознавание графа при помощи нескольких блуждающих по нему агентов. Актуальной является задача по распознаванию графа несколькими блуждающими по нему мобильными агентами.

1. Актуальность темы

Одной из центральных и актуальных задач робототехники является задача распознавания неизвестной среды блуждающими роботами [3]. Существует множество алгоритмов для ее решения. Центральным моментом при распознавании среды – роботы могут мешать друг другу или блокировать друг друга. Актуальными проблемами являются алгоритм расхождения двух роботов, а также прохождение робота по чужому пути. Таким образом, возникает необходимость в разработке оптимальных алгоритмов для робототехники, которые могли бы иметь минимальную емкостную, временную и коммуникационную сложность.

Магистерская работа посвящена актуальной научной задаче по анализу и разработке алгоритма исследования графов коллективом агентов, направленного на уменьшение временной, емкостной и коммуникационной сложности алгоритма. В качестве целевого базиса используется алгоритм Степкина А.В., Грунского И.С. – Базовый алгоритм восстановления графов коллективом агентов, а инструментальными средствами исследования выступают Rational Rose и Java SE [12].

Важной в работе является задача восстановления графа, то есть создание таких маршрутов движения агентов по неизвестному графу, разметки его элементов, сбора и обработки локальной информации о графе и способов построения графа по этой информации, чтобы работа роботов не блокировалась, не повторялась и не простаивалась. А также задачи, связанные с оптимизацией расходов ресурсов и затрат времени.

2. Цель и задачи исследования, планируемые результаты

Целью исследования является предложить методику восстановления графа коллективом агентов с меньшей временной сложностью или меньшим количеством типов меток.

Основные задачи исследования:

1. Изучить основные определения и обозначения теории графов.

2. Изучить и оценить способы уменьшения временной, емкостной и коммуникационной сложностей.

3. Проанализировать методы восстановления графов.

4. Разработка улучшенного метода восстановления графов коллективом агентов, который заключеается в уменьшении сложностиалгоритма.

5. Оценка скорости алгоритма на разных типах графов.

Объект исследования: процесс перемещения агентов по неориентированному, связному графу без дуг и петель, разметки его элелентов.

Предмет исследования: методика восстановления графа коллективом агентов, которая заключается в том, что используется три мобильных агента: два исследователя и один экспериментатор; производится запрос координат при нахождении новой вершине, а так же при нахождении перешейков.

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

3. Основные определения

Чтобы иметь точное представление об исследуемой среде, необходимо дать четкое определение используемым понятиям и определить параметры среды [6], [7], [8].

Теория графов – раздел дискретной математики, изучающий свойства графов. В общем смысле граф представляется как множество вершин(узлов), соединённых рёбрами. В строгом определении графом называется такая пара множеств G=(V, E), где V есть подмножество любого счётного множества, а E – подмножество VхV [15].

Инцидентность – понятие, используемое только в отношении ребра и вершины: если v₁, v₂ – вершины, а e(v₁, v₂) – соединяющее их ребро, тогда вершина v₁ и ребро e инцидентны, вершина v₂ и ребро e тоже инцидентны. Две вершины (или два ребра) инцидентными быть не могут. Для обозначения ближайших вершин используется понятие смежности.

Инцидентор – место соединения вершины и ребра (обычно используются парой – инцидентор от начальной вершины и инцидентор у конечной вершины).

Коллектив агентов – совокупность агентов, осуществляющих навигацию по графу.

Агент исследователь – агент, который ходит по среде и размечает вершины, одновременно передавая информацию агенту-экспериментатору.

Агент экспериментатор – агент, который восстанавливает граф по данным, переданным агентами исследователями.

Топологическая среда – среда, использующая описание связей между различными областями.

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

Обход графа в глубину – один из методов обхода графа. Алгоритм поиска описывается следующим образом: для каждой не пройденной вершины необходимо найти все не пройденные смежные вершины и повторить поиск для них. Используется в качестве подпрограммы в алгоритмах поиска одно- и двусвязных компонент, топологической сортировки.

Окрестность вершины k – множество вершин на расстоянии k от заданной вершины v; иногда толкуется расширительно как множество вершин, отстоящих от v на расстоянии не больше k.

Изоморфизм графа – два графа называются изоморфными, если существует перестановка вершин, при которой они совпадают. Иначе говоря, два графа называются изоморфными, если существует взаимно-однозначное соответствие между их вершинами и рёбрами, которое сохраняет смежность и инцидентность (графы отличаются только названиями своих вершин) [10].

Перешеек – вершина, в которой встречаются агенты исследователи. Размеченная вершина АИ₁, встречена АИ₂.

Петля – ребро, начало и конец которого находятся в одной и той же вершине.

Висячая вершина – вершина, степень которой равна 1 (то есть d(v)=1).

Матрица инцидентности графа – это матрица, значения элементов которой характеризуется инцидентностью соответствующих вершин графа (по вертикали) и его рёбер (по горизонтали). Для неориентированного графа элемент принимает значение 1, если соответствующая ему вершина и ребро инцидентны. Для ориентированного графа элемент принимает значение 1, если инцидентная вершина является началом ребра, значение -1, если инцидентная вершина является концом ребра; в остальных случаях (в том числе и для петель) значению элемента присваивается 0 [5].

Матрица смежности графа – это матрица, значения элементов которой характеризуются смежностью вершин графа. При этом значению элемента матрицы присваивается количество рёбер, которые соединяют соответствующие вершины. Петля считается сразу двумя соединениями для вершины, то есть к значению элемента матрицы в таком случае следует прибавлять два.

4. Обзор существующих алгоритмов по восстановлению графов

4.1 Бесконечное исследование графов

 

Проблема исследования графа, которая рассматривается французскими авторами R. Baldoni, F. Bonnet, A. Milani, M. Raynal [1] состоит в посещении одного или нескольких роботов каждой вершины связного графа. Эти мобильные существа иногда называют агентами или роботами. Поэтому мы используем слово Робот. Обход графа бесконечен, если робот бесконечное число раз посещает каждую вершину графа. Бесконечное исследование графа не избежать, когда роботы должны двигаться вместе, непрерывно отправляя информацию или ища динамические ресурсы (ресурсы, чье положение меняется с изменением времени). Если узлы и ребра имеют уникальные названия, обход графа относительно проще и не бесконечен.

Проблема обхода графа становится более серьезной, когда граф неизвестен. В таком контексте, устанавливают некоторые ограничения. Они касаются времени на посещение вершин, или размера памяти робота, необходимой для исследования графа, когда робот нуждается в O(D log d) битах локальной памяти для последовательного исследования любого графа размерностью и максимальной связностью d. Результаты невозможны для одного или нескольких роботов с ограниченной памятью (вычислительная сложность робота определена, когда определена степень автоматизации) для исследования всех графов. Главная часть результатов по исследованию графов выполнена с учетом того, что обход графа делается одним роботом. Только в последнее время обход (исследование) графа несколькими роботами стало популярным. Это мотивировано исследованиями на более эффективных (подготовленных) графах, с допустимыми дефектами, или нуждающихся в ослаблении точности для ограниченных возможностей одного робота.

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

4.2 Алгоритм распознавания конечных графов тремя агентами

 

Рассматриваемый алгоритм основан на стратегии поиска в глубину [2].

Вход: конечный, неориентированный граф G(V) без петель и кратных ребер неизвестный АИ и АЭ, все элементы графа окрашены краской 1, АИ₁ и АИ₂ расставляются в случайные вершины.

Выход: все элементы графа.

Данные: v₁ и v₂ – рабочие вершины графа G, в которых находятся агенты.

Эта стратегия такова: агенты идут в глубину, пока это возможно, возвращаются назад, ищут другой путь с еще не посещенными вершинами и не пройденными ребрами. В случае обнаружения смежной вершины, окрашенной в чужой цвет, агент метит все перешейки из текущей вершины в чужую область и сообщает второму АИ, через агента-экспериментатора, о необходимости распознавания помеченных перешейков. Пока второй АИ распознает перешейки, первый АИ не может метить новые перешейки. В случае отсутствия других возможных вариантов перемещения, кроме как пометить новый перешеек, первый АИ останавливается до того момента, пока второй АИ не распознает все помеченные перешейки [3].

Предлагаемая стратегия обладает рядом особенностей:

1) граф G агентам не известен;

2) при обходе графа G , агенты создают неявную нумерацию пройденных вершин: при первом посещении вершины она окрашивается агентом A в красный цвет (в желтый цвет в случае агента B) и ей фактически ставится в соответствие номер, равный значению переменной Сч_А для агента A (Сч_B для агента B ).

Отметим, что Сч_А и Сч_B принимают соответственно нечетные и четные значения. На основе нумерации и происходит восстановление графа путем построения графа H изоморфного G [4]. В процессе обхода агенты строят неявные деревья поиска в глубину. Относительно этих деревьев все ребра разделяются на древесные (окрашиваются при первом прохождении по ним красным либо желтым цветом), обратные (не принадлежат дереву и окрашиваются при первом прохождении в черный цвет) и ребра перешейки (соединяют деревья, построенные разными агентами). Древесные ребра проходятся как минимум 2 раза и при последнем проходе окрашиваются агентами в черный цвет. Обратные ребра проходятся один раз. А вот ребра перешейки проходятся каждым агентом по два раза: первый прошедший по нему агент метит перешеек, окрашивая его в красный цвет в случае агента A (в желтый цвет в случае агента B ), второй прошедший по нему агент распознает перешеек и красит его в черный цвет.

Красные (желтые) вершины графа G , на каждом шаге алгоритма, образуют красный (желтый) если это не возврат для распознания перешейков) – укорачивается, при распознавании обратного ребра и перешейков – не изменяется. Вершина, у которой все инцидентные ребра распознаны, окрашивается в черный цвет. Алгоритм заканчивает работу, когда красный и желтый пути становятся пустыми, а все вершины черными.

Предложен базовый метод восстановления ранее неизвестного графа с точностью до меток на элементах графов, при помощи передвигающегося по нему агента. На основе метода построен Базовый алгоритм, который использует две краски и имеет временную сложность T(G), O(n)<=T(G)<=O(n3).

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

Базовый метод [12] допускает модификации, которые позволяют получить лучшую оценку временной сложности и упрощают агента, который передвигается по графу, однако, накладывают дополнительные ограничения на восстанавливаемый граф. T(G) – временная сложность.

Модификация 1 – мобильный агент, O(n)<=T(G)<=O(n³).

Модификация 2 – O(n) <= T(G) <= O(n²).

Модификация 3 – порождает новые алгоритмы восстановления графа, но не улучшает сложность алгоритмов.

Модификация 4 – агент конечный автомат, классы графов для которых T(G)=O(n) , S(G) = O(n).

Модификация 5 – T(G)=O(n), агент использует две краски и ht камней, где ht – наибольшая высота дерева при обходе графа в глубину.

4.3 Восстановление графа с использованием пометки одного типа

 

При обходе графа и разметки его элементов агент не использует записанную ранее в память информацию, а только оперирует ею на определенных этапах обхода и разметки, возможно разделение агента на два агента: агента-исследователя и агента экспериментатора. Первый будет перемещаться по графу, считывать и изменять метки на элементах графа, и передавать сообщения агенту экспериментатору, а второй будет принимать сообщения, обрабатывать их и восстанавливать граф. Обратные ребра восстанавливаются при первом их появлении. При распознавании обратного ребра агент движется назад по красному пути до тех пор, пока не встретит вершину, соединенную с вершиной с не раскрашенным ребром. После этого переходит по данному ребру, раскрашивая его в красный, при этом, не раскрашивая инциденторы. Возвращаясь, агент движется по красному пути, не раскрашивая его. Алгоритм завершает работу, когда агент попадает в вершину с белыми инциденторами, которые не имеют смежных не раскрашенных вершин [14], [12].

4.4 Детерминированная разметка графа

 

Задача построения Д-разметки формулируется следующим образом. Агент устанавливается в произвольную вершину априори неизвестного ему графа, все вершины которого помечены одной и той же меткой. Агент должен осуществить Д-разметку вершин этого графа, причём если вершина уже помечена агентом, то её метка в дальнейшем не изменяется [13].

Построение минимальной Д-разметки на основе только локальной информации о вершинах графа представляется в общем случае невозможным. Поэтому в работе рассматривается построение жадных алгоритмов разметки. Показано, что с помощью Д-разметки агент может восстановить исследуемый граф с точностью до изоморфизма и что минимальная Д-разметка восстановленного графа может быть получена применением к его транзитивному замыканию известных в теории графов алгоритмов правильной раскраски.

Метод Д-разметки вершин агентом A3 основан на обходе графа в ширину. При этом для неявного именования вершин используются метки путей в них из начальной вершины по дереву обхода. Разработан соответствующий полиномиальный алгоритм.

Увеличение размера наблюдаемой агентом окрестности (т. е. объёма его входной информации) приводит к увеличению сложности робота, который реализует функции агента, поэтому целесообразно рассмотреть модель с ограничениями на размер наблюдения.

5. Алгоритм распознавания графов коллективом агентов

 

В выпускной работе рассмотрены и проанализированы существующие алгоритмы восстановления графов. В магистерской работе был разработан следующий алгоритм:

Вход: конечный, неориентированный граф G(V) без петель и кратных ребер неизвестный АИ и АЭ, все элементы графа окрашены краской 1, АИ₁ и АИ₂ расставляются в случайные вершины.

Выход: все элементы графа.

Данные: v₁ и v₂ – рабочие вершины графа G, в которых находятся агенты.

Возможности мобильных агентов АИ₁ и АИ₂: роботы передвигаются по графу из начальных случайных вершин v₁ и v₂ по ребрам (v₁,u₁) и(v₂,u₂) соответственно. Агенты могут изменять окраску вершин v₁ и u₁, v₂ и u₂, а также их инцеденторы соответственно ((v₁,u₁, u₁) и ((v₂,u₂,u₂) цветом 2 и 3 соответственно.

Находясь в вершине v, АИ воспринимает метки всех элементов окрестности Q(v). И на основании этих меток определяет, по какому ребру будет перемещаться, и как будет окрашивать элементы графа. АЭ передает, принимает и идентифицирует сообщения, полученные от АИ. АЭ обладает конечной, неограниченно растущей внутренней памятью, в которой фиксируется результат функционирования АИ на каждом шаге и строится представление графа G, вначале неизвестного агентам, списками ребер и вершин.

Через конечное число шагов АИ закончит разметку вершин, а АЭ восстановит неизвестный граф до изоморфизма, т.е. распознает граф.

Действия агентов: АИ: ход вперед, ход назад, используют 2 краски для определения того, находился ли в вершине АИ. АЭ: имеет неограниченную память, принимает от АИ сообщение, запрашивает координаты АИ для распознавания перешейков и идентификация вершин происходит по координатам (x_i, y_i). Спутник определяет местоположение АИ, отправляет координаты экспериментатору.

Краска агентам необходимы для того, чтобы агенты распознавали пройденный путь. Краской 2 и 3 агенты АИ1 и АИ2 размечают соответственно вершины, которые посетили, и конечный инцидентор ребра, по которым прошли.

Для решения поставленной задачи предлагается следующая стратегия:

Рисунок 1.4 – Работа агента исследователя (анимация: объем – 111 КБайт, количество кадров – 13, размер – 400х300)

1. Помещаем агентов в произвольные вершиныv₁[rand] и v₂[rand]. Переход на 2 шаг.

2. АИ₁ и АИ₂ размечает вершины цветом 2, размечает цветом 2 их конечные инциденторы. Переход на 3 шаг.

>i=0; j=0;
V[i] = 2;
V(v, u) = (false, true);
V[j] = 2;
V(v, u) = (false, true);

3. Передаем информацию (new vertex, если вершина была цвета 1 или vertex если вершина была цвета не равного цвету 1). Переход на 4 шаг.

AI1.send("new vertex");
AI2.send("new vertex");

4. АЭ строит вершину, ставит в соответствие вершине координаты, полученные с помощью спутника. Переход на 5 шаг.

getPosition(AI1);
drawVertex(getPosition(AI1).getX(), getPosition(AI1).getY());
AE.sendAI1("Go");
getPosition(AI2);
drawVertex(getPosition(AI2).getX(), getPosition(AI2).getY());
AE.sendAI2("Go");

5. АИ идет вглубь графа, пока есть вершины цвета 1. Иначе начинает движение назад, размечать конечные инциденторы, при этом начинается поиск перешейков. Переход на шаг 2, если есть неразмеченные вершины, иначе шаг 6.

6. В случае если перешеек найден, АИ отправляет информацию АЭ (vertex). АЭ принимает сообщение, делает запрос на получение координат АИ, и соединяет ребром вершины: из которой пришел АИ в которую пришел, путем приведения соответствия координат.

7. Путь назад продолжается до тех пор, пока АИ не придет в начальную вершину. Начальной вершиной будет считаться вершина, в которой нет неразмеченных смежных вершин и инциденторов.

Рисунок 1.5 –Восстановление графа агентом экспериментатором (анимация: объем – 33,4 КБайт, количество кадров – 6, размер – 400х300)

Cхема инициализации и взаимодействия агентов исследователей и агента экспериментатора представлена в печатной версии работы.

1. Инициализация счетчиков.

2. АЭ дает команду для начала восстановления.

3. АИ устанавливаются в различные друг от друга случайные вершины.

4. Пока АИ не остановились делаем проверки..

5. Если вершина не размечена и её конечный инцидентор не раскрашен, то раскрашиваем вершину и конечный инцидентор. АИ отправляет сообщение New vertex (новая вершина).

6. АЭ получает координаты найденной вершины, и строит её.

7. АЭ посылает команду АИ Дальше.

8. Если вершина размечена, но не раскрашен конечный инцидентор, то АИ отправляет сообщение Vertex (вершина, т.е. не новая). АЭ узнает координаты вершины в которую отходит неизвестное ребро и соединяет ребром вершину, из которой пришел АИ с вершиной, в которую шло неизвестное ребро.

9. Если вершины размечены и нет не раскрашенных конечных инциденторов, то АЭ отправляет команду АИ back (идти назад). Сделав шаг назад, АИ снова производит поиск неразмеченных ребер или вершин.

10. Если один из АИ пришел в начало, а другой АИ продолжает путь вперед, то производится команда переброса в свободную вершину с неразмеченной 2-окрестностью.

if(i==0&&AI2.state== next)
{
AI1.perebros();
}

11. Если один из АИ пришел в начало, а другой АИ идет назад, то АИ завершает свою работу.

if(i==0&&AI2.state== back)
{
AI1.state = finish;
}

12. Если один из АИ пришел в начало, а другой АИ завершил свою работу, то АИ первый также завершает свою работу.

if(i==0&&j==0&&AI2.state == finish)
{
AI1.state = finish;
}

Выводы

 

Проведен обзор и анализ существующих алгоритмов по восстановлению графов, выявлены их основные недостатки. Изучены основные определения и понятия.

Разработан алгоритм восстановления неориентированного связного графа без петель и кратных ребер коллективом агентов (двумя агентами исследователями и агентом экспериментатором), который заключается в использовании трех мобильных агентов, использовании двух красок; в запросе координат при нахождении новой вершины или перешейка; в отсутствии возвратов.

Произведена оценка сложности базового алгоритма и алгоритма с модификациями. Увеличена коммуникационная сложность за счет запроса координат агентов исследователей для агента экспериментатора с целью распознать перешейки, что сильно не повлияло на скорость выполнения процесса восстановления графа, т.к. запросы координат выполняет АЭ, у которого неограниченная память.

Анализ полученных результатов, показывает уменьшение значений временной и емкостной сложностей. Такие результаты достигаются за счет следующих модификаций.

1. Выбор ребра и проход по нему осуществляется за единицу времени. В базовом алгоритме временная сложность O(n³) – это O(n): прохождение АИ вперед*O(n): прохождение АИ назад*O(n): распознавание перешейков. В алгоритме с модификациями временная сложность O(n) – это синхронное прохождение АИ вперед (т.е. за единицу времени АИ восстанавливают 2 вершины) и назад. При распознавании перешейков агенты не производят возвраты, за счет приведения в соответствие вершины и координат вершины.

2. Емкостная сложность определяется размером списков вершин цвета 1 и цвета 2. АИ используют 2 цвета, размечая 1 цветом вершину и инцидентор. Третий цвет не используется, так как АИ возвращается по размеченным конечным инциденторам.

3. Коммуникационная сложность увеличивается за счет двойного обмена сообщениями: сначала АИ: нашел – АЭ: дальше или АИ: конец – АЭ: назад, а также АИ: нашел (перешеек) – АЭ: запрос координат – АЭ: дальше.

Примечание:

При написании данного автореферата выпускная работа еще не оформлена. Окончательная сдача работы: декабрь 2014 года. Полный текст работы и материалы по теме могут быть получены у автора или его руководителя после указанной даты.

Список источников

1. R. Baldoni, F. Bonnet, A. Milani, M. Raynal "Anonymous graph exploration without collision by mobile robots". Publication interne. – 2008 – 10 pages.
2. Грунский И.С., Стёпкин А.В. Распознавание конечного графа коллективом агентов. – Труды ИПММ НАН Украины. – 2009. – Т.19. – С. 43–52.
3. Стёпкин А.В. Распознавание графов коллективом агентов. // Мат. IV мiжнар. наук.-практ. конф. Сучасна iнформацiйна Україна: iнформатика, економiка, фiлософiя 2010, Донецьк, – т.1 – С. 139–143.
4. Грунский И.С., Татаринов Е.А. Алгоритм распознавания графов // Тр. 4 междунар. Конф. Параллельные вычисления и задачи управления PACO’2008, Москва, Ин-т Проблем Управления им. В.А. Трапезникова РАН, 2008 – С. 1483–1498.
5. Касьянов В.Н., Евстигнеев В.А. Графы в программировании: обработка, визуализация и применение. – СПБ.: БХВ – Петербург, 2003. – 1104 с.
6. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. – М.: Мир, 1979. – 536 с.
7. Кристофидес Н. Теория графов: алгоритмический подход / Н. Кристофидес. – М.: Мир, 1978. – 430 с.
8. Оре О. Теорія графів / Оре О. – М. : Наука, 1980. – 340 с.
9. Килибарда Г., Кудрявцев В.Б., Ушчумлич Щ. Коллективы автоматов в лабиринтах // Дискретная математика. – 2003. – Т. 15, вып. 3. – С. 3–40.
10. Кудрявцев В.Б., Алешин С.В., Подколзин А.С. Введение в теорию автоматов. – М.: Наука, 1985. – 320 с.
11. Капитонова Ю.В. Математическая теория проектирования вычислительных систем / Ю.В. Капитонова, А.А. Летичевский. – М.: Наука, 1988. – 296 с.
12. Грунский И.С. Распознавание конечного графа блуждающим по нему агентом / И.С. Грунский, Е.А. Татаринов // Вестник Донецкого университета. Сер. А. Естественные науки. – 2009. – № 1. – С. 492–497.
13. Сапунов С.В. Неотличимость вершин помеченных графов / С.В. Сапунов // Труды ИПММ. – 2008. 189 с.
14. Грунский И.С., Сапунов С.В. Восстановление графа операционной среды мобильного робота путем разметки вершин, пригодной для дальнейшей навигации. – 2012. C. 422–427
15. Материал из свободной электронной библиотеки Википедия: словарь теории графов. Электронный ресурс. Режим доступа: http://ru.wikipedia.org/wiki/Глоссарий_теории_графов