Реферат за темою випускної роботи

Зміст

• Вступ
• 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, Е), де V є підмножина будь-якої рахункової безлічі, а E – підмножина VхV [15].

Інцидентність – поняття, що використовується тільки відносно ребра і вершини: якщо v₁, v₂ – вершини, а е (v₁, v₂) – з'єднує їх ребро, тоді вершина v₁ та ребро е інцидентні, вершина v₂ і ребро е теж інцидентні. Дві вершини (або два ребра) інцидентними бути не можуть. Для позначення найближчих вершин (ребер) використовується поняття суміжності.

Інцідентор – місце з'єднання вершини і ребра (зазвичай використовуються парою – інцідентор від початкової вершини і інцідентор у кінцевій вершині).

Колектив агентів – сукупність агентів, що здійснюють навігацію по графу.

Агент дослідник – агент, який ходить по середовищу, і розмічає вершини, одночасно передаючи інформацію агенту-експериментатору (АІ).

Агент експериментатор – агент, який відновлює граф за даними, переданим агентом дослідником (АЕ).

Топологічна середа – середа, що використовує опис зв'язків між різними областями.

Кратні ребра – кілька ребер, інцидентних однієї і тієї ж парі вершин. Зустрічаються в мультіграфах.

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

Околиця вершини K до – безліч вершин на відстані K від заданої вершини V; іноді тлумачиться розширено як безліч вершин, віддалених від V на відстані не більше K.

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

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

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

Висяча вершина – вершина, ступінь якої дорівнює 1 (тобто г (у)=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(n³).

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

Базовий метод [12] допускає модифікації, які дозволяють отримати кращу оцінку часової складності і спрощують агента, який пересувається по графу, однак, накладають додаткові обмеження на відновлюваний граф.

Модифікація 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 Відновлення графа з використанням позначки одного типу

 

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

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. Розміщуємо агентів в довільні вершини 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. Ініціалізація лічильників.

2. АЕ дає команду для початку відновлення.

3. АІ встановлюються в різні один від одного випадкові вершини.

4. Поки АІ не зупинилися робимо перевірки..

5. Якщо вершина не розмічена і її кінцевий інцідентор не розфарбований, то розфарбовуємо вершину і кінцевий інцідентор. АІ відправляє повідомлення New vertex (нова вершина).

6. АЕ отримує координати знайденої вершини, і будує її.

7. АЕ посилає команду АІ Далі.

8. Якщо вершина розмічена, але не розфарбований кінцевий інцідентор, то АІ відправляє повідомлення Vertex (вершина, тобто не нова). АЕ дізнається координати вершини в яку відходить невідоме ребро і з'єднує ребром вершину з якої прийшов АІ з вершиною, до якої йшло невідоме ребро.

9. Якщо вершини розмічені і немає не розфарбованих кінцевих інціденторів, то АЕ відправляє команду АІ back (йти назад). Зробивши крок назад АІ знову проводить пошук нерозмічених ребер або вершин.

10. Якщо один з АІ прийшов в початок, а інший АІ продовжує шлях вперед, то проводиться команда перекидання у вільну вершину з нерозміченою 2-околицею.

11. Якщо один з АІ прийшов в початок, а інший АІ йде назад, то АІ завершує свою роботу.

12. Якщо один з АІ прийшов в початок, а інший АІ завершив свою роботу, то АІ перший також завершує свою роботу.

Аналіз результатів

 

Висновки

 

Проведено огляд та аналіз існуючих алгоритмів з відновлення графів. Вивчено основні визначення та поняття.

Запропонована модифікація для алгоритму відновлення неорієнтованого зв'язного графа без петель та кратних ребер колективом агентів (двома агентами дослідниками та агентом експериментатором).

Проведена оцінка складності базового алгоритму та алгоритму з модифікаціями. Збільшена комунікаційна складність, за рахунок запиту координат агентів дослідників для агента експериментатора з метою розпізнати перешийки, що сильно не вплинуло на швидкість виконання процесу відновлення графа, так як запити координат виконує АЕ, у якого необмежена пам'ять.

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

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

2. Ємкісна складність визначається розміром списків вершин кольору 1 і кольору 2. АІ використовують 1 колір, розмічаючи 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/Глоссарий_теории_графов