ISSN 1683-4720 Труды ИПММ НАН Украины. 2010. Том 21

И.С. Грунский, С.В. Сапунов

Идентификация вершин помеченных графов

Аннотация

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

Ключевые слова: граф с помеченными вершинами, идентификатор вершины, диагностический эксперимент.

1 Введение

Развитие теории формальных языков и конечных автоматов вы­звало интерес к графам с помеченными элементами (вершинами, дугами, точками ”прикосновения” дуги к вершине и т.п.) [1,2]. Результаты исследований таких гра­фов получили широкий спектр приложений. В частности, графы с помеченными элементами (помеченные графы) оказались удобным средством для исследования топологических операционных сред мобильных агентов (роботов, поисковых про­грамм и т.п.)[3]. При планировании двигательного поведения мобильных агентов (МА) возникают три взаимосвязанные фундаментальные задачи: задача построе­ния модели неизвестной среды (exploration), задача определения положения робота в известной среде (robot selflocation) и задача проверки соответствия неизвестной среды и ее модели (карты) (map validation) [4]. Заметим, что эти задачи имеют соответствующие аналоги в теории автоматов [5].

Центральной из перечисленных задач является задача самолокализации, так как от ее решения зависит решение двух других задач. Состоит она в следующем: МА, обладая картой (помеченным графом) среды, должен установить соответствие меж­ду вершиной на карте и неизвестной ему априори областью среды, в которой он пер­воначально находился. При изучении задачи самолокализации возник ряд подходов, зависящих от того, какие элементы графа агент наблюдает и метки каких элементов он может изменить. В работах [3,4] рассматривается задача самолокализации МА, у которого операционная среда моделируется конечным неориентированным графом с помеченными концами ребер. МА, находясь в некоторой вершине графа, единствен­ным образом нумерует концы ребер, инцидентных этой вершине. МА не отличает вершины графа друг от друга. Если существует путь из одной вершины графа в другую его вершину, то он описывается как последовательность пар номеров попар­но смежных ребер. Авторы предлагают алгоритм определения начальной вершины известного n-вершинного графа за О (п5) шагов при условии, что робот использует один переносной маркер. Основная идея алгоритма состоит в построении 0(п2) ги­потез о начальной вершине и разметке инцидентных ей ребер. Далее, МА проверяет каждую гипотезу за время О п3. При этом он восстанавливает граф из начальной вершины, параллельно сравнивая восстановленную часть графа с известной ему мо­делью. Недостатком предложенных модели и алгоритма самолокализации является невозможность однозначного определения положения робота на графе с симметрией (нетривиальным автоморфизмом).

В данной работе в качестве топологической модели операционной среды рас­сматриваются конечные ориентированные графы. Вершины этих графов заранее помечены и эти метки агент не меняет. Такая модель возникает, например, при каче­ственной навигации МА (qualitative navigation) [8]. Основой такой навигации служат ориентиры, которые разбивают линиями действия, каждая из которых проходит че­рез два ориентира, операционную среду на выпуклые многоугольники, являющиеся областями информационной эквивалентности. Каждая такая область является, в свою очередь, вершиной скелетного графа, а общая сторона двух многоугольни­ков порождает ребро между соответствующими вершинами скелетного графа. Если каждой вершине сопоставить упорядоченную по углу наблюдения последователь­ность ориентиров, то получим неориентированный граф с помеченными вершинами.

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

Конечным ориентированным графом с помечен­ными вершинами (помеченным орграфом) назовем четверку G = (G,E (G) , М, цо), где G – конечное множество вершин, |G| = п, Е (G) CGxG- конечное множество ребер, М – алфавит меток, \М\, G – М – сюръективная функция разметки. Последовательность меток вершин w = fiG (gi) ¦ ¦ ¦ № Ы, соответствующую некото­рому пути t в графе G, назовем словом длины к, порожденным вершиной d1. Через d(w) обозначим длину слова w. Инверсией слова w =хг...хк назовем слово wrev = Хк ¦ ¦ ¦ Х\. Слово v называется подсловом слова w, если существуют слова и U2 (возможно пустые) такие, что w = U1VU2. Если U1 пусто, то слово v также назы­вается начальным отрезком или префиксом piek(w) слова w длины к, где к = d(v). Обозначим через М+ множество всех непустых слов в алфавите М. Пусть W С М+. Высотой W назовем наибольшую из длин, входящих в него слов, его кратностью – величину \W\, его объемом – сумму длин всех входящих в него слов.

