Автор: Грунский И.С., Сапунов С.В.
Источник: Прикладная дискретная математика. Приложение. – 2012. – №5. – C. 89–91.
Грунский И.С., Сапунов С.В.Рассматривается задача разметки вершин конечного простого связного неорграфа посредством блуждающего по нему агента. Разметка производится за один проход так, что в окрестности каждой вершины все вершины размечены разными метками.
Рассматривается задача разметки вершин конечного простого связного неорграфа посредством блуждающего по нему агента. Разметка производится за один проход так, что в окрестности каждой вершины все вершины размечены разными метками. Размеченные таким способом графы (помеченные графы) могут быть использованы в качестве топологических моделей операционной среды мобильных роботов [1].
Помеченным графом будем называть конечный простой связный неорграф с помеченными вершинами G = (V, E, M, µ), где V – множество вершин; E – множество ребер; M – множество меток вершин; µ: V→M – сюръективная функция разметки. Путем длины k в графе G будем называть последовательность его вершин p = g1, . . . , 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+ через обозначим множество всех вершин h ∈V , таких, что существует путь p из g в h и µ(p) = w. Множество всех вершин, находящихся от g на расстоянии не больше k, назовём k-окрестностью (k) g вершины g ∈ V .
Мобильный агент A, находясь в вершине g ∈ V , наблюдает метки всех вершин из Г(g²), k > 2. Положим, что наименьшим наблюдением, необходимым для мобильности агента, является наблюдение Г(g²). Основываясь на анализе «увиденного», агент принимает решение о перемещении между смежными вершинами. Агент может заменить метку вершины другой меткой из M. Агент также может устанавливать в текущей вершине переносной маркер (камень) или подбирать его. Через A2 обозначим агента, наблюдающего только Г(g²); через A3 – агента, наблюдающего только Г(g³).
Функцию разметки µ назовём детерминированной (или Д-разметкой), если для любой g ∈ V и любых s, t ∈ Г(g²) g из s 6=t следует µ(s)6= µ(t). Граф с Д-разметкой будем называть детерминированным, или Д-графом. Далее всюду используются Д-графы. В таких графах для любой вершины g ∈ V и любого слова w ∈ M+ выполняется |g ∈ w| ≤ 1, где |g ∈ w| = 1, если w ∈ Lg, и |g ∈ w| = 0 иначе. Показано, что агент A2, «зная» слово w ∈ Lg, такое, что g∈w = h, может переместиться из g в h. Таким образом, Д-разметка графа является достаточным условием для организации на нём навигации мобильных агентов. Показано далее, что для любых g, h ∈ V , g ≠ h, µ(g) = µ(h), и любого w ∈ Lg ∩ Lh расстояние между g ∈ w и h ∈ w не меньше 4, т. е. для того, чтобы выполнить Д-разметку вершин, необходимо наблюдение их 3-окрестностей.
Задача построения Д-разметки формулируется следующим образом. Агент устанавливается в произвольную вершину априори неизвестного ему графа, все вершины которого помечены одной и той же меткой. Агент должен осуществить Д-разметку вершин этого графа, причём если вершина уже помечена агентом, то её метка в дальнейшем не изменяется
Построение минимальной Д-разметки на основе только локальной информации о вершинах графа представляется в общем случае невозможным. Поэтому в работе рассматривается построение «жадных» алгоритмов разметки. Показано, что с помощью Д-разметки агент может восстановить исследуемый граф с точностью до изоморфизма и что минимальная Д-разметка восстановленного графа может быть получена применением к его транзитивному замыканию известных в теории графов алгоритмов правильной раскраски [2].
Предложен метод Д-разметки вершин агентом A3, основанный на обходе графа в ширину. При этом для неявного именования вершин используются метки путей в них из начальной вершины по дереву обхода. Разработан соответствующий полиномиальный алгоритм.
Увеличение размера наблюдаемой агентом окрестности (т. е. объёма его входной информации) приводит к увеличению сложности робота, который реализует функции агента, поэтому целесообразно рассмотреть модель с ограничениями на размер наблю- дения.
Предложена модификация алгоритма разметки для системы (A2, p1, p2), состоящей из агента A2 и камней двух видов: одного камня p1 для обозначения текущей вершины и нескольких камней p2 для обозначения непомеченных вершин из её 2-окрестности. Число камней p2 не превышает максимальной степени вершин графа.
Теорема 1.При решении задачи построения Д-разметки вершин помеченного графа агент A3 и система (A2, p1, p2) эквивалентны по вычислительной мощности.
Для графов типа n-цепь, n-веер, n-угольник [2] разработана модификация алгоритма разметки агентом A2 без использования камней и без запоминания неявных имён вершин. Показано, что разметка n-цепи и n-угольника может быть выполнена конечным автоматом.
1. Dudek G. and Jenkin M. Computational Principles of Mobile Robotics. Cambridge: Cambridge
University Press, 2000.
2. Зыков А. А. Основы теории графов. М.: Вузовская книга, 2004.