О высоте идентификаторов вершин помеченных графов
Рассматривается задача различения вершин помеченного графа по ассоциированным с ними языкам в
 алфавите меток. Показано, что верхняя оценка длины слова, различающего две вершины графа,
 детерминированного по разметке окрестностей вершин, равна половине числа его вершин. Показано&...
Збережено в:
| Опубліковано в: : | Искусственный интеллект |
|---|---|
| Дата: | 2013 |
| Автори: | , |
| Формат: | Стаття |
| Мова: | Російська |
| Опубліковано: |
Інститут проблем штучного інтелекту МОН України та НАН України
2013
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/85116 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | О высоте идентификаторов вершин помеченных
 графов / С.В. Сапунов, В.Ю. Пилипенко // Искусственный интеллект. — 2013. — № 3. — С. 444–454. — Бібліогр.: 8 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860180919432773632 |
|---|---|
| author | Сапунов, С.В. Пилипенко, В.Ю. |
| author_facet | Сапунов, С.В. Пилипенко, В.Ю. |
| citation_txt | О высоте идентификаторов вершин помеченных
 графов / С.В. Сапунов, В.Ю. Пилипенко // Искусственный интеллект. — 2013. — № 3. — С. 444–454. — Бібліогр.: 8 назв. — рос. |
| collection | DSpace DC |
| container_title | Искусственный интеллект |
| description | Рассматривается задача различения вершин помеченного графа по ассоциированным с ними языкам в
алфавите меток. Показано, что верхняя оценка длины слова, различающего две вершины графа,
детерминированного по разметке окрестностей вершин, равна половине числа его вершин. Показано
также, что в языке каждой из любых двух различных вершин есть слово, отличающее одну вершину
от другой, и его длина меньше числа вершин графа. Найдены оценки высоты конечных множеств
слов, отличающих одну вершину графа от всех других его вершин (т.н. идентификаторов).
Розглядається задача розрізнення вершин позначеного графа за асоційованими з ними мовами в алфавіті
позначок. Визначено, що верхня оцінка довжини слова, що розрізнює дві вершини графа, детермінованого за
розміткою околів вершин, дорівнює половині від кількості його вершин. Визначено також, що у мові кожної
з двох різних вершин є слово, яке відрізняє одну вершину від іншої, і його довжина менша, ніж кількість
вершин у графі. Знайдено оцінки висоти скінчених множин слів, що відрізняють одну вершину графа від
інших його вершин (т.з. ідентифікаторів).
The problem of vertex distinguishing on vertex labeled graphs is considered. Two vertices are called distinguishable if
associated languages over the alphabet of labels are different. A linear upper bound of vertex distinguishing word
length equal to half of the number of all vertices is obtained. It is shown that at both languages of two different
vertices there are distinguishing words and their lengths are less then number of all vertices. Upper bounds of height
of finite sets of words over the vertex labels alphabet distinguishing a given vertex from other (i.e. identifiers) are
obtained.
|
| first_indexed | 2025-12-07T18:02:15Z |
| format | Article |
| fulltext |
ISSN 1561-5359 «Искусственный интеллект» 2013 № 3 444
5С
УДК 519.7
С.В. Сапунов
1
, В.Ю. Пилипенко
2
1
Институт прикладной математики и механики НАН Украины
Украина, 83114, г. Донецк, ул. Розы Люксембург, 74
2Донбасский государственный педагогический университет, Украина
Украина, 84116, Донецкая обл., г. Славянск, ул. Генерала Батюка, 19
О высоте идентификаторов вершин помеченных
графов
S.V. Sapunov
1
, V.Yu. Pilipenko
2
1
Institute of Applied Mathematics and Mechanics of NAS of Ukraine
Ukraine, 83114, Donetsk, Rozy Luksemburg st., 74.
2
Donbas State Teachers' Training University
Ukraine, 84116, Donetsk area. Slavyansk, Generala Batyuka st., 19
On Height of Vertex Identifiers of Vertex Labeled Graphs
С.В. Сапунов
1
, В.Ю. Пилипенко
2
1
Інститут прикладної математики і механіки НАН України
Україна, 83114, м. Донецьк, вул. Рози Люксембург, 74
2
Донбаський державний педагогічний університет, Україна
Україна, 84116, Донецька обл., м. Слов’янськ, вул. Генерала Батюка, 19
Про висоту ідентифікаторів вершин графів
з позначеними вершинами
Рассматривается задача различения вершин помеченного графа по ассоциированным с ними языкам в
алфавите меток. Показано, что верхняя оценка длины слова, различающего две вершины графа,
детерминированного по разметке окрестностей вершин, равна половине числа его вершин. Показано
также, что в языке каждой из любых двух различных вершин есть слово, отличающее одну вершину
от другой, и его длина меньше числа вершин графа. Найдены оценки высоты конечных множеств
слов, отличающих одну вершину графа от всех других его вершин (т.н. идентификаторов).
Ключевые слова: помеченные графы, языки в алфавите меток, идентификаторы вершин.
The problem of vertex distinguishing on vertex labeled graphs is considered. Two vertices are called distinguishable if
associated languages over the alphabet of labels are different. A linear upper bound of vertex distinguishing word
length equal to half of the number of all vertices is obtained. It is shown that at both languages of two different
vertices there are distinguishing words and their lengths are less then number of all vertices. Upper bounds of height
of finite sets of words over the vertex labels alphabet distinguishing a given vertex from other (i.e. identifiers) are
obtained.
Key words: vertex labeled graphs, languages over the label alphabet, vertex identifiers.
Розглядається задача розрізнення вершин позначеного графа за асоційованими з ними мовами в алфавіті
позначок. Визначено, що верхня оцінка довжини слова, що розрізнює дві вершини графа, детермінованого за
розміткою околів вершин, дорівнює половині від кількості його вершин. Визначено також, що у мові кожної
з двох різних вершин є слово, яке відрізняє одну вершину від іншої, і його довжина менша, ніж кількість
вершин у графі. Знайдено оцінки висоти скінчених множин слів, що відрізняють одну вершину графа від
інших його вершин (т.з. ідентифікаторів).
Ключові слова: позначені графи, мови у алфавіті позначок, ідентифікатори вершин.
О высоте индентификаторов вершин помеченных графов
«Штучний інтелект» 2013 № 3 445
5С
Введение
Одной из широко используемых моделей информационных систем является взаи-
модействие двух объектов: агента и его операционной среды [1]. Проблематика, изуча-
емая с помощью этой модели, чрезвычайно обширна: от навигации мобильных роботов
в физическом рабочем пространстве, до функционирования программных агентов в
сложных информационных средах [2], [3]. Одним из подходов к анализу операционной
среды является ее представление в виде топологической модели, т.е. графа с помечен-
ными элементами (вершинами, дугами, точками «прикосновения» дуги к вершине и т.д.).
Одной из центральных задач анализа операционной среды является определение агентом
своего местоположения в среде (самолокализация агента, если агент локализует себя
самостоятельно). В случае топологической среды это означает определение началь-
ной вершины графа, т.е. отделение этой вершины от всех других вершин. Заметим,
что эта задача имеет соответствующий аналог в теории автоматов [4]. В [5], [6] предло-
жен ряд методов и алгоритмов решения задачи самолокализации, основанных на исполь-
зовании конечных множеств слов в алфавите меток, которые отличают одну вершину
графа от всех других его вершин (т.н. идентификаторов вершин). Рассматривались
позитивные идентификаторы, содержащие исключительно слова языка вершины и сме-
шанные идентификаторы, содержащие также слова, отсутствующие в языке вершины.
Для предложенных методов важной проблемой явилось оценивание сложности мини-
мальных идентификаторов, т.е. таких, которые состоят из наименьшего числа слов
кратчайшей длины. Отысканию таких оценок посвящена данная статья.
Постановка задачи
Анализируются языки, ассоциированные с вершинами связных помеченных
неориентированных графов. Требуется оценить сверху длину кратчайших слов, отли-
чающих в совокупности одну вершину графа от всех других его вершин.
Основные определения
Неопределяемые понятия общеизвестны и их можно найти в [7].
Помеченным графом назовем конечный простой связный неориентированный граф
с помеченными вершинами ( )µ,,, MEVG = , где V – множество вершин, nV = , E –
множество ребер (т.е. неупорядоченных пар вершин), M – множество меток, MV→:µ –
сюръективная функция разметки вершин. Под открытой окрестностью
v
Γ вершины Vv∈
будем понимать множество всех вершин, смежных с v . Под окрестностью ( )vΓ вершины
Vv∈ будем понимать { }v
v
∪Γ . Путем в графе G назовем последовательность вершин
k
vvp K
1
= , такую, что ( ) Evv
ii
∈
+1
, , 1,,1 −= ki K . Число Nk∈ назовем длиной пути p .
Меткой ( )pµ пути p назовем слово ( ) ( )
k
vvw µµ K
1
= в алфавите меток M . Будем гово-
рить, что слово w определяется вершиной
1
v . Длину слова w будем обозначать через
( )wd . Путь с меткой w , начинающийся в вершине v , будем обозначать ( )wvp , .
Инверсией слова ( ) ( )
k
vvw µµ K
1
= назовем слово ( ) ( )
1
1
vvw
k
µµ K=
− . Множество
v
L
всех слов +
∈Mw , определяемых вершиной Vv∈ , будем называть языком этой вершины.
Граф G будем называть приведенным, если для любых вершин Vvv ∈
21
, из
21
vv ≠ сле-
дует
21
vv
LL ≠ .
Сапунов С.В., Пилипенко В.Ю.
«Искусственный интеллект» 2013 № 3 446
5С
Определим на +
M частичную операцию o композиции слов. Пусть Myx ∈, ,
∗
∈Mww
21
, , тогда
2121
xwwxwxw =o и
21
ywxw o не определено, если yx ≠ . Композицию k
экземпляров слова w будем обозначать k
w .
Введем операцию V
MV 2: →×∗
+ соотношением: для любой вершины Vv∈ и лю-
бого слова +
∈Mw через wv∗ обозначим множество всех вершин Vh∈ таких, что су-
ществует путь p , соединяющий вершины v и h, и ( ) wp =µ . Ясно, что если слово
v
Lw∈ ,
то 0>∗wv и 0=∗wv – в противном случае.
Слово w′ называется подсловом слова w , если существуют слова
1
w и
2
w (возмож-
но, однобуквенные) такие, что
21
wwww oo ′= . Если ( ) 1
1
=wd ( ( ) 1
2
=wd ), то слово w′ на-
зывается начальным отрезком (конечным отрезком) слова w . Будем писать ww p′ , если
слово w′ является начальным отрезком слова w .
Функцию разметки MV→:µ будем называть детерминированной или Д-разметкой,
если для любой вершины Vv∈ и любых вершин
v
ts Γ∈, из ts ≠ следует ( ) ( )ts µµ ≠ .
Помеченный граф G с детерминированной функцией разметки будем называть детерми-
нированным, или Д-графом. Функцию разметки MV→:µ будем называть сильно детер-
минированной или СД-разметкой, если для любой вершины Vv∈ и любых вершин ( )vts Γ∈,
из ts ≠ следует ( ) ( )ts µµ ≠ . Помеченный граф G с сильно детерминированной функ-
цией разметки будем называть сильно детерминированным, или СД-графом. В [8] было
показано, что из определения СД-графа вытекают следующие его свойства: (1) помечен-
ный граф G является СД-графом тогда и только тогда, когда для любой вершины Vv∈
и любого слова +
∈Mw выполняется 1≤∗wv , причем 1=∗wv , если
v
Lw∈ и 0=∗wv –
в противном случае; (2) для любых различных вершин Vvv ∈
21
, и любого слова
21
vv
LLw ∩∈
расстояние между вершинами wv ∗
1
и wv ∗
2
не меньше 4.
Идентификатором вершины Vv∈ назовем конечное множество слов +
⊂ MW
v
, та-
кое, что для любой вершины Vh∈ равенство
hvvv
LWLW ∩=∩ выполняется тогда и только
тогда, когда hv= . Всякий идентификатор
v
W можно представить как объединение
−+
∪
vv
WW
двух множеств
vvv
LWW ∩=
+ и
vvv
LWW \=
− . Идентификатор
v
W назовем позитивным,
если ∅=
−
v
W , и негативным, если ∅=
+
v
W .
Высота идентификаторов вершин
Следующая теорема дает оценки длин слов, различающих две вершины связно-
го СД-графа.
Теорема. Пусть G является связным приведенным СД-графом. Тогда для
любых вершин Vvv ∈
21
, ,
21
vv ≠ , одновременно выполняются утверждения:
1) длина кратчайшего слова из
21
vv
LL ⊕ не превосходит
2
n
;
2) существует слово из
21
\
vv
LL , длина которого строго меньше n .
Доказательство. Если ( ) ( )
21
vv µµ ≠ , то любое из слов ( )
11
vw µ= и ( )
22
vw µ=
является кратчайшим словом из
21
vv
LL ⊕ . Ясно, что ( )
2
1
n
vd ≤ и ( )
2
2
n
vd ≤ , причем ра-
О высоте индентификаторов вершин помеченных графов
«Штучний інтелект» 2013 № 3 447
5С
венство выполняется тогда и только тогда, когда { }
21
,vvV = . Таким образом, в этом
случае выполняются оба утверждения теоремы.
Пусть ( ) ( ) xvv ==
21
µµ . Так как граф G – приведенный и связный, то ∅≠
21
\
vv
LL
и ∅≠
12
\
vv
LL и, следовательно, ∅≠⊕
21
vv
LL .
Обозначим через u метку некоторого кратчайшего пути из
1
v в
2
v . Легко видеть,
что ( ) nud ≤≤4 . Действительно, ограничение ( )ud снизу вытекает из определения СД-гра-
фа, а ограничение сверху определяется числом вершин графа G . Из определения СД-гра-
фа следует, что слово u не является палиндромом, т.е. 1−
≠ uu . Действительно, если u
является палиндромом, то существует начальный отрезок u′ и конечный отрезок u ′′
слова u такие, что ( ) ( )
=′′=′
2
n
udud и ( ) 1−
′=′′ uu . Тогда вершины uv ′∗
1
и uv ′′∗
2
либо
смежные, либо принадлежат окрестности одной и той же вершины. В обоих случаях
граф G не является СД-графом, что невозможно.
Обозначим через w кратчайшее слово из
21
vv
LL ⊕ . Без потери общности предпо-
ложим, что
21
\
vv
LLw∈ . Обозначим через w′ длиннейший начальный отрезок слова w ,
такой, что
21
vv
LLw ∩∈′ , т.е. yww ′= , где My∈ .
Предположим, что граф G является деревом.
Пусть ( )wvp ,
1
и ( )wvp ′,
2
не имеют общих вершин. Введем вспомогательные
обозначения. Пусть 1
311
−
= wuwu oo , где ww ′p
1
, ww ′p
3
, а
1
u является меткой крат-
чайшего пути из вершины
11
wv ∗ в вершину
32
wv ∗ . Положим, что ( ) ( )wdwd ′≤≤
1
1 и
( ) ( )wdwd ′≤≤
3
1 . Обозначим через
2
w метку кратчайшего пути из вершины
11
wv ∗ в
вершину wv ′∗
1
. Обозначим через
4
w метку кратчайшего пути из вершины
32
wv ∗ в
вершину wv ′∗
2
. Таким образом,
21
www o=′ и
43
www o=′ . Если ( ) ( )
3211
wvwv ∗=∗ µµ ,
то по определению СД-графа ( ) 4
1
≥ud . Тогда в графе G число вершин, которые не
принадлежат ( )wvp ,
1
, больше, либо равно ( )wd . Следовательно, ( )
2
n
wd ≤ и первое
утверждение теоремы выполняется. Пусть ( ) ( )
3211
wvwv ∗≠∗ µµ . Тогда ( ) ( )
31
wdwd ≠ .
Положим, что ( ) ( )
31
wdwd > . Так как ww ′p
1
и ww ′p
3
, то
13
ww p . Рассмотрим граф
на рис. 1. Здесь стрелкой обозначается направление прохождения пути в соответствии с
чтением его метки слева направо.
Рисунок 1 – Граф, с чтением его метки слева направо
Сапунов С.В., Пилипенко В.Ю.
«Искусственный интеллект» 2013 № 3 448
5С
Обозначим через u′ начальный отрезок слова 1
1
−
u такой, что ( ) ( )wduwd ′≤′o
3
.
Слово
21
3 vv
LLuw ∩∈′o . Если wuw ′′ po
3
, то в окрестности вершины
32
wv ∗ находятся
две различные вершины с одной и той же меткой, что невозможно по определению СД-
графа. Следовательно, вершина uwv ′∗ o
31
не принадлежит ( )wvp ,
1
. Тогда в графе G
число вершин, которые не принадлежат ( )wvp ,
1
, больше либо равно ( )wd . Следова-
тельно, ( )
2
n
wd ≤ и первое утверждение теоремы выполняется.
Проверим, выполняется ли второе утверждение теоремы для деревьев при условии,
что ( )wvp ,
1
и ( )wvp ′,
2
не имеют общих вершин. Обозначим через
5
w метку кратчайшего
пути из вершины
31
wv ∗ в вершину
11
wv ∗ . Если слово
12
\
1
13 vv
LLuw ∈
−
o , то второе утвер-
ждение теоремы выполняется, т.к. ( ) nuwd <
−1
13
o . Пусть
21
1
13 vv
LLuw ∩∈
−
o . Тогда сло-
во
2
1
1
1
5
1
13 v
Luwuw ∈
−−−
ooo . Если слово
12
\
1
1
1
5
1
13 vv
LLuwuw ∈
−−−
ooo , то второе утвержде-
ние теоремы выполняется, т.к. ( ) nuwuwd <
−−− 1
1
1
5
1
13
ooo . Так как дерево G конечно, то
для некоторого натурального k выполняется ( )
12
\
1
5
1
13 vv
k
LLuwuw ∈′
−−
ooo , где 1
1
−
′ uu p .
Величина ( )( ) nuwuwd
k
<′
−−
ooo
1
5
1
13
. Следовательно, второе утверждение теоремы в дан-
ном случае выполняется.
Доказательство обоих утверждений теоремы для случая, когда ( ) ( )
13
wdwd >
аналогично.
Покажем, что оценка длины слова из первого утверждения теоремы достижима.
Рассмотрим граф на рис. 2.
Рисунок 2 – Граф, подтверждающий оценку длины слова
Легко видеть, что длина слова w равна
2
n
.
Пусть граф G по-прежнему является деревом. Предположим, что ( )wvp ,
1
и ( )wvp ′,
2
имеют общие вершины. Предположим, далее, что для любого слова ww ′′′ p выполня-
ется
21
vwv ≠′′∗ и
12
vwv ≠′′∗ . Введем вспомогательные обозначения. Обозначим через
1
w
начальный отрезок слова w′ такой, что uw p
1
и длина
1
w наибольшая из возможных.
Обозначим через
2
w конечный отрезок слова w′ , такой, что
21
www o=′ . Обозначим
через
3
w начальный отрезок слова w′ такой, что 1
3
−
uw p и длина
3
w , наибольшая из
возможных. Обозначим через
4
w конечный отрезок слова w′ такой, что
43
www o=′ .
По предположению ( )
11
,wvp и ( )
32
,wvp имеют общие вершины. Если
31
ww = , то метка
кратчайшего пути из вершины
11
wv ∗ в вершину
32
wv ∗ является палиндромом, что
невозможно для СД-графов. Следовательно,
31
ww ≠ и либо
31
ww p , либо
13
ww p .
О высоте индентификаторов вершин помеченных графов
«Штучний інтелект» 2013 № 3 449
5С
Пусть
31
ww p . Если ( )
11
,wvp и ( )
12
,wvp имеют общие вершины, то метка кратчайшего
пути из вершины
11
wv ∗ в вершину
12
wv ∗ является палиндромом, что невозможно для
СД-графов. Обозначим через
6
w метку кратчайшего пути из вершины
11
wv ∗ в верши-
ну
12
wv ∗ . По определению СД-графа ( ) 4
6
≥wd . Обозначим через
5
w метку кратчайшего
пути из вершины
1
v в вершину
31
wv ∗ . Длина слова
45
ww o меньше, чем ( )wd . Следова-
тельно,
12
45 vv
LLww ∩∈o и существует простой путь ( )
452
, wwvp o (рис. 3).
Рисунок 3 – Простой путь ( )
452
, wwvp o
Обозначим через
7
w метку кратчайшего пути из вершины
11
wv ∗ в вершину
32
wv ∗ .
Слово w′ можно представить в виде
47
1
61
wwww ooo
− . Тогда слово
2
w можно пред-
ставить в виде
47
1
6
www oo
− . Слово
1
761 v
Lwww ∈oo и его длина меньше, чем ( )wd .
Следовательно,
21
761 vv
LLwww ∩∈oo . Так как слово
76
ww o не может быть палиндромом,
то
3761
wwww poo / и вершины пути ( )
7612
, wwwvp o∗ не принадлежат ( )wvp ,
1
. Тогда
в графе G число вершин, которые не принадлежат ( )wvp ,
1
, больше либо равно ( )wd .
Следовательно, ( )
2
n
wd ≤ и первое утверждение теоремы выполняется.
Покажем, что при данных условиях второе утверждение теоремы также выполняет-
ся. Слово
2
1
6
1
61 v
Lwww ∈
−−
oo и его длина меньше, чем n . Если
12
\
1
6
1
61 vv
LLwww ∈
−−
oo ,
то второе утверждение теоремы выполняется. Пусть
12
1
6
1
61 vv
LLwww ∩∈
−−
oo . Тогда
слово ( )
2
31
61 v
Lww ∈
−
o . Если ( )
12
\
31
61 vv
LLww ∈
−
o , то второе утверждение теоремы выполняется.
Так как дерево G конечно, то для некоторого натурального k выполняется, ( )1
61
k
www ∈′′
−
oo
12
\
vv
LL∈ где 1
6
−
′′ ww p . Величина ( )( ) nwwwd
k
<′′
−
oo
1
61
. Следовательно, второе утвержде-
ние теоремы в данном случае выполняется. Доказательство обоих утверждений теоремы
для случая, когда
13
ww p аналогично.
Пусть граф G является деревом, а пути ( )wvp ,
1
и ( )wvp ′,
2
имеют общие вершины.
Положим, что wu p . Тогда { }
21
1
,
vv
LLuu ∩⊆
− . Действительно, если
2
v
Lu∉ или
1
1
v
Lu ∉
− ,
то в
21
vv
LL ⊕ существует слово, длина которого меньше ( )wd , что невозможно. Предполо-
Сапунов С.В., Пилипенко В.Ю.
«Искусственный интеллект» 2013 № 3 450
5С
жим, что для некоторого натурального k выполняется ( ){ }
21
1
,
vv
kk
LLuu ∩⊆
−
и ywuw
k
1
o= ,
где My∈ , а
1
w является конечным отрезком слова w′ . Оценим длину слова w. Из того,
что слово
1
1 v
k
Lywu ∈o следует, что слово
2
1
1
v
k
Lywu ∈
−
o и существует простой
путь ( )ywuvp
k
1
1
2
, o
− . Так как ( ) ( )wdywud k
<
−
1
1
o , то слово
1
1
1
v
k
Lywu ∈
−
o и существует простой
путь ( )ywuvp
k
1
1
1
, o
− . Тогда слово
2
1
2
v
k
Lywu ∈
−
o и существует простой путь ( )ywuvp
k
1
2
2
, o
− . Про-
должая эти рассуждения получаем, что слово
2
1 v
Lyw ∈ и существует простой путь ( )ywvp
12
, .
Так как ( ) ( )wdywd <
1
, то слово
1
1 v
Lyw ∈ и существует простой путь ( )ywvp
11
, . Тогда
слово
2
1
1
v
Lywu ∈
−
o и существует простой путь ( )ywuvp
1
1
2
, o
− . Так как ( ) ( )wdywud <
−
1
1
o , то
слово
1
1
1
v
Lywu ∈
−
o и существует простой путь ( )ywuvp
1
1
1
, o
− . Продолжая рассуждения,
получаем, что слово ( )
21
1
1
vv
k
LLywu ∩∈
−
o и, следовательно, слово ( )
2
1
11
v
k
Lywu ∈
+
−
o (рис. 4).
Рисунок 4 – Слово ( )
21
1
1
vv
k
LLywu ∩∈
−
o и слово ( )
2
1
1
1
v
k
Lywu ∈
+
−
o
В данном случае ( ) ( ) ( ) ( ) 142212
1
−−+++≥ kywdkudkn и ( ) ( ) ( ) kywdukdwd −+=
1
.
Следовательно, ( )
2
n
wd ≤ для любого 1≥k и первое утверждение теоремы выполняется.
Выполнимость второго утверждения теоремы следует из того, что слово ( )
1
11 k
ywu ∈
+
−
o
12
\
vv
LLy∈ и его длина меньше, чем n .
Таким образом, оба утверждения теоремы выполняется для деревьев.
Пусть граф G не является деревом. Если ( )wvp ,
1
и ( )wvp ′,
2
не содержат циклов,
то доказательство утверждений теоремы аналогично их доказательству для деревьев.
Предположим, что ( )wvp ,
1
и ( )wvp ′,
2
не содержат общих вершин. Пусть путь ( )wvp ,
1
содержит цикл, например, ( )
3211
, wwwvp o∗ (рис. 5). Здесь G′ обозначает подграф
графа G , представляющий неориентированное дерево с корнем в вершине
2
v , ветви
которого помечены начальными отрезками слова w . Принципы выделения подграфа G′
из графа G будут объяснены ниже.
Рисунок 5 – Цикл пути ( )wvp ,
1
– ( )
3211
, wwwvp o∗
О высоте индентификаторов вершин помеченных графов
«Штучний інтелект» 2013 № 3 451
5С
Пусть путь ( )wvp ′,
2
содержит цикл ( )
3212
, wwwvp o∗ . По определению СД-графа
путь ( )
4212
, wwwvp oo определен единственным образом. Тогда слово
21
421 vv
LLwww ∩∈oo ,
а слово
21
\
421 vv
LLywww ∈oo . Легко видеть, что ( ) ( )wdywwwd <
421
oo . Следователь-
но, ywww
421
oo является кратчайшим словом из
21
vv
LL ⊕ , что невозможно. Если ( ) ( )wdud ≥ ,
то очевидно, что ( )
2
n
wd ≤ . Пусть ( ) ( )wdud < . Так как путь ( )uvp ,
1
содержит вершины,
которые не принадлежат ( )wvp ,
1
, то положим его длину минимальной, т.е. ( ) 4=ud .
Так как для некоторого натурального k вершина
2
v определяет путь с меткой k
u
такой, что ( ) ( )wdud
k
′= , то для уменьшения числа вершин, не принадлежащих ( )wvp ,
1
,
положим
12
vuv =∗ . Пусть ( ) ywwwwww
s
42321
oooo= . Предположим, что длины слов
1
w ,
2
w ,
3
w ,
4
w совпадают и 1=s . Тогда существует простой путь ( )
423212
, wwwwwvp oooo .
Слово
21
421 vv
LLywww ∩∈oo так как его длина меньше, чем ( )wd . Следовательно, существует
простой путь ( )ywwwvp
4212
, oo . Так как ( ) ( )wdwwwwd <
−1
1321
ooo , то
21
1
1321 vv
LLwwww ∩∈
−
ooo и
существует простой путь ( )1
13212
,
−
wwwwvp ooo . Так как ( ) ( )wdwwwwwd <
32321
oooo ,
то
21
32321 vv
LLwwwww ∩∈oooo и существует простой путь ( )
323212
, wwwwwvp oooo .
Слово
21
4
1
31 vv
LLywww ∩∈
−
oo так как его длина меньше, чем ( )wd . Следовательно, су-
ществует простой путь ( )ywwwvp
4
1
312
, oo
− . Так как длины слов 1
1
1
2
1
31
−−−
wwww ooo ,
4
1
3
1
2
1
31
wwwww oooo
−−− , 1
2
1
3
1
2
1
31
−−−−
wwwww oooo меньше, чем ( )wd , то все эти слова при-
надлежат
21
vv
LL ∩ и существуют простые пути с соответствующими метками из вер-
шины
2
v (рис. 6).
Рисунок 6 – Простые пути с соответствующими метками из вершины
Сапунов С.В., Пилипенко В.Ю.
«Искусственный интеллект» 2013 № 3 452
5С
Оценим число ( )Gn ′ вершин в подграфе G′ . В данном случае ( ) ( )3
1
+≥′ wdGn
) ( ) ( ) ( ) 9444
432
−+++ wdwdwd , а ( ) ( ) ( ) ( ) ( ) 32
4321
−+++= wdwdwdwdwd . Таким образом,
значение ( )wd , по крайней мере, в 2 раза меньше, чем число вершин в подграфе G′ . Сле-
довательно, ( )
2
n
wd ≤ и первое утверждение теоремы выполняется. С ростом величины s
число вершин в подграфе G′ будет только возрастать. Таким образом, значение ( )wd не
превысит
2
n
.
Выполнение второго утверждения теоремы следует из того, что слово
12
\
1
1 vv
LLwu ∈
−
o
и его длина меньше n .
Пусть ( )wvp ,
1
и ( )wvp ′,
2
имеют общие вершины. При этом, по соображениям,
изложенным выше, цикл может содержать только путь ( )wvp ,
1
.
Предположим, что для любого слова ww ′′′ p выполняется
21
vwv ≠′′∗ и
12
vwv ≠′′∗ .
Введем дополнительные обозначения. Пусть ( ) ywwwwww
s
42321
oooo= . Пусть
1
865
−
= wwwu oo ,
где
165
www po ,
1
1
68
www po
− и оба эти слова имеют максимальную возможную длину.
Обозначим через
7
w конечный отрезок слова
1
w такой, что
1765
wwww =oo . Обозначим
через
9
w конечный отрезок слова w′ такой, что wwww ′=
−
9
1
68
oo и ( )
423219
wwwwww
s
oooo′= ,
1
1
681
wwww ′=
−
oo . Пусть ( )
4232710
wwwwww
s
oooo= . Рассмотрим граф на рис. 7.
Рисунок 7 – Граф двух слов с максимальной длиной
Здесь G′ обозначает неориентированное дерево, ветви которого помечены всеми на-
чальными отрезками слов
9
w и ( )
4
1
3
1
2
1
31
wwwww
s
oooo
−−−
′ , а G ′′ обозначает неориентирован-
ное дерево, ветви которого помечены всеми начальными отрезками слов
10
w и ( 1
37
www oo
− .
)
4
1
3
1
2
www
s
ooo
−− Так как число вершин дерева G ′′ не меньше ( )
10
wd , то число вершин гра-
фа G , которые не принадлежат ( )wvp ,
1
не меньше, чем ( )wd . Следовательно, ( )
2
n
wd ≤
и первое утверждение теоремы выполняется.
Выполнение второго утверждения теоремы следует из того, что слово
12
\
108 vv
LLyww ∈o и его длина меньше n .
О высоте индентификаторов вершин помеченных графов
«Штучний інтелект» 2013 № 3 453
5С
Пусть ( ) ywwwwww
s
42321
oooo= и
1
wu p . Введем вспомогательные обозначения.
Обозначим через
5
w начальный отрезок слова
1
w такой, что uw =
5
. Обозначим через
6
w
конечный отрезок слова
1
w такой, что
651
www o= . Пусть ( )
423267
wwwwww
s
oooo= .
Рассмотрим граф на рис. 8.
Рисунок 8 – Граф условия теоремы ( ) ywwwwww
s
42321
oooo= и
1
wu p
Здесь G′ обозначает неориентированное дерево, ветви которого помечены всеми
начальными отрезками слов
7
w и ( )
4
1
3
1
2
1
36
wwwww
s
oooo
−−− . Так как число вершин дерева G′
не меньше ( )
7
wd , то число вершин графа G , которые не принадлежат ( )wvp ,
1
не меньше,
чем ( )wd . Следовательно, ( )
2
n
wd ≤ и первое утверждение теоремы выполняется.
Выполнение второго утверждения теоремы следует из того, что слово (
26
www oo
)
12
\
423 vv
LLywww ∈ooo и его длина меньше n .
Доказательство выполнимости утверждений теоремы для случаев, когда
21
wwu op
и
421
wwwu oop аналогично.
Теорема доказана.
Из этой теоремы непосредственно вытекают следующие утверждения.
Следствие 1. Высота идентификатора любой вершины произвольного связного
приведенного СД-графа не превосходит
2
n .
Следствие 2. Высота позитивного идентификатора любой вершины
произвольного связного приведенного СД-графа не превосходит n .
Выводы
Таким образом, в работе показано, что верхняя оценка длины слова, разли-
чающего две вершины СД-графа, равна половине числа его вершин. Показано также,
что в языке каждой из любых двух различных вершин есть слово, отличающее одну
вершину от другой, и его длина меньше числа вершин графа. При помощи этих
результатов получены оценки высоты идентификаторов вершин, что влияет на
эффективность алгоритмов самолокализации мобильных агентов в топологических
средах (роботов, поисковых программ и т.п.).
Сапунов С.В., Пилипенко В.Ю.
«Искусственный интеллект» 2013 № 3 454
5С
Литература
1. Капитонова Ю.В. Математическая теория проектирования вычислительных систем / Ю.В. Капитонова,
А.А. Летичевский. – Москва : Наука, 1988. – 296 с.
2. Dudek G. Computational Principles of Mobile Robotics / G. Dudek, M. Jenkin. – Cambridge University Press,
Cambridge, 2000. – 280 p.
3. Peled Doron A. Software Reliability Methods / Peled Doron A. – Springer-Verlag, 2001. – 331 p.
4. Kohavi Z. Switching and finite automata theory / Z. Kohavi, N. Jha. – Cambridge University Press, 2010. – 617 p.
5. Сапунов С.В. Определение положения робота в топологической среде / С.В. Сапунов // Искусственный
интеллект. – 2008. – № 4. – С. 558-565.
6. Грунский И.С. Идентификация вершин помеченных графов / И.С. Грунский, С.В. Сапунов // Труды
ИПММ. – 2010. – Т. 20. – С. 86-97.
7. Хопкрофт Д.Э. Введение в теорию автоматов, языков и вычислений / Д.Э. Хопкрофт, Р. Мотвани,
Д.Д. Ульман. – М. : Изд. дом «Вильямс», 2002. – 528 с.
8. Грунский И.С. Восстановление графа операционной среды мобильного робота путем разметки вершин,
пригодной для дальнейшей навигации / И.С. Грунский, С.В. Сапунов // Искусственный интеллект. –
2012. – № 4. – С. 420-428.
Literaturа
1. Kapitonova Yu.V., Letichevsky A.A. Mathematical Theory of Computational Systems Design. – Moscow :
Nauka, 1988. – 296 p.
2. Dudek G. Jenkin M. Computational Principles of Mobile Robotics – Cambridge University Press, Cambridge,
2000. – 280 p.
3. Peled Doron A. Software Reliability Methods – Springer. – Verlag, 2001. – 331 p.
4. Kohavi Z., Jha N. Switching and finite automata theory – Cambridge University Press, 2010. – 617 p.
5. Sapunov S.V. Mobile Robot Self Location on Topological Environment // Iskusstvennyj intellekt. – 2008.
№ 4. – P. 558-565.
6. Grunsky I.S., Sapunov S.V. Identification of vertices of vertex labeled graphs // Trudy IPMM. – 2010. –
V. 20. – P. 86-97.
7. Hopcroft J.E., Motwani R., Ullman J.D. Introduction to Automata Theory, Languages, and Computation. –
Moscow, Williams Publishing, 2002. – 528 p.
8. Grunsky I.S., Sapunov S.V. Reconstruction of the graph of operating environment of mobile robot by
vertex-labeling sufficient for further navigation // Iskusstvennyj intellekt. – 2012. № 4. – P. 420-428.
RESUME
S.V. Sapunov, V.Yu. Pilipenko
On Height of Vertex Identifiers of Vertex Labeled Graphs
Labeled graphs are widely used as models of operational environment of mobile
agents (robots, programs and so on). One of the main problem of operational environment
analysis is agent self location (i.e. distinguishing initial vertex from all other vertices). The
problem of vertex distinguishing on vertex labeled graphs is considered. Two vertices are
called distinguishable if associated languages over the alphabet of labels are different. A
labeled graph is said to be strongly deterministic (or SD-graph) if all vertices in closed
neighborhood of every its vertex have different labels. A linear upper bound of vertex
distinguishing word length equal to half of the number of all vertices is obtained for SD-
graphs. It is shown that at both languages of two different vertices there are distinguishing
words and their lengths are less then number of all vertices. Upper bounds of height of
finite sets of words over the vertex labels alphabet distinguishing a given vertex from other
(i.e. identifiers) are obtained.
Статья поступила в редакцию 26.04.2013.
|
| id | nasplib_isofts_kiev_ua-123456789-85116 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1561-5359 |
| language | Russian |
| last_indexed | 2025-12-07T18:02:15Z |
| publishDate | 2013 |
| publisher | Інститут проблем штучного інтелекту МОН України та НАН України |
| record_format | dspace |
| spelling | Сапунов, С.В. Пилипенко, В.Ю. 2015-07-19T15:12:25Z 2015-07-19T15:12:25Z 2013 О высоте идентификаторов вершин помеченных
 графов / С.В. Сапунов, В.Ю. Пилипенко // Искусственный интеллект. — 2013. — № 3. — С. 444–454. — Бібліогр.: 8 назв. — рос. 1561-5359 https://nasplib.isofts.kiev.ua/handle/123456789/85116 519.7 Рассматривается задача различения вершин помеченного графа по ассоциированным с ними языкам в
 алфавите меток. Показано, что верхняя оценка длины слова, различающего две вершины графа,
 детерминированного по разметке окрестностей вершин, равна половине числа его вершин. Показано
 также, что в языке каждой из любых двух различных вершин есть слово, отличающее одну вершину
 от другой, и его длина меньше числа вершин графа. Найдены оценки высоты конечных множеств
 слов, отличающих одну вершину графа от всех других его вершин (т.н. идентификаторов). Розглядається задача розрізнення вершин позначеного графа за асоційованими з ними мовами в алфавіті
 позначок. Визначено, що верхня оцінка довжини слова, що розрізнює дві вершини графа, детермінованого за
 розміткою околів вершин, дорівнює половині від кількості його вершин. Визначено також, що у мові кожної
 з двох різних вершин є слово, яке відрізняє одну вершину від іншої, і його довжина менша, ніж кількість
 вершин у графі. Знайдено оцінки висоти скінчених множин слів, що відрізняють одну вершину графа від
 інших його вершин (т.з. ідентифікаторів). The problem of vertex distinguishing on vertex labeled graphs is considered. Two vertices are called distinguishable if
 associated languages over the alphabet of labels are different. A linear upper bound of vertex distinguishing word
 length equal to half of the number of all vertices is obtained. It is shown that at both languages of two different
 vertices there are distinguishing words and their lengths are less then number of all vertices. Upper bounds of height
 of finite sets of words over the vertex labels alphabet distinguishing a given vertex from other (i.e. identifiers) are
 obtained. ru Інститут проблем штучного інтелекту МОН України та НАН України Искусственный интеллект Интеллектуальные робототехнические системы О высоте идентификаторов вершин помеченных графов Про висоту ідентифікаторів вершин графів з позначеними вершинами On height of vertex identifiers of vertex labeled graphs Article published earlier |
