Труды ИПММ НАН Украины. 2008. Том 16

УДК 519.7

С.В. Сапунов

О методе построения отношения неотличимости помеченных графов

Аннотация

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

Введение. Основной проблемой теоретической кибернетики является проблема взаимодействия управляющей и управляемой систем (управляющего автомата и его операционной среды) [1,2]. Взаимодействие таких систем зачастую представляется как процесс перемещения автомата по помеченному графу или лабиринту среды. Та­кое представление интенсивно развивается в работах В.Б. Кудрявцева и его школы [3]. Одной из центральных и актуальных как в теоретическом, так и в прикладном аспектах проблем, возникающих при исследованиях взаимодействия автоматов и графов, является проблема анализа или распознавания свойств графа при различ­ной априорной информации и при различных способах взаимодействия автомата и графа. Один из подходов к решению проблемы анализа графа операционной среды основывается на том, что операционная среда рассматривается как неориентирован­ный граф с помеченными вершинами. Такие графы возникли первоначально как блок-схемы и схемы программ, а в настоящее время находят применение в задачах навигации роботов [4]. В монографии Ю.В. Капитоновой и А.А. Летичевского [2] с вершинами таких графов естественным образом связаны языки в алфавите меток вершин и показано, что эти языки регулярны и не содержат пустого слова.

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

1. Постановка задачи

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

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

В [6] введено понятие графов, детерминированных по разметке окрестностей вершин, (D-графы) и показано, что верхняя оценка длин траекторий, различаю­щих вершины такого графа, линейна. В настоящей работе рассматривается задача различения вершин произвольного помеченного графа.

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

Конечным ориентированным графом с помеченны­ми вершинами (помеченным орграфом) назовем четверку G = (G,E (G), М,L), где G - конечное множество вершин, |G| = п, Е (G) С GxG – конечное множество ребер, М – конечное множество меток, \М\ = m, j-g : G —>¦ М – сюръективная функция разметки. Последовательность меток вершин w = h (dg)... h (dg), соответствую­щую некоторому пути d.. .dк в графе Q, назовем словом длины к, порожденным вершиной d. Обозначим через множество всех непустых слов в алфавите М. Языком Lg вершины д назовем множество всех слов, порожденных этой вершиной. С каждым помеченным орграфом Q свяжем две характеристики Lg = IJ Lg (язык gee графа) и lc = {Lg}geG (семейство языков вершин графа). Введем частичную опе­рацию * : соотношением: для любой вершин  d   G и любого слова w G М+ через g-kw обозначим множество всех вершин h G G таких, что существует путь из д в h, помеченный словом w. Для слов u,w G М+ введем их композицию uow равную uw1, если и = и'х, w = xw', х G М, и не определено в противном случае. Множеством преемников Г – вершины д орграфа Q называется множество вер­шин, являющихся концами дуг, исходящих из д. Открытой окрестностью Од верши­ны д неорграфа Q называется множество всех смежных с ней вершин. Чере обозначим множество Од U d. Помеченный орграф Q назовем детерминированным орграфом или D-орграфом, если для любой вершины д е G и любых вершин s,t G Г~ из s = t следует, что g = (i(t)). В противном случае Q назовем ND-орграфом. Простой D-орграф Q, для которого выполняются следующие ограничения: (1) для любых вершин g,h G G если (g,h) G E(G), то (h,g) G E(G); (2) для любой вершины d любых вершин s, t G 0(fl) из s = t следует, что i(s) = i(t), назовем сильно детерминированным или SD-графом. Сравнение языков вершин приводит к следующим отношениям на множестве вершин помеченного графа.