Для слов u,w G М+ введем их композицию и о w равную uw', если и = и'х, w = xw1, х G М, и не определено в противном случае. Введем частичную операцию r: G х М+ —>¦ 2G соотношением: для любой вершины d G G и любого слова w G М+ через d w обозначим множество всех вершин h G G таких, что существует путь из д в h, помеченный словом w = [i (g) о w о ц (h)]. Распространим операцию на подмножества множества G естественным образом: если G' Q G, то G' * w = UgeG,(g*w).

Языком Lg вершины д назовем множество всех слов, порожденных этой верши­ной. Будем говорить, что вершины g,h G G неотличимы, т.е. (д, h) G е, если Lg = L^. Отношение е рефлексивно, симметрично и транзитивно, т.е. является отношением эквивалентности. Фактор-граф G/e графа G по отношению е назовем приведенным графом. Всякому множеству вершин G' С G поставим в соответствие множество слов.

Помеченный орграф G назовем детерминированным орграфом или D-орграфом,если для любой вершины d G и любых вершин s,t t Т,d из s ф t следует, что fi(s) b fi(t) (здесь Г~ обозначает множество всех вершин, являющихся концами дуг, исходящих из д). В противном случае G назовем ND-орграфом. В [9] показано, что оценка длины кратчайшего слова, различающего две вершины D-орграфа равна п – m + 1 и совпадает с верхней оценкой длины кратчайшего слова, различающего состояния конечного всюду определенного детерминированного автомата Мура [6]. Простой D-граф G назовем сильно детерминированным или SD-графом, если для него выполняются следующие ограничения: 1) для любых вершин g,h G G если (g,h) G E(G), то (h,g) G E(G); 2) для любой вершины д е G и любых вершин s,te .

3 Эксперименты с графами

Экспериментом с графом G относительно апри­орной информации I, цели С и средств S назовем процесс, состоящий из трех этапов: 1) построение теста Р С М+ на основе I и С; 2) получение мобильным агентом (МА) экспериментальных данных W на основе Р и S; 3) вывод заключений о свойствах графа на основе W и I. Априорная информация – это класс графов, к которому принадлежит G. Основное отличие экспериментов с графами от экспериментов с автоматами [5] состоит в методах и средствах S получения экспериментальных дан­ных, а именно, возможностях МА перемещаться по графу, воспринимать локальную информацию о вершинах и ставить в них дополнительные стираемые/нестираемые метки.

Эксперимент назовем диагностическим, если априори полностью известен граф G и МА установлен в произвольную начальную вершину этого графа, а целью яв­ляется определение этой вершины, то есть отличение этой вершины от всех других вершин. Допуская вольность речи, множество W будем также называть экспери­ментом и говорить, что эксперимент W порождается тестом Р.

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

Из определения эксперимента следует, что он осуществляется посредством про­хождения МА некоторого связанного с тестом Р множества путей по графу G из вершины д. Будем полагать, что, находясь в любой вершине h G G, МА воспри­нимает множество слов Ob+(h) = Мк П L^, где Мк С М+ является множеством всех слов длины не больше к в алфавите меток М, и вычисляет множество слов Оb~(К) = Мк – L/j = Мк — Оb+(b). При к = 1 полагаем, что МА воспринимает толь­ко метку текущей вершины. Таким образом, проходя путь dt...dt в графе G, МА воспринимает множество слов.

