Deterministic labelling of graph vertices by walking agent.pdf Рассматривается задача разметки вершин конечного простого связного неорграфапосредством блуждающего по нему агента. Разметка производится за один проходтак, что в окрестности каждой вершины все вершины размечены разными метками.Размеченные таким способом графы (помеченные графы) могут быть использованыв качестве топологических моделей операционной среды мобильных роботов [1].Помеченным графом будем называть конечный простой связный неорграф с по-меченными вершинами G = (V, E,M, где V - множество вершин; E - множестворебер; M - множество меток вершин; ^ : V ^ M - сюръективная функция раз-метки. Путем длины к в графе G будем называть последовательность его вершинp = g 1 , . . . , gk, такую, что (gi, gi + 1 ) Е E, i = 1 , . . . , k - 1. Меткой ^(p) пути p, определя-емой вершиной g1, назовём слово w = ^ (g1) . . . ^ (gk). Обозначим через Lg множествовсех слов w Е M +, определяемых вершиной g. Введём операцию * : V х M + ^ 2V: длялюбой g Е V и любого w Е M + через g*w обозначим множество всех вершин h Е V, та-ких, что существует путь p из g в h и ^(p) = w. Множество всех вершин, находящихсяот g на расстоянии не больше к, назовём к-окрестностью rgk) вершины g Е V.Мобильный агент A, находясь в вершине g Е V, наблюдает метки всех вершиниз rgk), к ^ 2. Положим, что наименьшим наблюдением, необходимым для мобиль-ности агента, является наблюдение rg2). Основываясь на анализе «увиденного», агентпринимает решение о перемещении между смежными вершинами. Агент может заме-нить метку вершины другой меткой из M. Агент также может устанавливать в те-кущей вершине переносной маркер (камень) или подбирать его. Через A2 обозначимагента, наблюдающего только rg2); через A3 - агента, наблюдающего только rg3).Функцию разметки ^ назовём детерминированной (или Д-разметкой), если длялюбой g Е V и любых s, t Е rg2) из s = t следует ^(s) = ^(t). Граф с Д-разметкой будемназывать детерминированным, или Д-графом. Далее всюду используются Д-графы.В таких графах для любой вершины g Е V и любого слова w Е M+ выполняется|g*w| ^ 1, где |g*w| = 1, если w Е , и |g*w| = 0 иначе. Показано, что агент A2,«зная» слово w Е , такое, что g*w = h, может переместиться из g в h. Таким образом,Д-разметка графа является достаточным условием для организации на нём навигациимобильных агентов. Показано далее, что для любых g, h Е V, g = h, ^(g) = ^(h), илюбого w Е П Lh расстояние между g * w и h * w не меньше 4, т. е. для того, чтобывыполнить Д-разметку вершин, необходимо наблюдение их 3-окрестностей.Задача построения Д-разметки формулируется следующим образом. Агент уста-навливается в произвольную вершину априори неизвестного ему графа, все вершиныкоторого помечены одной и той же меткой. Агент должен осуществить Д-разметкувершин этого графа, причём если вершина уже помечена агентом, то её метка в даль-нейшем не изменяется.Построение минимальной Д-разметки на основе только локальной информации овершинах графа представляется в общем случае невозможным. Поэтому в работе рас-сматривается построение «жадных» алгоритмов разметки. Показано, что с помощьюД-разметки агент может восстановить исследуемый граф с точностью до изоморфизмаи что минимальная Д-разметка восстановленного графа может быть получена при-менением к его транзитивному замыканию известных в теории графов алгоритмовправильной раскраски [2].Предложен метод Д-разметки вершин агентом A3, основанный на обходе графав ширину. При этом для неявного именования вершин используются метки путей в нихиз начальной вершины по дереву обхода. Разработан соответствующий полиномиаль-ный алгоритм.Увеличение размера наблюдаемой агентом окрестности (т. е. объёма его входнойинформации) приводит к увеличению сложности робота, который реализует функцииагента, поэтому целесообразно рассмотреть модель с ограничениями на размер наблю-дения.Предложена модификация алгоритма разметки для системы (A2,p^p2), состоящейиз агента A2 и камней двух видов: одного камня p1 для обозначения текущей вершиныи нескольких камней p2 для обозначения непомеченных вершин из её 2-окрестности.Число камней p2 не превышает максимальной степени вершин графа.Теорема 1. При решении задачи построения Д-разметки вершин помеченногографа агент A3 и система (A2,p1,p2) эквивалентны по вычислительной мощности.Для графов типа n-цепь, n-веер, n-угольник [2] разработана модификация алго-ритма разметки агентом A2 без использования камней и без запоминания неявныхимён вершин. Показано, что разметка n-цепи и n-угольника может быть выполненаконечным автоматом.

Скачать электронную версию публикации