Будем говорить, что вершина h G G покрывает вершину д G G и писать (g,h) G х, если Lg С Lfc. Отношение х рефлексивно, транзитивно, но в общем случае не антисимметрично и, таким образом, является предпорядком. Обозначим через хк отношение fc-покрытия: (g,h) G х, если Lkg С Lk, где L^ и Lkh обозначают подъязыки соответствующих языков, состоящие из слов, длина которых не превос­ходит некоторого натурального к. Будем говорить, что вершины g,h G G неотличимы  G е, ес­ли Lg = Lh. Отношение е рефлексивно, симметрично и транзитивно, т.е. являет­ся эквивалентностью. Ясно, что е = х П х~1. Обозначим через Sk отношение к-неотличимости: (d, К) G Ai если iA = L. Пример  показывает, что покрытие одной вершины другой и неотличи­мость вершин в общем случае не влекут за собой соответствующие отношения меж­ду их одинаково помеченными вершинами-преемниками. Действительно, вершины d и d$ неотличимы (а, следовательно, (d, h) G х), но любая пара их преемников отличима и не сравнима по х. Этим отношение е отличается от соответствующего отношения эквивалентности состояний детерминированных автоматов.

Через Ei обозначим последовательность отношений е1 е2, ... . Она монотонно убывает.

Говорят, что Ei стабилизируется на к-ом шаге, если из е^ = Kк+1 всегда следует k = 1. Пример  показывает, что равенство не всегда влечет стабилизацию I, поскольку е2 = е3, но е3 = е4. Действительно, обозначим через ттк разбиение множества вершин на классы эквивалентности. Тогда, tg = {{1,12}, {2, 3,13,14}, {4,15}, {5,17}, {6,16}, {7,18}, {8,19}, {9, 20}, {10, 21}, {11, 22}}, тг2 = {{1,12}, {2}, {3}, {13}, {14}, {4,15}, {5}, {17}, {6}, {16}, {7,18}, {8,19}, {9,20}, {10,21}, {11,22}}, tgz =tg2, 7g4 = {{1}, {12}, {2}, {3}, {13}, {14}, {4,15}, {5}, {17}, {6}, {16}, {7,18}, {8,19}, {9,20}, {10,21}, {11,22}}.

Этим свойством отношение fc-неотличимости вершин помеченного графа отли­чаются от аналогичного отношения на состояниях конечного, детерминированного автомата [7]. Заметим, что пример  показывает также, что в общем случае равенство u = u+1 не всегда влечет за собой стабилизацию монотонно убывающей последова­тельности x1x 3 Х2. Однако, далее будет показано, что начиная с некоторого к стабилизация всегда происходит.

3. Граф пар

Kаждому графу Q = (G,E(G),M, fig) поставим в соответствие граф пар V{G) = (D,E(D), M, fiv), построенный следующим образом. Сначала определим множество D1 по правилу: (S,Q) G D1 точно тогда, когда S,Q G 2G, SUQ^0 и fig(SuQ) = l. При этом полагаем, что fiv (S, Q) = fig (S U Q). 

Затем множество D1 пополним m экземплярами пар (0,0), при этом их метки попарно различны. Полученное семейство пар образует ”множество” вершин D графа пар. Из вершины (S,Q) с меткой х исходит дуга в вершину (S',Q') с меткой у точно тогда, когда S' = S -кху и Q' = Q-к ху.

Из правил построения графа T>(G) следует, что:

1) множество меток его вершин равно М;

2) fiv является сюръективной функцией;

3) из каждой его вершины (S, Q) исходит ровно m дуг;

4) из любой его вершины вида (S, S) достижимы только вершины вида (S', S'). Имеет место следующее простое, полезное в дальнейшем, утверждение, устанав­ливающее основные свойства графа пар.

Утверждение 1. Пусть V(G) является графом пар произвольного помеченного графа д, тогда:

1) \D\=0{rrn);

2) если из вершины (S, Q) с меткой ж исходят дуги в вершину (S', Q') с меткой у и в вершину (S", Q") с меткой z, то у ф z;

3) для любой вершины (S, Q) G D и любого слова w e M+ существует не более чем один путь из этой вершины, помеченный этим словом;

4) если из вершины (S,Q) достижима вершина (S',Q') и S = 0 (Q = 0), то S' = 0 (Q' = 0).