Пусть w G M+. Обозначим через 5g(w) множество всех путей из вершины д, ко­торые помечены словом w. По произвольному множеству Р С М+ и  G построим пару Wg = [W+, W-], где W+ = jwe[P] ОЪ+ 5g{w)) и W~ = jwe[P] Оb~ (tg(w)), а [Р] является замыканием множества Р по всем непустым начальным отрезкам слов из Р. Экспериментом W с графом G, порожденным тестом Р, назовем семейство {Wfl} „. Эксперимент W назовем диагностическим точно тогда, когда для любых вершин g,heG из дф!г вытекает Wg ф Wh, то есть W+ f W+ или W~ f W^. В этом случае тест Р также назовем диагностическим.

4 Идентификаторы вершин

Идентификатором вершины д eG назовем ко­нечное множество слов Wg С М+ такое, что для любой вершины h G G равенство Wg P Lg = Wg П L/j выполняется тогда и только тогда, когда д = h. Ясно, что всякий идентификатор Wg можно представить как объединение W+ U Wg- двух множеств W+ = Wg П Ьд и Wg~ = Wg – Lg. Идентификатор Wg будем позитивным, если W = 0 и негативным, если W^ = 0.называть Рассмотрим условия существования идентификаторов вершин D-графов.

Теорема 1.

Равносильны следующие утверждения:

1. Существует идентификатор вершины g eG.

2. Существует идентификатор вершины g eG высоты не больше n–t + 1 и кратности не больше п – 1.

3. е (d) = {d}.

Доказательство. Импликация 2 => 1 очевидна.

Покажем, что из утверждения 1 следует утверждение 3. Пусть Wg – идентифи­катор вершины д, h – некоторая вершина и h G е(d). Из последнего соотношения следует, что Lg = Lh и тогда Wg П Lg = Wg П Lh. По определению идентификатора д = h, то есть е(d) = {d}.

Покажем далее, что из утверждения 3 следует утверждение 2. Пусть G – {d} = {d...,gn-i}. Так каdк f = {}, то для любой вершины gh 1 < i < п–1, существует слово ил G Lg 0 Lg.. Пусть W = {wi,... ,wn-i). Очевидно, что для любой вершины Qi выполняется LgC\ W ф LgiC\ W, то есть W является идентификатором д. Ясно, что \W\ = п — 1. По [9] длина слова w% не превосходит п – т + 1.

Теорема доказана.

Рассмотрим алгоритм построения идентификаторов всех вершин произвольно­го D-графа G. Основная идея алгоритма состоит в построении последовательности 7g1,7g2,...,gTfc разбиений множества вершин G до тех пор, пока ttk = ttk+i. Одно­временно для каждого разбиения г = {К\, К2, ¦ ¦ ¦, Kr}, r ^ п, строится семейство {W\, W2, ¦ ¦ ¦, Wr} множеств слов в алфавите М так, что каждому классу Kj G TTi, 1 < j < г, соответствует множество Wj С М+. Финальному разбиению vrfc соответ­ствует семейство идентификаторов всех вершин графа G.

Алгоритм 1. Построение идентификаторов вершин

Вход. D-граф G = [G, Е, М, c)

