О методе построения отношения неотличимости помеченных графов
Збережено в:
| Опубліковано в: : | Труды Института прикладной математики и механики НАН Украины |
|---|---|
| Дата: | 2008 |
| Автор: | |
| Формат: | Стаття |
| Мова: | Російська |
| Опубліковано: |
Інститут прикладної математики і механіки НАН України
2008
|
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/19997 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | О методе построения отношения неотличимости помеченных графов / С.В. Сапунов // Труды Института прикладной математики и механики НАН Украины. — Донецьк: ІПММ НАН України, 2008. — Т. 16. — С. 179-189. — Бібліогр.: 11 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859481680826335232 |
|---|---|
| author | Сапунов, С.В. |
| author_facet | Сапунов, С.В. |
| citation_txt | О методе построения отношения неотличимости помеченных графов / С.В. Сапунов // Труды Института прикладной математики и механики НАН Украины. — Донецьк: ІПММ НАН України, 2008. — Т. 16. — С. 179-189. — Бібліогр.: 11 назв. — рос. |
| collection | DSpace DC |
| container_title | Труды Института прикладной математики и механики НАН Украины |
| first_indexed | 2025-11-24T15:07:11Z |
| format | Article |
| fulltext |
ISSN 1683-4720 Труды ИПММ НАН Украины. 2008. Том 16
УДК 519.7
c©2008. С.В. Сапунов
О МЕТОДЕ ПОСТРОЕНИЯ ОТНОШЕНИЯ
НЕОТЛИЧИМОСТИ ПОМЕЧЕННЫХ ГРАФОВ
Рассматривается задача различения вершин графов с помеченными вершинами (помеченных гра-
фов) и самих таких графов путем сравнения языков в алфавите меток, связанных с вершинами.
Для анализа языков вершин разработан метод графа пар, представляющий собой модификацию из-
вестного в теории автоматов метода пар состояний. При помощи этого метода показано, что оценка
длины слова, различающего две вершины помеченного орграфа в общем случае экспоненциальна.
Далее, методом графа пар найдены конструктивные критерии нахождения помеченных графов в
отношениях неотличимости и слабой неотличимости, индуцированных сравнением объединений и
семейств языков их вершин.
Введение. Основной проблемой теоретической кибернетики является проблема
взаимодействия управляющей и управляемой систем (управляющего автомата и его
операционной среды) [1, 2]. Взаимодействие таких систем зачастую представляется
как процесс перемещения автомата по помеченному графу или лабиринту среды. Та-
кое представление интенсивно развивается в работах В.Б. Кудрявцева и его школы
[3]. Одной из центральных и актуальных как в теоретическом, так и в прикладном
аспектах проблем, возникающих при исследованиях взаимодействия автоматов и
графов, является проблема анализа или распознавания свойств графа при различ-
ной априорной информации и при различных способах взаимодействия автомата и
графа. Один из подходов к решению проблемы анализа графа операционной среды
основывается на том, что операционная среда рассматривается как неориентирован-
ный граф с помеченными вершинами. Такие графы возникли первоначально как
блок-схемы и схемы программ, а в настоящее время находят применение в задачах
навигации роботов [4]. В монографии Ю.В. Капитоновой и А.А. Летичевского [2] с
вершинами таких графов естественным образом связаны языки в алфавите меток
вершин и показано, что эти языки регулярны и не содержат пустого слова.
В настоящей работе рассматривается проблема анализа ориентированных и
неориентированных графов с помеченными вершинами. Объектом анализа графа
выбран язык, ассоциированный с вершиной, то есть множество всех последователь-
ностей меток, соответствующих путям, исходящим из этой вершины. Такое исследо-
вание актуально с теоретической точки зрения и постоянно стимулируется приклад-
ными задачами. Теоретическая актуальность определяется тем, что методы, анало-
гичные методам теории автоматов эффективно распространяются на графовые си-
стемы, не являющиеся конечными автоматами, но являющиеся в некотором смыс-
ле автоматоподобными системами. Прикладная актуальность определяется связью
проблем исследования таких графов с задачами навигации мобильных роботов.
1. Постановка задачи. Рассматривается задача различения вершин графов с
помеченными вершинами (помеченных графов) и самих таких графов путем сравне-
179
С.В. Сапунов
ния языков в алфавите меток, связанных с вершинами. По дугам графа от вершины
к вершине блуждает автомат. Находясь в вершине, автомат считывает ее метку и
метки смежных с ней вершин. Последовательности меток, связанные с траектори-
ями блуждания автомата, образуют слова в алфавите меток. С каждой вершиной
связывается ее язык, т.е. множество слов, связанных с траекториями, начинающи-
мися в этой вершине. Будем говорить, что вершины отличимы, если их языки раз-
личны. С каждым помеченным графом свяжем две характеристики – объединение
языков всех его вершин и семейство этих языков. Будем говорить, что графы отли-
чимы, если связанные с ними семейства языков вершин различны, и графы слабо
отличимы, если связанные с ними объединения языков вершин различны.
Как было указано выше, языки вершин регулярны. Сравнение регулярных язы-
ков обычно проводится путем построения и детерминизации соответствующих ко-
нечных автоматов и их анализа. Известно, что переход от недетерминированного
автомата к детерминированному дает достижимую экспоненциальную оценку роста
числа состояний (см., например, [5]). В данной работе предлагаются методы сравне-
ния языков вершин помеченных графов и характеристик самих графов, основанные
на анализе специального вида помеченных графов, построенных по исходным гра-
фам.
В [6] введено понятие графов, детерминированных по разметке окрестностей
вершин, (D-графы) и показано, что верхняя оценка длин траекторий, различаю-
щих вершины такого графа, линейна. В настоящей работе рассматривается задача
различения вершин произвольного помеченного графа.
2. Основные определения.Конечным ориентированным графом с помеченны-
ми вершинами (помеченным орграфом) назовем четверку G = (G,E (G) ,M, µG), где
G – конечное множество вершин, |G| = n, E (G) ⊆ G×G – конечное множество ребер,
M – конечное множество меток, |M | = m, µG : G → M – сюръективная функция
разметки. Последовательность меток вершин w = µG (g1) . . . µG (gk), соответствую-
щую некоторому пути g1 . . . gk в графе G, назовем словом длины k, порожденным
вершиной g1. Обозначим через M+ множество всех непустых слов в алфавите M .
Языком Lg вершины g назовем множество всех слов, порожденных этой вершиной.
С каждым помеченным орграфом G свяжем две характеристики LG =
⋃
g∈G
Lg (язык
графа) и ΛG = {Lg}g∈G (семейство языков вершин графа). Введем частичную опе-
рацию ? : G ×M+ → 2G соотношением: для любой вершины g ∈ G и любого слова
w ∈ M+ через g ?w обозначим множество всех вершин h ∈ G таких, что существует
путь из g в h, помеченный словом w. Для слов u,w ∈ M+ введем их композицию
u◦w равную uw′, если u = u′x, w = xw′, x ∈ M , и не определено в противном случае.
Множеством преемников Γ− вершины g орграфа G называется множество вер-
шин, являющихся концами дуг, исходящих из g. Открытой окрестностью Og верши-
ны g неорграфа G называется множество всех смежных с ней вершин. Через O(g)
обозначим множество Og ∪ {g}.
Помеченный орграф G назовем детерминированным орграфом или D-орграфом,
если для любой вершины g ∈ G и любых вершин s, t ∈ Γ−g из s 6= t следует, что
180
О методе построения отношения неотличимости помеченных графов
µ(s) 6= µ(t). В противном случае G назовем ND-орграфом.
Простой D-орграф G, для которого выполняются следующие ограничения: (1)
для любых вершин g, h ∈ G если (g, h) ∈ E(G), то (h, g) ∈ E(G); (2) для любой
вершины g ∈ G и любых вершин s, t ∈ O(g) из s 6= t следует, что µ(s) 6= µ(t), назовем
сильно детерминированным или SD-графом.
Сравнение языков вершин приводит к следующим отношениям на множестве
вершин помеченного графа.
Будем говорить, что вершина h ∈ G покрывает вершину g ∈ G и писать
(g, h) ∈ κ, если Lg ⊆ Lh. Отношение κ рефлексивно, транзитивно, но в общем
случае не антисимметрично и, таким образом, является предпорядком. Обозначим
через κk отношение k-покрытия: (g, h) ∈ κ, если Lk
g ⊆ Lk
h, где Lk
g и Lk
h обозначают
подъязыки соответствующих языков, состоящие из слов, длина которых не превос-
ходит некоторого натурального k.
Будем говорить, что вершины g, h ∈ G неотличимы и писать (g, h) ∈ ε, ес-
ли Lg = Lh. Отношение ε рефлексивно, симметрично и транзитивно, т.е. являет-
ся эквивалентностью. Ясно, что ε = κ ∩ κ−1. Обозначим через εk отношение k-
неотличимости: (g, h) ∈ εk, если Lk
g = Lk
h.
Пример на рис. 1 показывает, что покрытие одной вершины другой и неотличи-
мость вершин в общем случае не влекут за собой соответствующие отношения меж-
ду их одинаково помеченными вершинами-преемниками. Действительно, вершины
g1 и g8 неотличимы (а, следовательно, (g1, g8) ∈ κ), но любая пара их преемников
отличима и не сравнима по κ. Этим отношение ε отличается от соответствующего
отношения эквивалентности состояний детерминированных автоматов.
a a
bb b b
f fd deec c
1
2 3 9
8
10
4 5 6 7 1211 13 14
Рис. 1.
Через ε̃i обозначим последовательность отношений ε1, ε2, ... . Она монотонно
убывает, то есть ε1 ⊇ ε2 ⊇ . . . ⊇ εi ⊇ . . . ⊇ ε.
Говорят, что ε̃i стабилизируется на k-ом шаге, если из εk = εk+1 всегда следует
εk = ε. Пример на рисунке 2 показывает, что равенство εk = εk+1 не всегда влечет
стабилизацию ε̃, поскольку ε2 = ε3, но ε3 6= ε4. Действительно, обозначим через πk
разбиение множества вершин на классы εk-эквивалентности. Тогда, π1 = {{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}}, π3 = π2, π4 = {{1} , {12}, {2}, {3}, {13}, {14}, {4, 15}, {5}, {17},
{6}, {16}, {7, 18}, {8, 19}, {9, 20}, {10, 21}, {11, 22}}.
181
С.В. Сапунов
a a
bb b b
f fd deec c
j jh hi ig g
1
2 3
4 5 6 7
8 9 10 11
12
13 14
15 16 17 18
19 20 21 22
Рис. 2.
Этим свойством отношение k-неотличимости вершин помеченного графа отли-
чаются от аналогичного отношения на состояниях конечного, детерминированного
автомата [7].
Заметим, что пример на рис. 2 показывает также, что в общем случае равенство
κi = κi+1 не всегда влечет за собой стабилизацию монотонно убывающей последова-
тельности κ1 ⊇ κ2 ⊇ . . . ⊇ κi ⊇ . . . ⊇ κ. Однако, далее будет показано, что начиная
с некоторого k стабилизация всегда происходит.
Пусть G = (G, E(G), M, µG) и H = (H, E(H), M, µH) — произвольные графы
из K(M). Будем говорить, что граф G неотличим от графа H, если для любой вер-
шины g ∈ G существует вершина h ∈ H такая, что Lg = Lh. Будем говорить, что
графы G и H неотличимы и писать (G,H) ∈ ρ, если G неотличим от H и H неот-
личим от G. Из определения неотличимости графов следует, что (G,H) ∈ ρ тогда и
только тогда, когда ΛG = ΛH. Отношение ρ рефлексивно, симметрично, транзитив-
но и, таким образом, является эквивалентностью. Будем говорить, что графы G и
H слабо неотличимы и писать (G,H) ∈ τ , если LG = LH. Отношение τ рефлексивно,
симметрично, транзитивно и, таким образом, также является эквивалентностью.
3. Граф пар. Каждому графу G = (G, E(G),M, µG) поставим в соответствие
граф пар D(G) = (D, E(D),M, µD), построенный следующим образом. Сначала
определим множество D1 по правилу: (S, Q) ∈ D1 точно тогда, когда S, Q ∈ 2G,
S ∪Q 6= ∅ и |µG (S ∪Q)| = 1. При этом полагаем, что µD (S, Q) = µG (S ∪Q). Затем
множество D1 пополним m экземплярами пар (∅,∅), при этом их метки попарно
различны. Полученное семейство пар образует ”множество” вершин D графа пар.
Из вершины (S, Q) с меткой x исходит дуга в вершину (S′, Q′) с меткой y точно
тогда, когда S′ = S ? xy и Q′ = Q ? xy.
Из правил построения графа D(G) следует, что:
1) множество меток его вершин равно M ;
2) µD является сюръективной функцией;
3) из каждой его вершины (S, Q) исходит ровно m дуг;
4) из любой его вершины вида (S, S) достижимы только вершины вида (S′, S′).
Имеет место следующее простое, полезное в дальнейшем, утверждение, устанав-
ливающее основные свойства графа пар.
182
О методе построения отношения неотличимости помеченных графов
Утверждение 1. Пусть D(G) является графом пар произвольного помеченного
графа G, тогда:
1) |D| = O
(
22n
)
;
2) если из вершины (S,Q) с меткой x исходят дуги в вершину (S′, Q′) с меткой
y и в вершину (S′′, Q′′) с меткой z, то y 6= z;
3) для любой вершины (S,Q) ∈ D и любого слова w ∈ M+ существует не более
чем один путь из этой вершины, помеченный этим словом;
4) если из вершины (S,Q) достижима вершина (S′, Q′) и S = ∅ (Q = ∅), то
S′ = ∅ (Q′ = ∅).
Доказательство. Покажем справедливость свойства 1. Обозначим через ni чис-
ло вершин графа G с меткой xi ∈ M , где 1 6 i 6 m. Ясно, что n1 + . . . + nm = n. Из
определения графа пар следует, что число вершин графа D(G) с меткой xi равно
22ni . Тогда |D| = 22n1 + . . . + 22ni 6 m22n = O
(
22n
)
.
Свойства 2 и 4 непосредственно следуют из определения. Покажем справедли-
вость свойства 3.
Пусть d(w) = 1, тогда, по определению операции ?, |(S, Q) ? w| 6 1. Пусть
d(w) = 2, тогда из свойства 2 следует, что |(S,Q) ? w| 6 1. Таким образом, всякому
слову w ∈ M+ длины 1 или 2 соответствует не более чем один путь из вершины
(S, Q). Так как любое слово w ∈ M+ длины больше 2 можно единственным образом
представить в виде композиции его двухбуквенных подслов, то тем самым доказана
справедливость свойства 3.
Утверждение доказано. ¤
С целью упрощения графа пар проведем дополнительные построения. Выделим
в нем подмножество DI начальных вершин и подмножество DF финальных вер-
шин. Множество всех слов (быть может пустое), каждое из которых соответствует
некоторому пути из вершины (S, Q) ∈ DI в какую-либо вершину (S′, Q′) ∈ DF ,
назовем языком L(S,Q) вершины (S, Q). Через LD(G) обозначим объединение язы-
ков
⋃
(S,Q)∈DI
L(S,Q), а через ΛD(G) – семейство языков
{
L(S,Q)
}
(S,Q)∈DI
. Настроенным
графом пар назовем тройку (DT (G), DI , DF ), где DI , DF ⊆ D1 и DT (G) подграф
графа D(G), порожденный всеми начальными вершинами, всеми финальными вер-
шинами и всеми вершинами, через которые проходит хотя бы один путь из некото-
рой начальной вершины в некоторую финальную. Из построения следует, что этот
подграф содержит только вершины из D1. Заметим, что этот подграф аналогичен
так называемому триму автомата [7]. Обозначим DT (G) = (DT , E (DT ) , µD,Mt), где
MT ⊆ M . Рассмотрим некоторые настроенные графы пар.
Если положить DI = DF = D1, то справедливо
Утверждение 2. 1) LD(G) = LG ; 2) ΛG ⊆ ΛD(G).
Доказательство. (1) Пусть g является произвольной вершиной графа G и сло-
во w ∈ Lg. Из построения графа пар следует, что каждая его вершина, одна из
компонент которой включает вершину g, порождает слово w, то есть LG ⊆ LD(G).
Покажем, что выполняется обратное включение. Пусть w ∈ LD(G), тогда w ∈
L(S,Q) для некоторой вершины (S,Q) ∈ D1. Тогда, так как S 6= ∅ или Q 6= ∅, то
183
С.В. Сапунов
существует вершина g ∈ S ∪Q, для которой w ∈ Lg.
Таким образом, LD(G) = LG .
(2) Из утверждения 1 следует, что вершина ({g},∅) ∈ D порождает тот же язык,
что и вершина g ∈ G. Таким образом, ΛG ⊆ ΛD(G).
Покажем, что в общем случае ΛD(G) 6= ΛG . Рассмотрим граф G и фрагмент его
граф пар D(G) на рисунке 3. Ни одна из вершин графа G не порождает множество
слов {da, db, dc}, которое порождает вершина
(
4, 5, 6,∅
) ∈ D.
Утверждение доказано. ¤
1 2 3
4
5 6
d
d d
a b ñ
G
4,5,6, Æ4, Æ 5, Æ 6, Æ
1, Æ
4,6, Æ5,6, Æ
2, Æ 3, Æ
4,5, Æ
d d dd
d d d
a b ñ
D(G)
Рис. 3.
Если положить, что DI состоит из одной вершины ({g}, {h}), где Lg 6= Lh, а DF
состоит из всех вершин (S,Q) ∈ D1, у которых S = ∅ или Q = ∅, то L({g},{h}) =
Lg ⊕ Lh.
Если положить, что DI состоит из одной вершины ({g}, {g}), а DF из всех вершин
(S, S), то L({g},{g}) = Lg.
Рассмотрим вырожденные случаи. Пусть в графе G m = n, то есть все вершины
имеют попарно различные метки. Тогда в графе пар нет вершин (S, Q), где S 6= Q,
S 6= ∅ и Q 6= ∅, то есть он содержит не более n2 + m вершин. Полагая DI = DF =
{(g,∅) | g ∈ G}, получаем, что Lg⊕Lh = Lg∪Lh для всех h 6= g, h ∈ G. Пусть теперь
в графе G ε1 = ε, то есть все одинаково помеченные вершины составляют класс
неотличимости. Тогда, если (S, Q) ∈ D1, S 6= ∅ и Q 6= ∅, то S и Q включаются
в некоторый класс неотличимости. Полагая, что DI = {(S, Q) |S 6= ∅ ∧Q 6= ∅} и
DF = {(S′, Q′) |S′ = ∅ ∨Q′ = ∅}, получаем, что LD(G) = ∅ и настроенный граф пар
не содержит вершин, не входящих в DI ∪DF .
Проделанные рассуждения показывают, что настроенный соответствующим об-
разом граф пар позволяет анализировать языки вершин помеченных графов и ис-
следовать характеристики самих графов.
4. Сравнение вершин. Следующее утверждение дает конструктивный крите-
рий покрытия одной вершины помеченного орграфа другой.
Теорема 1. Пусть G является помеченным орграфом, тогда κ = κk для неко-
торого k не превосходящего 22n.
184
О методе построения отношения неотличимости помеченных графов
Доказательство. Расширим отношение κ на булеан 2G по правилу: (S,Q) ∈ κ∗,
если LS ⊆ LQ, где S, Q ∈ 2G. Отношение κ∗ рефлексивно, симметрично и тран-
зитивно, т.е. является эквивалентностью. Аналогично полагаем (S,Q) ∈ κ∗k, если
Lk
S ⊆ Lk
Q.
Из определения отношения κ∗k следует, что последовательность отношений κ̃∗i
монотонно убывает, то есть κ∗1 ⊇ κ∗2 ⊇ . . . ⊇ κ∗i ⊇ . . . ⊇ κ∗. Покажем, что если для
некоторого i последовательность κ̃∗i стабилизируется, то стабилизация сохраняется
для всех k > i. Иными словами, нам надо показать, что из равенства κ∗i = κ∗i+1
следуют равенства κ∗i+1 = κ∗i+2 = . . . = κ∗.
Пусть существуют множества вершин S, Q ∈ 2G такие, что (S,Q) ∈ κ∗i+1 и
(S, Q) 6∈ κ∗i+2. Тогда существуют метки x, y ∈ M и слово w ∈ M∗ такие, что слово
xyw ∈ LS − LQ и d(xyw) = i + 2. Пусть T = S ? xy и P = Q ? xy. Из (S, Q) ∈ κ∗i+1
и κ∗i = κ∗i+1 следует, что (T, P ) ∈ κ∗i+1. С другой стороны, слово yw ∈ LT − LP
и d(yw) = i + 1, то есть (T, P ) 6∈ κ∗i+1. Полученное противоречие доказывает, что
стабилизация последовательности κ̃∗i сохраняется.
Покажем далее, что стабилизация последовательности κ̃∗i наступает при неко-
тором i 6 22n, где n = |G|. Положим, что в настроенном графе пар
(DT (G), DI , DF ) множество DI состоит из всех вершин вида ({g}, {h}), где g 6= h, а
множество DF состоит из всех вершин (S, Q) ∈ D1, у которых S = ∅ или Q = ∅.
Легко видеть, что всякое слово из LD(G) различает некоторую пару вершин графа
G. Действительно, пусть слово w ∈ Lg − Lh, где g, h ∈ G, тогда по утверждению 1
существует единственный путь с меткой w из ({g}, {h}) ∈ DI . Так как w 6∈ Lh,
то этот путь оканчивается в некоторой финальной вершине (S,∅). Так как |DT | =
O
(
22n
)
, то длина кратчайшего пути из начальной вершины в финальную также
равна O
(
22n
)
. Возможен один из следующих вариантов:
1) все достижимые из вершины ({g}, {h}) финальные вершины имеют вид (∅, T ),
где T ∈ 2G, тогда ({g}, {h}) ∈ κ∗;
2) все достижимые из вершины ({g}, {h}) финальные вершины имеют вид (S,∅),
где S ∈ 2G, тогда ({h}, {g}) ∈ κ∗;
3) среди достижимых из вершины ({g}, {h}) финальных вершин есть вершины
вида (∅, T ) и вершины вида (S,∅), где S, T ∈ 2G, тогда {g} и {h} не сравнимы по
κ∗;
4) из вершины ({g}, {h}) не достижима ни одна финальная вершина, тогда
({g}, {h}) ∈ κ∗ и ({h}, {g}) ∈ κ∗.
Таким образом, ({g}, {h}) ∈ κ∗ тогда и только тогда, когда ({g}, {h}) ∈ κ∗k для
k 6 22n. Очевидное соотношение (g, h) ∈ κ ⇔ ({g}, {h}) ∈ κ∗ доказывает теорему. ¤
Следствие. Пусть G является помеченным орграфом, тогда ε = εk для неко-
торого k не превосходящего 22n.
Эта теорема показывает, что для вычисления отношений покрытия и неотли-
чимости на вершинах произвольного помеченного графа достаточно перебрать все
слова длины 22n. Использованный при доказательстве теоремы метод анализа язы-
ков вершин является модификацией известного в теории автоматов так называемого
185
С.В. Сапунов
метода пар состояний (см., например, [9], стр. 39). Модификация состоит в перене-
сении метода предназначенного для орграфов с отмеченными дугами на орграфы с
отмеченными вершинами.
Из результатов известной работы И. Штокмайера и А. Майера [10] следует, что,
по-видимому, оценки из теоремы 1 не могут быть понижены.
Построение отношений κ и ε может быть выполнено с использованием настро-
енного графа пар (DT (G), DI , DF ) из теоремы 1. Для построения отношения κ до-
статочно для каждой начальной вершины настроенного графа пар найти все до-
стижимые из нее финальные вершины. Для построения отношения ε достаточно
для каждой начальной вершины настроенного графа пар проверить достижима ли
из нее какая-либо финальная вершина этого графа. Так как число начальных вер-
шин не превосходит n2, то для таких построений достаточно (при использовании
известных алгоритмов поиска на графе [11] O
(
n224n
)
шагов.
Фактор-граф G/ε графа G по отношению ε назовем приведенным графом, а опе-
рацию перехода от G к G/ε – приведением графа G.
Алгоритм приведения произвольного помеченного орграфа G состоит из следу-
ющих этапов:
1) построим методом графа пар эквивалентное разбиение множества вершин гра-
фа G;
2) объединим все вершины из одного класса эквивалентности и представим объ-
единенные вершины одной вершиной, помеченной общей меткой класса;
3) из каждой группы дуг, имеющих общее начало и конец, вычеркнем все, кроме
одной.
Полученный в результате граф будет графом G/ε.
Поскольку сложность построения отношения ε методом графа пар как показа-
но выше составляет O
(
n224n
)
, а объединение вершин и вычеркивание кратных дуг
выполняется за константное время, то алгоритм приведения произвольного поме-
ченного графа требует не более O
(
n224n
)
шагов.
5. Сравнение графов. Охарактеризуем отношение ρ, то есть найдем условия,
при которых (G,H) ∈ ρ. Имеет место следующее очевидное утверждение.
Утверждение 3. Графы G иH неотличимы тогда и только тогда, когда в каждом
классе неотличимости ε графа G+H находятся как вершины графа G, так и вершины
графа H.
Для проверки неотличимости графов G и H воспользуемся настроенным гра-
фом пар (DT (G + H) , DI , DF ), у которого множество DI состоит из всех вершин
({g}, {h}), где g, h ∈ G + H и g 6= h, а множество DF состоит из всех вершин
(S, Q) ∈ D1, где S = ∅ или Q = ∅. Пусть N = |G| + |H|. Ясно, что |DI | = O
(
N2
)
,
а |DT | = O
(
24N
)
. Определим сложность проверки неотличимости графов G и H.
В подразделе 2.1 показано, что построение отношения ε на вершинах графа G +H
требует не более O
(
N2 · 24N
)
. Проверка, находятся ли в каждом классе как вер-
шин графа G, так и вершин графа H, требует не более N шагов. Таким образом,
сложность проверки неотличимости графов G и H составляет O
(
N2 · 24N
)
.
Охарактеризуем отношение τ , то есть найдем условия, при которых (G,H) ∈ τ .
186
О методе построения отношения неотличимости помеченных графов
Для этого воспользуемся настроенным графом пар (DT (G + H) , DI , DF ), у которого
множество DI состоит из всех вершин (G ? x, H ? x), для всех x ∈ M , а множество
DF состоит из всех вершин (S, Q) ∈ D1, где S = ∅ или Q = ∅. Ясно, что при такой
настройке |DI | = m, DT ⊆ D1 и |DT | = O
(
24N
)
.
Имеет место следующее утверждение.
Утверждение 4. Графы G и H слабо неотличимы тогда и только тогда, когда
в настроенном графе пар (DT (G + H) , DI , DF ) ни из одной начальной вершины не
достижима ни одна финальная вершина.
Доказательство. Действительно, пусть (G,H) 6∈ τ , то есть LG 6= LH. Тогда суще-
ствует, по крайней мере, одно слово w = x1x2 . . . xk такое, что w ∈ LG⊕LH. По утвер-
ждению 1 существует единственный путь с меткой w из вершины (G ? x1,H ? x1) ∈
D. Так как слово w не порождается одним из множеств G?x1 и H ?x1, то этот путь
оканчивается в финальной вершине, достижимой из вершины (G ? x1,H ? x1) ∈ DI .
Утверждение доказано. ¤
Оценим сложность проверки слабой неотличимости графов G и H. Пусть N =
|G|+ |H|. Для проверки достижимости из некоторой начальной вершины графа пар
хотя бы одной его финальной вершины достаточно (при использовании известных
алгоритмов [10]) O
(
24N
)
шагов. Тогда для проверки слабой неотличимости графов
G и H достаточно O
(
m24N
)
шагов.
Следующее утверждение устанавливает соотношение между ρ и τ .
Теорема 2. 1) На множестве K(M) ρ ⊂ τ и обратное включение не выполня-
ется.
2. На подмножестве всех связных SD-графов ρ = τ .
Докажем вначале следующую
Лемма 1. Пусть G является SD-графом, H ⊂ G и g ∈ G − H. ({g}, H) ∈ κ∗
тогда и только тогда, когда существует h ∈ H такая, что (g, h) ∈ κ.
Доказательство. Очевидно, что из (g, h) ∈ κ следует, что ({g},H) ∈ κ∗.
Пусть ({g}, H) ∈ κ∗ и для любой вершины h ∈ H выполняется (g, h) 6∈ κ. Пред-
положим, что H ′ = {h1, . . . , hk} это наименьшее множество такое, что H ′ ⊆ H
и ({g}, H ′) ∈ κ∗. Тогда существуют слова w1, ..., wk такие, что wi ∈ Lg − Lhi , где
1 6 i 6 k. Рассмотрим слово w = w1◦wrev
1 ◦. . .◦wi◦wrev
i ◦. . .◦wk−1◦wrev
k−1◦wk. Так как
G является SD-графом, то для любой вершины q ∈ G и любого слова u ∈ Lg выпол-
няется q ? (u ◦ urev) = q. Следовательно, w ∈ Lg. Пусть слова w1, ..., wi−1 ∈ Lhi , где
1 < i 6 k, тогда hi?
(
w1 ◦ wrev
1 ◦ . . . ◦ wi−1 ◦ wrev
i−1
)
= hi и w1◦wrev
1 ◦. . .◦wi−1◦wrev
i−1 ∈ Lhi
.
Так как слово wi 6∈ Lhi , то слово w1 ◦wrev
1 ◦ . . . ◦wi−1 ◦wrev
i−1 ◦wi 6∈ Lhi . Из сказанного
следует, что слово w не порождается ни одной вершиной из H ′, то есть w ∈ Lg−LH′
и ({g},H ′) 6∈ κ∗.
Лемма доказана. ¤
Доказательство. Прямое включение в части 1 непосредственно следует из опре-
деления отношений.
Пример на рис. 4 показывает, что τ ⊆ ρ не выполняется для произвольных ND-
орграфов из K(M). Несложно убедиться, что LG = LH. Следовательно, (G,H) ∈ τ .
187
С.В. Сапунов
С другой стороны, легко видеть, что ΛG 6= ΛH. Действительно, L4 = L8 ∪L9 ∪L10 и
L8 ⊂ L4, L9 ⊂ L4, L10 ⊂ L4. Так как других вершин, кроме 4, с меткой d в графе G
нет, то (G,H) 6∈ ρ.
G
H
d
ba c
2 3
4
d
d d
ba c
10
5
9
6 7 8
1
d
d
d
d
b
a
c
1, 6
2, 7 4, 5,9
3, 8
4, 9,10
4, 5,10
4, 5,9,10
D ( + )G H
Рис. 4.
Пример на рис. 5 показывает, что τ ⊆ ρ не выполняется для произвольных D-
орграфов из K(M). Легко видеть, что LG = LH и, следовательно, (G,H) ∈ τ . С
другой стороны, легко убедиться, что ΛG 6= ΛH, так как ни одна вершина графа G
не порождает точно такой язык как вершина 7.
dd
a aa
bb c c1
2
3
4
5 6
7
8 9
G H
Рис. 5.
Докажем вторую часть теоремы. Предположим, что существуют SD-графы
G,H ∈ K(M) такие, что (G,H) ∈ τ и (G,H) 6∈ ρ, то есть LG = LH и ΛG 6= ΛH.
Тогда существует, по крайней мере, одна вершина g ∈ G такая, что Lg ⊆ LH, то есть
({g},H) ∈ κ∗, но для любой вершины h ∈ H выполняется (g, h) 6∈ κ. Так как прямая
сумма G+H SD-графов G и H также является SD-графом, то такое предположение
противоречит лемме 1.
Теорема доказана. ¤
Заключение. Таким образом, в работе предложен метод анализа языков вер-
шин и графов – граф пар, являющийся модификацией известного в теории авто-
матов графа пар состояний. С его помощью показано, что верхняя оценка длины
188
О методе построения отношения неотличимости помеченных графов
слова, различающего две вершины помеченного графа в общем случае экспонен-
циальна от числа вершин графа. Разработаны методы проверки неотличимости и
слабой неотличимости помеченных графов с использованием графа пар. Эти ре-
зультаты создают основу для разработки методов распознавания и идентификации
помеченных графов.
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с.
Ин-т прикл. математики и механики НАН Украины, Донецк
sapunov@iamm.ac.donetsk.ua
Получено 20.04.08
189
|
| id | nasplib_isofts_kiev_ua-123456789-19997 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1683-4720 |
| language | Russian |
| last_indexed | 2025-11-24T15:07:11Z |
| publishDate | 2008 |
| publisher | Інститут прикладної математики і механіки НАН України |
| record_format | dspace |
| spelling | Сапунов, С.В. 2011-05-19T19:29:41Z 2011-05-19T19:29:41Z 2008 О методе построения отношения неотличимости помеченных графов / С.В. Сапунов // Труды Института прикладной математики и механики НАН Украины. — Донецьк: ІПММ НАН України, 2008. — Т. 16. — С. 179-189. — Бібліогр.: 11 назв. — рос. 1683-4720 https://nasplib.isofts.kiev.ua/handle/123456789/19997 519.7 ru Інститут прикладної математики і механіки НАН України Труды Института прикладной математики и механики НАН Украины О методе построения отношения неотличимости помеченных графов Article published earlier |
| spellingShingle | О методе построения отношения неотличимости помеченных графов Сапунов, С.В. |
| title | О методе построения отношения неотличимости помеченных графов |
| title_full | О методе построения отношения неотличимости помеченных графов |
| title_fullStr | О методе построения отношения неотличимости помеченных графов |
| title_full_unstemmed | О методе построения отношения неотличимости помеченных графов |
| title_short | О методе построения отношения неотличимости помеченных графов |
| title_sort | о методе построения отношения неотличимости помеченных графов |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/19997 |
| work_keys_str_mv | AT sapunovsv ometodepostroeniâotnošeniâneotličimostipomečennyhgrafov |