Доказательство. Покажем справедливость свойства 1. Обозначим через щ чис­ло вершин графа Q с меткой ж* G М, где 1 ^ г ^ т. Ясно, что щ + ... + пт = п. Из определения графа пар следует, что число вершин графа T>(G) с меткой х% равно 22п. Тогда \D\ = 22™i + ... + 22п> < т22п = О (22п).

Свойства 2 и 4 непосредственно следуют из определения. Покажем справедли­вость свойства 3. Пусть d(w) = 1, тогда, по определению операции *, \(S,Q)*w\ ^ 1. Пусть d(w) = 2, тогда из свойства 2 следует, что \(S,Q) *w\ ^ 1. Таким образом, всякому слову w G М+ длины 1 или 2 соответствует не более чем один путь из вершины (S, Q). Так как любое слово w e M+ длины больше 2 можно единственным образом представить в виде композиции его двухбуквенных подслов, то тем самым доказана справедливость свойства 3.

Утверждение доказано. 

С целью упрощения графа пар проведем дополнительные построения. Выделим в нем подмножество Dj начальных вершин и подмножество Dp финальных вер­шин. Множество всех слов (быть может пустое), каждое из которых соответствует некоторому пути из вершины (S,Q) G Dj в какую-либо вершину (S',Q') G DF, назовем языком Lis^q вершины (S,Q). Через L-piG обозначим объединение язы­ков U L(S)Q), а через AV{G) – семейство языков {L(S,q) }(sQ)eD . Настроенным графом пар назовем тройку {VT{G),DI,DF), где D^Dp С Dx и VT{G) подграф графа V(G), порожденный всеми начальными вершинами, всеми финальными вер­шинами и всеми вершинами, через которые проходит хотя бы один путь из некото­рой начальной вершины в некоторую финальную. Из построения следует, что этот подграф содержит только вершины из D\. Заметим, что этот подграф аналогичен так называемому триму автомата [7]. Обозначим VT{G) = (DT, E (DT), fj,v, Mt), где Mp С М. Рассмотрим некоторые настроенные графы пар.

Если положить Dj = Dp = D, то справедливо

Доказательство. (1) Пусть д является произвольной вершиной графа Q и сло­во w G Lg. Из построения графа пар следует, что каждая его вершина, одна из компонент которой включает вершину д, порождает слово w, то есть Lg С L-jyiG.

Покажем, что выполняется обратное включение. Пусть w G LV{G), тогда w G L(S)Q) для некоторой вершины (S,Q) G Dx. Тогда, так как S ф 0 или Q ф 0, то существует вершина д G 5 U Q, для которой w G Lg.

Таким образом, LV(G) = Lg. (2) Из утверждения 1 следует, что вершина (G). Ни одна из вершин графа Q не порождает множество слов {da,db,dc}, которое порождает вершина

Если положить, что Dj состоит из одной вершины (7 = DF = (d, 0) | d е G}, получаем, что Lfl L/j = Lg UL/j для всех h f d, h G G. Пусть теперь в графе Q е1 = е, то есть все одинаково помеченные вершины составляют класс неотличимости. Тогда, если (S,Q)

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

4. Сравнение вершин

Следующее утверждение дает конструктивный крите­рий покрытия одной вершины помеченного орграфа другой.

Теорема 1. Пусть Q является помеченным орграфом, тогда к = кк для неко­торого к не превосходящего 2p.

Доказательство. Расширим отношение я на булеан 2G по правилу: (5, Q) G я*, если Ls С Lq, где S,Q G 2G. Отношение я* рефлексивно, симметрично и транзитивно, т.е. является эквивалентностью. Аналогично полагаем (S,Q) G я^, если L| С L* . Из определения отношения. Следует, что последовательность отношений я* монотонно убывает, то есть я\ Э я*2 Э ... Э я* Э ... Э я*. Покажем, что если для некоторого г последовательность х стабилизируется, то стабилизация сохраняется для всех к ^ г. Иными словами, нам надо показать, что из равенства я* = я*+1 следуют равенства я*+ 1 = я*+ 2 = ... = я*.