Выход. Семейство {Wgi, ...,WgJ идентификаторов всех вершин графа G.

Метод.

1. Построим разбиение ty = {Хг,Х2,... ,Хт}, каждый класс которого состоит из всех одинаково помеченных вершин, то есть Х% = G -к Xi, где 1 ^ г ^ t, G М. Инициализируем множество АК активных классов и положим АК = tt1. С каждым классом Xi G тт\ свяжем множество слов Wxt и положим Wxt = {%i}.

2. Положим к = 1.

3. Положим TTfc+l = TTfc.

4. Если АК = 0 и 7Tfc = 7rfc+i, то финальное разбиение ттк = {КbК2,... ,КГ}, г ^ n, уже построено. Для каждого класса Ki g ttk, 1 ^ г ^ г, и для каждой вершины geKi положим Wg = WKi. Алгоритм прекращает работу.

5. Если АК = 0 и i, то положим к = к + 1. 

6. Если АК ф 0, то выберем класс В е АК и положим АК = АК \ В. 

7. Положим В' = 0, U' = 0, U" = 0. 8. Для каждой метки х G М такой, что существует вершина д y В, для которой выполняется g * /j (В) х = 0, положим U' = U' L) {х}.

9. Положим U" = M\ U'. 

10. Если j = 0, то перейдем к 16.

11. Выберем метку х G U' и положим U' = U'\ {х}.

12. Для каждой вершины j–B такой, что  (В) х = 0, положим b' = b'и{k}. 

13. Если В' = В и С/' f 0, то положим b' = 0 и возвратимся к 11.

14. Если b' = В и t = 0, то перейдем к 16.

15. Положим В" = В\ В', WB> = WBn = WB U {c (В) х} и перейдем к 23.

16. Если U" = 0, то возвратимся к 4. 

17. С каждой меткой х G С1" свяжем класс Кх такой, что х (k) = х, В (В) хg1 Кх f 0 и высота множества U1^ наименьшая из возможных. 

18. Выберем метку х G U", у которой высота WKx наименьшая, и положим U" = U1{x}.

19. Для каждой вершины d ,В такой, что d*c(В)х = Кх, положим В' = B'u{h}. 

20. Если В' = В и f= 0, то положим b' = 0 и возвратимся к 18.

21. Если В' = b и U" = 0, то возвратимся к 4.

22. Положим В" = В\В' WB, = WB» = WBUa (В) WK . 

23. Положим rfc+i = (7rfc+i \ b) U B' U Б" и возвратимся к 4. Анализ алгоритма 1 начнем со следующей теоремы.

Теорема 2. Алгоритм 1 строит семейство {Wg}g€G идентификаторов всех вершин произвольного D-графа G, для которых существует идентификатор.

Доказательство. Алгоритм останавливается тогда, когда все классы разбиения неактивны. Класс становится неактивным, если он не разделился на два подкласса. Поэтому алгоритм остановится, по крайне мере, после того, как будет получено разбиение, состоящее из одноэлементных классов.

Покажем, что финальное разбиение, построенное алгоритмом 3.1, является е-эквивалентным разбиением множества G. Пусть g,heG, c(d) = c{к) и {d, h) – е. То­гда существует кратчайшее слово wxy, где w G М*, х, у G М, такое, что wx G LgP\Lh и wxy G Lg ф L/j. Так как одна из вершин д * wxy или h * wxy не существует, то на некоторой итерации алгоритма 1 вершины g-kwx и h-kwx попадут в разные классы. Тогда на некоторой следующей итерации вершины д к w и hk w также попадут в разные классы. Далее, для любого к, К к < d(w), вершины gkWek{w) и hkWek{w) будут попадут в разные классы на соответствующих итерациях алгоритма. 

Покажем, что по окончании работы алгоритма будет получено семейство иден­тификаторов всех вершин графа G, то есть для любой вершины д <Е G множество слов Wg является ее идентификатором. Пусть g,heG. Если fi(h), то по по­строению WgDLg ф WgnLh, так как WgC\Lg и WgC\Lh = 0. Пусть fd = fj(h). Если д и h принадлежат одному и тому же классу е-неотличимости, то Wg = Wh по построению и, следовательно, Lg П Wg = Lh П Wg. Пусть fi(g) = fi(h) и вершины д и h принадлежат разным классам е-неотличимости. Покажем, что существует слово w G Wg П Wh такое, что w G Lg ф Lh. Пусть вершины д и h принадлежат одному и тому же классу X разбиения ттк–1 и /л (X) = х. Пусть, далее, при построении разби­ения7Tfc класс X разбивается на два подкласса X' и X" такие, что д G X',he X". Тогда для некоторой метки у G М или (1) д-кху = 0 и h-kxy ф 0, или (2) существует класс У G ттк такой, что j, (У) = у, d* ху eY' и h* xy

Таким образом, алгоритм 1 правильно строит идентификаторы всех вершин произвольного D-графа G. Оценку сложности алгоритма 1 и сложности идентификаторов, построенных при его помощи дает следующая теорема.

Теорема 3. Алгоритм 1 за время О (n2 + n3) для каждой вершины g eG строит идентификатор Wg, высота и кратность которого равны 0(п).

Доказательство. В наихудшем случае на каждой итерации алгоритма 1 в от­дельный класс отделяется только одна вершина. Тогда, с учетом того, что первона­чальное разбиение состоит из т классов, количество итераций ограничено сверху числом n.

Первоначально в каждом из множеств слов, порождаемых алгоритмом, нахо­дятся слова длины 1. На каждой итерации алгоритма максимальная длина слова среди всех слов, находящихся в этих множествах, увеличивается на 1. Таким обра­зом, по окончании работы алгоритма, высота построенных им идентификаторов не превосходит п – т + 1.

Вернемся к рассмотрению наихудшего случая. Если на каждой итерации алго­ритма отделяется ровно одна вершина, то множество слов, ассоциированное с еще неразличенными вершинами увеличивается на одно слово. Так как количество вер­шин в одном блоке не превосходит п – т + 1, то в указанном множестве может находиться не более п – т + 1 слов. Следовательно кратность построенных алгорит­мом 3.1. идентификаторов не превосходит п – т + 1.

Наиболее трудоемкой частью каждой из итераций алгоритма 1 является объ­единение множеств слов. Для объединения двух множеств слов кратностью 0(n), высотой О(n) и алфавитом мощности т достаточно воспользоваться алгоритмом лексикографической сортировки [7]. Сложность сортировки с такими параметрами равна Э(т–п + п2)Таким образом, сложность построения идентификаторов всех вершин графа С, с учетом верхней оценки числа итераций алгоритма 3.1., равна 0(т–п2+п3).

5 Диагностический эксперимент

апомним, что эксперимент с графом С называется диагностическим, если априори полностью известен граф С и МА уста­новлен в произвольную неизвестную ему вершину g этого графа, а целью экспери­мента является определение этой вершины, то есть отличение вершины g от всех других вершин. Из определения эксперимента следует, что он осуществляется по­средством прохождения МА некоторого связанного с тестом Р множества путей по графу С из вершины д. Очевидно, что если граф С не приведен, то диагностический эксперимент с ним невозможен. Действительно, если (g,h) G е, то вершины g,h G G по определению неотличимы никаким словом из М+ . Если граф С приведен, то, как показано в раз­деле 2, существует к такое, что Lkg ф L1 для всех д ф h, g,h G G. Тогда Р = U9eG ^g является диагностическим тестом для Q, поскольку порожденный Р эксперимент W является диагностическим экспериментом с графом С, так как W Г\bdf WDLh, то есть Wg ф Wh для всех f h. Поэтому в дальнейшем, если не оговорено противное, будем считать, что все рассматриваемые графы приведены.

Следующая теорема описывает класс диагностических тестов, определяемых идентификаторами вершин графа С. Рассмотрим множество слов Р = JgeGWg,где Wg является некоторым идентификатором вершины д е G. Очевидно, что для любых различных вершин g,h

Теорема 4. Множество слов Р=Jg€G Wg является диагностическим тестом для графа G при любом семействе идентификаторов {Wg}g€G.

Эта теорема дает метод построения диагностических тестов для помеченных графов различных типов. Опишем подробно каждый этап диагностического эксперимента.

Алгоритм 2. Диагностический эксперимент (стратегия 1)

Вход. Приведенный D-граф G = (G,E,M,[i).

Семейство {W9l, ...,Wgn} идентификаторов всех вершин графа G. МА установлен в неизвестную ему вершину h G G.

Выход. Разбиение тг {h) теста Р на два класса Р+ = Р П Lh и Р^ = Р - Lh.

Метод.

1. Положим Р+ = 0, Р~ = 0, Р' = 0, Р" = 0. 

2. Считать метку c (h) вершины h.

3. Для каждого слова w G Р, начинающегося с /l (h), положим Р' = Р' U {w}. 

4. Положим Р~ = Р1{Р'}. 

5. Если Р' = 0, то положим Р+ = 0 и Р" = Р. Алгоритм прекращает работу.

6. Если Р' ф 0, то выберем слово w G Р' и положим Р' = Р' 1 {w}. Иначе алгоритм прекращает работу.

7. Положим г = 1.

8. Положим Wi = рге*(ги).

9. Если г = d (w), то положим Р+ = Р+ U {w}. Перейти к п. 6.

10. Перейти в вершину h* lc. 

11. Вычислить С = Ob' (h*Wi). 

12. Для каждого слова и G Р' такого, что и является начальным отрезком какого-либо слова из С, положим Р^ = Р^ U {и} и Р' = Р' \ {i}. 

13. Если wi+i G С, то положим Р^ = Р^ U {u}. Перейти к п. 6. 14. Положим г = г + 1. Перейти к п. 8. Рассмотрим свойства алгоритма 2.

Теорема 5. Алгоритм 2 строит разбиение диагностического теста Р на два класса за О (n3) шагов.

Доказательство. Поскольку при каждой итерации цикла из Р' удаляется, по крайней мере, одно слово, то этот алгоритм всегда завершается и при Р' = 0 полу­чаем разбиение теста Р на два класса Р^ и Р^ . В наихудшем случае алгоритм построения 7г(г1) требует проверки всех слов из Р. Следовательно, сложность такого построения равна объему Р, то есть равна О (n3).

На данном этапе уже могут быть сделаны заключения об операционной высо­те и кратности диагностического эксперимента. Поскольку, в общем случае, тест Р кратный, то при выполнении второго этапа эксперимента предполагается, что или МА перед началом анализа слова w G Р' переносится экспериментатором в начальную вершину h, или в h помещается новый экземпляр МА. Таким образом, для теста Р кратности к и данной стратегии проведения диагностического экспери­мента операционная кратность диагностического эксперимента не превосходит к, а операционная высота диагностического эксперимента равна высоте теста Р.

На третьем этапе эксперимента определяется начальная вершина путем анализа экспериментальных данных. Для теста Р с каждой вершиной g - G свяжем его разбиение тг(#) на два класса Р+ = g Р~ =P–Lg. Ясно, что для построения семейства {ir(g)}geG таких разбиений достаточно О (п4) шага. Далее, построенное экспериментально разбиение n(h) сравнивается со всеми разбиениями из семейства {7r(g)} eG. Если для некоторого n(d) выполняется tt(d) = 7г(u1), то д = h и экспери­мент окончен. Из правил построения семейства {ir(g)}geG и разбиения n(h) следует, что последнее равенство всегда достигается. Из описания алгоритма построения разбиения 7г(ul) и правила вывода заключения непосредственно следует, что дей­ствительная начальная вершина h всегда будет определена правильно.

Во второй стратегии процесс получения экспериментальных данных заключа­ется в том, что МА, стартуя из неизвестной ему вершины h графа G, проверяет наличие/отсутствие в G путей, помеченных теми же словами, что и пути из корня дерева Т (Р^пл) во все выделенные вершины этого дерева. В зависимости от исхода каждой из таких проверок уменьшаются подмножества вершин графа G, связан­ные с выделенными вершинами дерева Т (Pat). По окончании работы алгоритма множество С^пл содержит единственную вершину, которая и является искомой на­чальной вершиной графа G. Таким образом, вторая стратегия объединяет этапы получения экспериментальных данных и вывода заключений.

Алгоритм 3. Диагностический эксперимент (стратегия 2)

Вход. 

D-граф G = {G, Е, М, /л). Лес F (Р) корневых деревьев. МА установлен в неизвестную ему вершину h G G. Выход. Множество G^y 

Метод. 

1. Считать метку c (г1) вершины h.

2. Выберем из леса F (Р) дерево Т (P^h)). 

3. Если G1^{h} = 1, то вершина h уже определена. Алгоритм прекращает работу.

4. Выберем выделенную вершину s = t^{h}*w и положим  {s}.

5. Положим г = 1. 6. Положим Wi = рге*(ri).

7. Если переход из вершины h в вершину h-kWi графа G невозможен, то перейти к п. 8, иначе перейти к п. 9.

8. Для каждой вершины t G T^{h) положим G (t) = G (t)\G (s), G (t) = G (t)\G (s) и GKh) = GKh) \G(s). Перейти к п. 3.

9. Если г = d (ri), то для каждой вершины t G T^{h) положим G (t) = G (t)nG (s), G(t) = G it) \ G(s), G^{h) =G(s). Перейти к п. 3.      10. Положим г – г + 1. Перейти к п. 6. Анализ алгоритма 3 начнем со следующей теоремы.