| spellingShingle | О высоте идентификаторов вершин помеченных графов Сапунов, С.В. Пилипенко, В.Ю. Интеллектуальные робототехнические системы |
| title | О высоте идентификаторов вершин помеченных графов |
| title_alt | Про висоту ідентифікаторів вершин графів з позначеними вершинами On height of vertex identifiers of vertex labeled graphs |
| title_full | О высоте идентификаторов вершин помеченных графов |
| title_fullStr | О высоте идентификаторов вершин помеченных графов |
| title_full_unstemmed | О высоте идентификаторов вершин помеченных графов |
| title_short | О высоте идентификаторов вершин помеченных графов |
| title_sort | о высоте идентификаторов вершин помеченных графов |
| topic | Интеллектуальные робототехнические системы |
| topic_facet | Интеллектуальные робототехнические системы |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/85116 |
| work_keys_str_mv | AT sapunovsv ovysoteidentifikatorovveršinpomečennyhgrafov AT pilipenkovû ovysoteidentifikatorovveršinpomečennyhgrafov AT sapunovsv provisotuídentifíkatorívveršingrafívzpoznačenimiveršinami AT pilipenkovû provisotuídentifíkatorívveršingrafívzpoznačenimiveršinami AT sapunovsv onheightofvertexidentifiersofvertexlabeledgraphs AT pilipenkovû onheightofvertexidentifiersofvertexlabeledgraphs |