Покажем далее, что стабилизация последовательности я* наступает при неко­тором г ^ 22га, где п = \G\. Положим, что в настроенном графе пар (T>t(G), Dj, Dp) множество Dj состоит из всех вершин вида ({

1) все достижимые из вершины ({#}, {h}) финальные вершины имеют вид (0, Т), где Т G 2G, тогда ({д}, {h}) G я*;

2) все достижимые из вершины ({#}, {h}) финальные вершины имеют вид (5, 0), где 5 G 2G, тогда ({h}, {g}) G я*;

3) среди достижимых из вершины ({#}, {h})

4) из вершины ({#}, {h})

Таким образом, ({#}, {h}).

Следствие. Пусть Q является помеченным орграфом, тогда е = ек для неко­торого к не превосходящегo.

Эта теорема показывает, что для вычисления отношений покрытия и неотли­чимости на вершинах произвольного помеченного графа достаточно перебрать все слова длины i. Использованный при доказательстве теоремы метод анализа язы­ков вершин является модификацией известного в теории автоматов так называемого метода пар состояний. Модификация состоит в перене­сении метода предназначенного для орграфов с отмеченными дугами на орграфы с отмеченными вершинами.

Из результатов известной работы И. Штокмайера и А. Майера [10] следует, что, по-видимому, оценки из теоремы 1 не могут быть понижены.

Построение отношений к и е может быть выполнено с использованием настро­енного графа пар (T>p(G),Di, Dp) из теоремы 1. Для построения отношения я до­статочно для каждой начальной вершины настроенного графа пар найти все до­стижимые из нее финальные вершины. Для построения отношения е достаточно для каждой начальной вершины настроенного графа пар проверить достижима ли из нее какая-либо финальная вершина этого графа. Так как число начальных вер­шин не превосходит п2, то для таких построений достаточно (при использовании известных алгоритмов поиска на графе [11] О  шагов.

Фактор-граф Q/e графа Q по отношению е назовем приведенным графом, а опе­рацию перехода от Q к Q/е – приведением графа Q.

Алгоритм приведения произвольного помеченного орграфа Q состоит из следу­ющих этапов:

1) построим методом графа пар эквивалентное разбиение множества вершин гра­фа G;

2) объединим все вершины из одного класса эквивалентности и представим объ­единенные вершины одной вершиной, помеченной общей меткой класса;

3) из каждой группы дуг, имеющих общее начало и конец, вычеркнем все, кроме одной.

Полученный в результате граф будет графом Q/е.

Поскольку сложность построения отношения е методом графа пар как показа­но выше составляет О (п224п), а объединение вершин и вычеркивание кратных дуг выполняется за константное время, то алгоритм приведения произвольного поме­ченного графа требует не более О  шагов.

5. Сравнение графов

Охарактеризуем отношение р, то есть найдем условия, при которых (Q,TC) G р. Имеет место следующее очевидное утверждение.

Утверждение 3. Графы Q и ТС неотличимы тогда и только тогда, когда в каждом классе неотличимости е графа Q+TL находятся как вершины графа Q, так и вершины графа ТС. Для проверки неотличимости графов Q и ТС воспользуемся настроенным гра­фом пар (Т>т (G + Н) ,Dj,Dp), у которого множество Dj состоит из всех вершин ({g},{h}), где g,h? G -\- Н и д ^ h, а множество Dp состоит из всех вершин (S, Q) G D1, где S = 0 или Q = 0. Пусть N = \G\ + \Н\. Ясно, что \Dj\ = О (А2), а \DT\ = 0(2Ш). Определим сложность проверки неотличимости графов Q и П. В подразделе 2.1 показано, что построение отношения е на вершинах графа Q + ТС требует не более О (А2 x 2k). Проверка, находятся ли в каждом классе как вер­шин графа д, так и вершин графа ТС, требует не более А шагов. Таким образом, сложность проверки неотличимости графов Q и ТС составляет О (А2 x 2 ).

Охарактеризуем отношение г, то есть найдем условия, при которых (hh, ТС) G т.

Для этого воспользуемся настроенным графом пар (Т>т (G + Я), Dj, Dp), у которого множество Dj состоит из всех вершин (G*x,H *х), для всех х G М, а множество DF состоит из всех вершин (S, Q) G Бъ где S = 0 или Q = 0. Ясно, что при такой настройке \Dj\ = m, DT С Dx и \DT\ = О (24iV).

Имеет место следующее утверждение. Утверждение 4. Графы d и Н слабо неотличимы тогда и только тогда, когда в настроенном графе пар (VT (G + H),DIy DF) ни из одной начальной вершины не достижима ни одна финальная вершина.

Доказательство. Действительно, пусть (Q,H) G-t, то есть Lg f LH. Тогда суще­ствует, по крайней мере, одно слов w = Х\Х2 ¦ ¦ ¦ Xk такое, что w G Lg Ly. По утвер­ждению 1 существует единственный путь с меткой w из вершины (G*Xi,H*Xi) G D. Так как слово w не порождается одним из множеств G*X и H*X, то этот путь оканчивается в финальной вершине, достижимой из вершины (G*Xi,H*Xi) G  >1. Утверждение доказано.

Оценим сложность проверки слабой неотличимости графов G и Н. Пусть N = \G\ + \H\. Для проверки достижимости из некоторой начальной вершины графа пар хотя бы одной его финальной вершины достаточно (при использовании известных алгоритмов [10] О  шагов. Тогда для проверки слабой неотличимости графов Я и ТС достаточно О  шагов. Следующее утверждение устанавливает соотношение между р и т.

Теорема 2.

1) На множестве Я(М) р С г и обратное включение не выполня­ется.

2. На подмножестве всех связных SD-графов р = т.

Докажем вначале следующую

Лемма 1. Пусть Q является SB-графом, HcGugeG-H. ({g},H) e я* тогда и только тогда, когда существует heH такая, что (g, h) G х.

Заключение

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

1. Глушков В.М., Цейтлин Г.Е., Ющенко Е.Л. Алгебра. Языки. Программирование. – К.: Наукова думка, 1989. – 376с.

2. Капитонова Ю.В., Летичевский А.А. Математическая теория проектирования вычислитель­ных систем. – М.: Наука, 1988. – 296 с. 

3. Килибарда Г., Кудрявцев В.Б., Ушчумлич Щ. Независимые системы автоматов в лабиринтах // Дискретная математика. – 2003. – Т.15, вып.2. –– С.3–39.

4. Соколов СМ., Кондриков С.С, Богуславский А.А. Исследование графовых структур для ин­формационных систем мобильных роботов // Труды международной школы-семинара ”Адап­тивные роботы – 2004” (8–11 июня 2004 г.). – М .– С.Пб.: Международная лаборатория ”Сенсо­рика”, 2004. – С.58–60.

5. Кудрявцев В.Б., Алешин СВ., Подколзин А.С. Введение в теорию автоматов. – М.: Наука, 1985. – 320с. 

6. Сапунов СВ. Эквивалентность помеченных графов // Труды ИПММ НАНУ. – 2002, – т.7 – С.162–167. 

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

8. Eilenberg S. Automata, Languages and Machines. V. A. – Academic Press, NY,1974. – 451p. 

9. Грунский И.С Анализ поведения конечных автоматов. – Луганск: Изд-во Луганск. гос. пед. ун-та, 2003. – 318с. 

10. Stockmeyer I.J., Meyer A.R. Word problems requiring exponential time // Proceedings of the 5th annual ACM symposium on Theory of computing (Austin, Texas, United States, April 30 – May 02, 1973). – New York: ACM Press, 1973. – P.1–9. 

11. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. – М.: МЦНМО, 2001. – 960с.

                                                                               Ин-т прикл. математики и механики НАН Украины, Донецк Получено 20.04.08