Теорема 6. По окончании работы алгоритма 4.2 множество G^{h) всегда со­держит единственную вершину.

Доказательство. Предположим, что после некоторой итерации алгоритма G>(m > 1 )и Тх = 0, то есть условие окончания алгоритма не достигнуто, но дальнейшее его выполнение невозможно. Пусть G^m = {h} U G', где h g- G'. Из построения теста (Path) следует, что для любой вершины д - G' существует слово w G Pu(l1) такое, что w G LhLg. Тогда вершина s = t^{h)-kw является выделенной вершиной дерева Т (Р^n) и, либо h e G (s) и д е G(s), либо наоборот j e G(s) и Л,  G(s). Так как Т^m = 0, то вершина s была удалена из Т^пл в ходе неко­торой итерации алгоритма. Рассмотрим как могло произойти такое удаление. Если вершина s была удалена из Т^пл по причине того, что G(s) = 0, то на этой же итерации либо вершина h, либо вершина д была удалена из Gwm, что невозможно. Следовательно, на этой итерации МА побывал в вершине s и по этой причине эта вершина была удалена из T^h. Тогда на этой же итерации либо вершина h, либо вершина д была удалена из G^m, что невозможно. Из проведенных рассуждений следует, что при Т^pl = 0 выполняется С^pl = {h}.

