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

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

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

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

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

Рассмотрена задача построения автономным мобильным роботом топологической модели своей операционной среды. Модель среды представляет собой связный неориентированный граф с помеченными вершинами. Предложен полиномиальный алгоритм восстановления и разметки графа среды для коллектива из робота-супервизора и робота-исследователя.

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

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

Роботу присвячено дослідженню представлення графів з розміченими вершинами множинами слів у алфавіті міток вершин та пошуку метричних властивостей цього представлення. Графи з розміченими вершинами широко використовуються для описання та моделювання обчислювальних процесів у програмуванні, робототехніці, перевірці моделей тощо. При цьому графи відіграють роль інформаційного середовища для одного або декількох мобільних агентів. Переміщення агентів по графу визначають послідовності міток вершин - слова в алфавіті міток. Граф з розміченими вершинами називається Д-графом, якщо в околі кожної його вершини всі інші вершини мають попарно різні мітки. Для Д-графів у випадку, коли відомі карта графа (тобто множини вершин і ребер та функція розмітки) та ініціальна вершина, з якої агенти починають свої переміщення, існує однозначна відповідність між послідовністю міток вершин, які відвідує агент, і траєкторією переміщень цього агента на графі. У випадку, коли зовнішньому спостерігачу невідома карта досліджуваного Д-графа, переміщення агентів можуть бути організовані в такий спосіб, щоб на основі їх аналізу спостерігач одержав шукану інформацію щодо структури графа (наприклад, карту графа, найкоротші шляхи між вершинами, порівняння досліджуваного графа з графом-еталоном). У даній роботі уточнено представлення Д-графів так званою визначальною парою множин слів. Перша компонента цієї пари описує цикли графа, друга - його висячі вершини. Це представлення є аналогом системи визначальних співвідношень для повністю визначених автоматів. Також розглянуто структуру мінімальної за кількістю слів так званої канонічної визначальної пари та наведено алгоритм її побудови. Для детермінованого графа із заданою кількістю вершин і ребер знайдено точну оцінку кількості слів у першій компоненті його канонічної визначальної пари та мінімальні й максимальні досяжні оцінки кількості слів у другій компоненті канонічної визначальної пари. Результати надають змогу створювати та використовувати нові методи й алгоритми для розв'язання задач аналізу графів з розміченими вершинами.