В наихудшем случае на каждой итерации алгоритма из С^pl удаляется одна вершина. Так как число вершин графа Q с меткой равной j,(h) не превосходит n – m + 1, то алгоритм оканчивает свою работу через не более чем n–m итераций.

6 Заключение

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

Литература

1. James A. Anderson. Automata Theory with Modern Applications. – Cambridge University Press, 2006. – 255 p. 

2. Edmund M. Clarke, Jr., Orna Grumberg, and Doron A. Peled. Model Checking. – The MIT Press, 1999. –  416 p.

3. Dudek G., Jenkin M. Computational Principles of Mobile Robotics. – Cambridge University Press, Cambridge, 2000. – 280 p.

4. Dudek G., Jenkin M., Milios E., Wilkes D. Map validation and Robot Self-Location in a Graph-Like World // Robotics and Autonomous Systems. – 1997. – Vol. 22, № 2. – P. 159–178. 

5. Zvi Kohavi. Switching and finite automata theory. – McGraw-Hill, New York, 1970. – 592 p. 

6. Мур Э.Ф. Умозрительные эксперименты с последовательностными машинами // Автоматы. – М.: ИЛ, 1956. – С. 179–210. 

7. Alfred V., John E. Hopcroft, Jeffrey D. Ullman. The design and analisys of computer algorithms. – Addison-Wesley, 1974, – 432 p. 

8. Levitt T., Lawton D.T. Qualitative navigation for mobile robot // Artificial Intelligence, 1990. – v. 40. – p. 306–360. 

9. Сапунов С.В. Контроль детерминированных графов // Труды ИПММ. – 2003. – в. 8. – С. 106–110.

I.S. Grunsky, S.V. Sapunov

Topological identifiers of vertices of vertex labeled graphs.

The self-location problem for mobile agent in the topological environment is considered. Environment is modeled by the vertex labeled graph. The agent can move by graph edges and observe labels of vertices. A finite sets of words over the vertex labels alphabet distinguishing a given vertex from other called vertex identifier is proposed. Existence conditions and complexity estimations for vertex identifiers are discovered and constructions methods are developed. Polynomial constructions and realizations methods for experiments detecting the vertex where the mobile agent start walking based on all vertices’ identifiers construction are proposed.

Keywords: vertex labeled graph, vertex identifier, distinguishing experiment.

I.С. Грунський, С.В. Сапунов

Топологiчнi iдентифiкатори вершин позначених графiв.

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

Ключовi слова: графи з позначеними вершинами, iдентифiкатор вершини, дiагностичний експеримент.

                                  

                                      

                                                                                                                                                                       Получено 25.11.10