Сложность восстановления графов, являющихся квазикольцами и квазидеревьями

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

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	2011
Автор:	Татаринов, Е.А.
Формат:	Стаття
Мова:	Russian
Опубліковано:	Інститут прикладної математики і механіки НАН України 2011
Назва видання:	Труды Института прикладной математики и механики
Онлайн доступ:	http://dspace.nbuv.gov.ua/handle/123456789/124064
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:	Сложность восстановления графов, являющихся квазикольцами и квазидеревьями / Е.А. Татаринов // Труды Института прикладной математики и механики НАН Украины. — Донецьк: ІПММ НАН України, 2011. — Т. 23. — С. 202-212. — Бібліогр.: 12 назв. — рос.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-124064
record_format	dspace
spelling	irk-123456789-1240642017-09-20T03:03:26Z Сложность восстановления графов, являющихся квазикольцами и квазидеревьями Татаринов, Е.А. Анализируются модификации алгоритма восстановления графа агентом, перемещающимся по его ребрам, считывающим и изменяющим метки на элементах графа. Найдены и исcледованы операции над графами. Результирующий граф этих операций восстанавливается с использованием числа камней, выражающееся через сумму числа камней, необходимых для восстановления исходных компонент. Аналiзуються модифiкацiї алгоритму вiдновлення графа агентом, що перемiщається по його ребрах, що зчитує i змiнює мiтки на елементах графа. Знайдено та дослiджено операцiї над графами. Результуючий граф цих операцiй вiдновлюється з використанням числа каменiв, що виражається через суму числа каменiв, необхiдних для вiдновлення вихiдних компонент. The modifications of the reconstruction a graph algorithm by agent moving moving through his edges, read and modify marks on the elements of the graph are analyzed. Found and research operations on graphs. The resulting graph of these operations is reconstructed with the use of stone, which is the sum of the number of stones needed to reconstruct the original components. 2011 Article Сложность восстановления графов, являющихся квазикольцами и квазидеревьями / Е.А. Татаринов // Труды Института прикладной математики и механики НАН Украины. — Донецьк: ІПММ НАН України, 2011. — Т. 23. — С. 202-212. — Бібліогр.: 12 назв. — рос. 1683-4720 http://dspace.nbuv.gov.ua/handle/123456789/124064 519.5 ru Труды Института прикладной математики и механики Інститут прикладної математики і механіки НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
description	Анализируются модификации алгоритма восстановления графа агентом, перемещающимся по его ребрам, считывающим и изменяющим метки на элементах графа. Найдены и исcледованы операции над графами. Результирующий граф этих операций восстанавливается с использованием числа камней, выражающееся через сумму числа камней, необходимых для восстановления исходных компонент.
format	Article
author	Татаринов, Е.А.
spellingShingle	Татаринов, Е.А. Сложность восстановления графов, являющихся квазикольцами и квазидеревьями Труды Института прикладной математики и механики
author_facet	Татаринов, Е.А.
author_sort	Татаринов, Е.А.
title	Сложность восстановления графов, являющихся квазикольцами и квазидеревьями
title_short	Сложность восстановления графов, являющихся квазикольцами и квазидеревьями
title_full	Сложность восстановления графов, являющихся квазикольцами и квазидеревьями
title_fullStr	Сложность восстановления графов, являющихся квазикольцами и квазидеревьями
title_full_unstemmed	Сложность восстановления графов, являющихся квазикольцами и квазидеревьями
title_sort	сложность восстановления графов, являющихся квазикольцами и квазидеревьями
publisher	Інститут прикладної математики і механіки НАН України
publishDate	2011
url	http://dspace.nbuv.gov.ua/handle/123456789/124064
citation_txt	Сложность восстановления графов, являющихся квазикольцами и квазидеревьями / Е.А. Татаринов // Труды Института прикладной математики и механики НАН Украины. — Донецьк: ІПММ НАН України, 2011. — Т. 23. — С. 202-212. — Бібліогр.: 12 назв. — рос.
series	Труды Института прикладной математики и механики
work_keys_str_mv	AT tatarinovea složnostʹvosstanovleniâgrafovâvlâûŝihsâkvazikolʹcamiikvaziderevʹâmi
first_indexed	2025-07-09T00:47:39Z
last_indexed	2025-07-09T00:47:39Z
_version_	1837128284732653568
fulltext	ISSN 1683-4720 Труды ИПММ НАН Украины. 2011. Том 23 УДК 519.5 c©2011. Е.А. Татаринов СЛОЖНОСТЬ ВОССТАНОВЛЕНИЯ ГРАФОВ, ЯВЛЯЮЩИХСЯ КВАЗИКОЛЬЦАМИ И КВАЗИДЕРЕВЬЯМИ Анализируются модификации алгоритма восстановления графа агентом, перемещающимся по его ребрам, считывающим и изменяющим метки на элементах графа. Найдены и исcледованы операции над графами. Результирующий граф этих операций восстанавливается с использованием числа камней, выражающееся через сумму числа камней, необходимых для восстановления исходных компонент. Ключевые слова: восстановление графов, агент, сложность алгоритма, блуждание по графу. 1. Введение. В настоящее время интенсивно развивается одно из направле- ний математической кибернетики – теория дискретных динамических систем [1-3]. В общей схеме Глушкова-Летичевского дискретная система представляется как мо- дель взаимодействия управляющей и управляемой систем (управляющего автомата и операционной среды) [4]. Взаимодействие этих систем зачастую представляется как процесс перемещения управляющего автомата по графу (лабиринту) управля- емой системы [1], что привело к обширной и интенсивно развивающейся области исследования поведения автоматов в лабиринтах [1-3]. Общая проблема анализа графа включает в себя ряд частных проблем, важней- шими из которых являются: проблема самолокализации, т.е. определения вершины графа, в которой первоначально находится автомат, проблему контроля графа (кар- ты), т.е. проверки изоморфизма исследуемого графа и заданного графа – эталона (карты), и проблему полного восстановления графа. При этом автомат перемеща- ется по дугам графа от вершины к вершине и воспринимает некоторую локальную информацию о нем и может отмечать элементы графа специальными метками (крас- ками и / или камнями). В данной работе рассматривается задача распознавания конечного, неориенти- рованного графа, без петель и кратных ребер при помощи агента, который переме- щается по нему и изменяет метки на вершинах и ребрах графа при помощи красок и камней [5]. Ранее в работе [6] проводился анализ временной сложности восстановления гра- фа, полученного из нескольких графов путем применения к ним операций сочлене- ния. Данная работа посвящена анализу числа камней, используемых для восстанов- ления такого графа. При этом предполагается, что агент выполняет модификации алгоритма (далее будем обозначать его A) и три его эвристики, предложенные в [7], (далее будем называть их A1, A2, A3, соответственно), который является модифи- кацией "Базового алгоритма" [8]. Найдены оценки числа камней, используемых для восстановления графов из классов квазикольца и квазидеревья. 2. Необходимые определения и понятия. Рассматриваются конечные, неори- 202 Сложность восстановления графов, являющихся квазикольцами и квазидеревьями ентированные графы без петель и кратных ребер. Все такие графы объединим в класс K. Все неопределяемые понятия общеизвестны и их можно найти, например, в [9-11]. Пусть G = (V, E) – граф, у которого V – множество вершин, E – множество ребер, E ⊆ V × V , мощности n и m, соответственно. Тройку ((u, v) , v) будем назы- вать инцидентором ("точкой прикосновения") ребра (u, v) и вершины v. Множество таких троек обозначим I. Множество L = V ∪E ∪ I назовем множеством элементов графа G. Окрестностью O (v) вершины v будем называть множество элементов гра- фа, состоящее из вершины v, всех вершин u смежных с v, всех ребер (v, u) и всех инциденторов ((v, u) , v) , ((v, u) , u). Последовательность u1, u2, .., uk попарно смежных вершин, где все вершины раз- личны, будем называть путем длины k в графе G. При u1 = uk этот путь называ- ется циклом. Краской будем называть ресурс, который имеется в неограниченном количестве, а камнем – ограниченный ресурс, все камни попарно различны и пере- нумерованы. Камень устанавливается в вершине и может быть снят с нее, а краской метят вершины и инциденторы ребер. Краска в отличие от камня может быть толь- ко заменена другой краской. При этом краска, на вершине в которой установлен камень, становится невидимой до тех пор, пока камень не будет снят. Для каждого камня существует счетчик количества непомеченных ребер, кото- рые есть в окрестности текущей вершины. Счетчик камня уменьшается на единицу, когда агент "видит" в окрестности текущей вершины вершину, помеченную этим камнем. После обнуления счетчика камня этот камень станет свободным, агент пе- рейдет в вершину, снимет камень, вершину пометит краской b и возвращается об- ратно. Агент использует для уставновки в вершине свободный на данный момент ка- мень наименьшим номером. С камнем ассоциируется M -номер [11], который неявно был присвоен вершине в момент установки в ней данного камня. Такая ассоциация сохраняется до тех пор, пока камень не станет свободным. Пару (G, v), где G – граф, а v – его вершина, назовем правильной, если удаление вершины v и всех инцидентных ей ребер не нарушает связности полученного графа G. То есть v не является точкой сочленения в смысле [12]. В противном случае пару назовем неправильной. Сочленение двух графов [6] осуществляется отождествлением двух их вершин. В графах G1 и G2 выбираются соответственно вершины v1, v2 и отождествляются в одну вершину v. Если в результате отождествления образовались кратные ребра или петли, кратные ребра заменяются одним, а петли – удаляются из результирую- щего графа. Вершину v назовем вершиной сочленения. Сочленние графов G1 и G2 будем обозначать G1 ⊙ G2. Подграфы G1 ⊙ G2 изоморфные графам G1 и G2 будут компонентами сочленения. Пусть задан класс K ′ ⊆ K, рассмотрим класс T k графов, полученных из G1, .., Gk ∈ K ′ последовательным применением сочленения к G1, .., Gk: H1 = G1 ⊙ G2; H2 = H1 ⊙ G3; G = Hk−1 ⊙ Gk. Граф G назовем квазидеревом, если он не содержит простых циклов, которые 203 Е.А. Татаринов содержат одновременно вершины из Gi и Gj , i 6= j. Пусть задан класс K ′ ⊆ K, рассмотрим класс Sk графов, полученных из G1, .., Gk ∈ K ′ последовательным применение операции сочленения к G1, .., Gk и отож- дествлением двух вершин компонент G1 и Gk: H1 = G1 ⊙ G2; H2 = H1 ⊙ G3, при этом в графе H1 вершина для отождествления выбирается из комопненты G2; Hk−1 = Hk−2 ⊙ Gk, при этом в графе Hk−2 вершина для отождествления выби- рается из комопненты Gk−1; Результирующий граф G получается отождествлением G1 ⊙ Gk. Будем называть квазикольцом. Связный ациклический граф, степень вершин которого не более двух, будем на- зывать линией. Ясно, что степень один могут иметь только две его вершины, кото- рые будем называть концами линии. Будем говорить, что граф принадлежит классу Mp c , если при его восстановлении агент использует p – камней и c – красок. 3. Постановка задачи. Пусть задан класс K графов: конечных, неориентиро- ванных, без петель и кратных ребер, – все элементы которых окрашены краской w. Задан агент,который может перемещаться по исследуемому графу из вершины по ребру, соединяющему их, и изменять метки на элементах графа так, как это было описано в пункте 2. Агент помещается в произвольную вершину априори неизвест- ного ему графа G ∈ K. Агенту требуется восставновить граф G, т. е. построить граф H, изоморфный графу G, с точностью до меток на элементах графов. 4. Стратегия восстановления графа с использованием камней. Алго- ритм A восстановления графа при помощи камней подробно описан в [7]. Алгоритм A основан на методе обхода графа в глубину [9, 10]. Этот метод модифицирован с учетом того, что агенту граф изначально неизвестен, агент может воспринимать локальную информацию о графе и агент строит на вершинах графа нумерацию в по- рядке посещения вершин (M – нумерация)[11]. Агент реализует нумерацию неявно, при помощи набора попарно различных камней. В процессе обхода графа в глубину агент строит неявное дерево поиска в глубину, относительно которого ребра графа разбиваются на два множества: древесные и об- ратные. Древесные ребра проходятся два раза – в прямом (процедура ВПЕРЕД (v)) и обратном направлении (процедура НАЗАД (v)). При первом прохождении по дре- весному ребру оно восстанавливается в графе G и один из его инциденторов метить- ся краской r. После перехода по ребру агент устанавливает в новой непомеченной вершине свободный камень и восстанавливает все обратные ребра текущей верши- ны. Для восстановления обратных ребер агенту не требуется переходить по ним, поскольку, находясь в текущей вершине, помеченной некоторым камнем, он увидит камень, установленный в вершине, с которой смежно восстанавливаемое обратное ребро. Зная эти два камня, агент может однозначно определить ассоциируемые с ними неявные M -номера и восстановить обратное ребро. При установке в вершине 204 Сложность восстановления графов, являющихся квазикольцами и квазидеревьями камня она добавляется в помеченный путь, при пометке ее краской b она удаляется из помеченного пути. Алгоритм останавливается, когда помеченный путь становиться пустым, а все вершины помечены краской b. Данный алгоритм можно модифицировать с целью уменьшения количества кам- ней, используемых при восстановлении графа или же сократить время анализа окрестности вершины. Первая модификация, реализуется алгоритмом A1.Она заключается в том, что агент анализирует вершину, в которой собирается установить камень. Выделяется два вида вершин, для которых нет необходимости использовать камни: 1) вершины из которых не видно непомеченных вершин; 2) вершины, из которых видно только одну непомеченную вершину. Вторая модификация реализуется алгоритмом A2. Она заключается в том, что для увеличения области восприятия агента, т. е. метятся камнями все вершины из окрестности текущей вершины. При этом часть камней будет освобождаться, так как за один шаг будет исследовано большее количество вершин. Третья модификация реализуется алгоритмом A3. Она заключается в том, что камни, установленные в вершинах со cтепенью, большей чем D, не снимаются. D – заранее известная константа. При этом агент анализирует только вершины со степенью, меньше либо равной D. 5. Восстановление квазидеревьев и квазиколец, полученных при по- мощи сочленения. Сформулируем результаты для алгоритма из [7], аналогичные результатам, полученным в [6]. А именно, покажем, что при восстановлении гра- фов из классов T k и Sk число камней, есть сумма числа камней используемых для восстановления его компонент. Пусть G получен сочленением двух правильных пар. Покажем, что при восста- новлении G агент либо сначала восстанавливает одну компоненту, а затем другую, либо восстанавливает часть первой компоненты, переходит в другую компоненту и не возвращается в первую до тех пор, пока вторая не будет полностью восстановле- на. Лемма 1. Пусть изначально агент помещается в вершину v графа G ∈ K такую, что (G, v) – правильна пара. Тогда при выполнении агентом алгоритма A,A1−A3, агент перейдет в вершину v после того, как восстановит все вершины графа G. Доказательство. Доказательство от противного. Предположим, что агент вос- становил часть графа G и вернулся в вершину v, при выполнении процедуры НАЗАД(v). При этом из вершины v агент может попасть в ранее не посещенные вершины. Так как (G, v) – правильная пара, то в силу связности (G − v) из v существует путь в некоторую вершину u, которая смежна, хотя бы с одной из ранее посещенных вер- шин x, которая отлична от v. Это противоречит тому, что агент придерживается стратегии обхода графа в глубину. Поскольку при такой стратегии агент из верши- ны x перешел бы в вершину u, а не наоборот. Полученное противоречие доказывает лемму. ¤ 205 Е.А. Татаринов Теперь покажем, что число камней, используемых для восстановления графа G, будет равно сумме числа камней, используемых для восстановления каждой из его компонент. Лемма 2. Пусть (G1, v1) и (G2, v2) – правильные пары и G1 ∈ Mp1 2 , G2 ∈ Mp2 2 , тогда G, полученный сочленением вершин v1 и v2 этих двух графов, принадлежит классу Mp 2 , где p = p1 + p2. Доказательство. Рассмотрим всевозможные варианты начала выполнения аген- том восстановления G. Пусть u1 вершина сочленения G1 и G2. Существует три раз- личных начальных положения агента: 1) агент попал в вершину u1; 2) агент попал в вершину v1 ∈ V (G1) \ {u1}; 3) агент попал в вершину v2 ∈ V (G2) \ {u1}. Рассмотрим эти случаи. 1. Агент метит вершину u1 камнем номер 1 и добавляет ее в помеченный путь. После чего он начинает восстанавливать компоненту G1, используя камни, учтенные при подсчете p1. После этого агент, либо попадет в вершину v′1 ∈ V (G1) \ {u1}, либо в вершину v′2 ∈ V (G2) \ {u1}. Предположим, что он попал в v′1 (v′2). Далее агент будет восстанавливать вершины графа G и ребра G1 (G2). Так как (G1, v1) ((G2, v2)) правильная пара, то по лемме 1 агент не уйдет из компоненты G1 (G2), пока полностью ее не восстановит. При этом он будет использовать камни, которые были учтены при подсчете p1 (p2). Следовательно, агенту потребуется p1+p2 камней. 2. Агент пометит вершину v1 камнем номер 1 и добавит в помеченный путь. После чего он начинает восстанавливать вершины и ребра компоненты G1. В этом случае существует два различных варианта дальнейшего выполнения алгоритма. 2.1. Агент восстановит полностью компоненту G1, используя при этом p1 камней, и только после этого попадет в вершину сочленения u1, пометит ее камнем, который уже был учтен при подсчете p2. После чего он восстановит все вершины и ребра ком- поненты с G2, используя камни, учтенные при подсчете p2. Следовательно, агенту потребуется p1 + p2 камня. 2.2. Агент восстановит часть компоненты G1, используя при этом p1 камней. По- сле чего он попадет в вершину сочленения u1, пометит ее камнем i. После чего агент переходит в компоненту G2. Так как (G2, v2) правильная пара, то по лемме 1 он пол- ностью его восстанавливает, используя p2 камней. При этом камень номер i уже был учтен при подсчете p1. Даже если этот камень будет не свободным при восстановле- нии компоненты G2, то это не увеличит число камней p2, которые агент использует для ее восстановления. После восстановления компоненты G2 агент возвращается в u1 и восстанавливает оставшуюся часть G1, используя p1 камней. Следовательно, агенту потребуется p1 + p2 камней. 3. Этот случай полностью аналогичен случаю 2. Воспользуемся рассуждениями из пункта 2. ¤ Леммы 1, 2 обобщим на случай сочленения k правильных пар. Теорема 1. Если граф G получен последовательным отождествлением в одну 206 Сложность восстановления графов, являющихся квазикольцами и квазидеревьями вершин v1, .., vk правильных пар (G1, v1),..,(Gk, vk), где Gi ∈ Mpi 2 , i = 1, .., k, то G ∈ Mp 2 , где p = ∑k i=1 pi. При этом порядок восстановления компонент не имеет значения. Доказательство. Пусть v вершина сочленения всех правильных пар. Если агент помещен в вершину v, то он, согласно лемме 1, перейдет в эту вершину v только после того, как полностью восстановит одну из компонент. Следовательно, агент начнет последовательно восстанавливать компоненты Gi, используя pi камней, где i = 1, .., k. Тогда согласно лемме 2 G ∈ Mp 2 , где p = ∑k i=1 pi вне зависимости от порядка восстановления компонент. Если же агент будет помещен в компоненту Gj , в вершину отличную от вершины v, то возможны два варианта выполнения агентом восстановления графа: 1) агент полностью восстановит компоненту Gj и переходит в вершину сочленения v; 2) агент восстанавливает часть компоненты Gj , переходит в вершину сочленения v, а из нее в вершину vi компоненты Gi и i 6= j. 1. В этом случае агент из вершины сочленения v переходит в вершину vi компо- ненты Gi и i 6= j. Поскольку все компоненты правильные, то согласно лемме 1 агент не перейдет в вершину сочленения v при выполнении процедуры НАЗАД(v) до тех по пор, пока он не восстановит все ребра и вершины компоненты Gj . После чего он при выполнении процедуры НАЗАД(v) переходит в вершину сочленения v, а из нее в следующую не восстановленную компоненту. Следовательно, агент последова- тельно восстановит компоненты Gi, где i = 1, .., k и i 6= j, а G ∈ Mp 2 , где p = ∑k i=1 pi вне зависимости от порядка восстановления компонент. 2. В этом случае агент из вершины сочленения v переходит в вершину vi ком- поненты Gi и i 6= j. Поскольку все компоненты правильные, то согласно лемме 1 агент не перейдет в вершину сочленения v при выполнении процедуры НАЗАД(v) до тех по пор, пока он не восстановит все ребра и вершины компоненты Gj . После чего он при выполнении процедуры НАЗАД(v) переходит в вершину сочленения v. Далее агент либо возвращается в компоненту Gj , либо переходит в следующую не восстановленную компоненту. В первом случае агент восстановит оставшуюся часть компоненты Gj (по лемме 1 в силу того, что Gj правильная компонента). Во втором случае, агент восстановит полностью еще одну компоненту. Следовательно, агент восстановит часть компоненты Gj , затем некоторое число компонент Gi, после чего восстановит оставшуюся часть компоненты Gj , а затем – оставшиеся компоненты Gi, где i = 1, .., k и i 6= j, а G ∈ Mp 2 , где p = ∑k i=1 pi вне зависимости от порядка восстановления компонент. ¤ Следствие 1. Граф G, полученный сочленением двух графов G1 и G2, где G1 ∈ Mp1 2 и G2 ∈ Mp2 2 , принадлежит классу Mp 2 , где p = p1+p2 при выполнении агентом алгоритмов A, A1 – A3. Любой граф Gi i = 1, 2, можно представить в виде сочленения правильных пар( v1, G 1 i ) ,.., ( vki , G ki i ) , где Gj i j = 1, .., ki подграфы графа Gi. Тогда G будет сочлене- нием правильных пар компонент G1 и G2. Из теоремы 1 получаем справедливость следствия. 207 Е.А. Татаринов Следствие 2. Пусть G ∈ T k получен последовательным сочленением G1, ..., Gk, где Gj ∈ M pj 2 , j = 1, .., k. Тогда G ∈ Mp 2 где p = ∑k i=1 pi. При этом pj определяются выполняемым агентом алгоритмом A, A1 – A3. Докажем следствие 2 методом математической индукции. При k = 1. В этом случае G = G1, соответственно p = p1 и следствие справедли- во. Пусть при k = j следствие справедливо, тогда p = ∑k i=1 pi. Покажем, что при k = j + 1 выполняется p = ∑k i=1 pi. Поскольку в этом случае результирующий граф получается путем сочленения графа G′,полученного j после- довательными сочленениями графов G1, .., Gj , и графа Gj+1, то для них справедливо следствие 1, тогда p = ∑k i=1 pi. Доказанные выше утверждения показывают, что число камней используемых при восстановлении графа с агентом, выполняющим алгоритмы A, A1 – A3, опреде- ляется формулой p = ∑k j=1 pj , где pj – число камней, используемых для восстанов- ления компоненты Gj . Другим классом графов, у которых число камней есть функцией числа камней компонент, является класс квазикольца. При восстановлении графа G ∈ Sk, для простоты рассуждений, будем предпо- лагать, что агент начинает восстановление из вершины компоненты G1. Теорема 2. Пусть G ∈ Sk получен последовательным сочленением G1, ..., Gk, где Gj ∈ M pj 2 , j = 1, .., k. тогда G ∈ Mp 2 где p = ∑k i=1 pi + p1. При этом pj определя- ются выполняемым агентом алгоритмом A, A1 – A3, Доказательство. Для графа G′ ∈ T k выполняется следствие 2, тогда G′ ∈ Mp 2 , где p = ∑k j=1 pj . Однако, в силу того, что G1 и Gk сочленяются, то агент может пройти по всем Gj , где j = 1, .., k, так что все ∑k j=1 pj будут заняты, и после то- го, как он перейдет из вершин компоненты Gk в вершину сочленения uk−1, метит камнем номер i, который был учтен при подсчете pk, после этого агент переходит в вершину компоненты G1. Поскольку камень номер i может остаться не свободным, то для восстановления оставшейся части вершин компоненты G1 агенту потребуется дополнительно не менее p1 камней, так как из вершины сочленения uk−1 агент мо- жет попасть в компоненты G1, в которой агент до этого еще не был. Следовательно, всего потребуется не более ∑k j=1 pj + p1 камней. ¤ Доказанные выше утверждения показывают, что число камней, используемых при восстановлении графа агентом, выполняющим A, A1, A2, определяется форму- лой ∑k i=1 pi + p1. 6. Восстановление квазидеревьев и квазиколец, полученных соедине- нием компонент мостом. Рассмотрим сочленение двух графов G1 и G2, когда их вершины v1 и v2 не отождествляются в одну, а соединяются ребром. Такое ребро является мостом в смысле [12]. Мы будем рассматривать соединение двух графов не только одним ребром (мостом),но и соединение двух графов линией. В этом случае будем говорить, что графы соединены мостом длины l, где l – количество вершин в линии. Ясно, что при соединении графов G1 и G2 мостом длины l происходит 208 Сложность восстановления графов, являющихся квазикольцами и квазидеревьями сочленение линии длины l с графами G1 и G2. При этом один конец линии v отож- дествляется с вершиной v1 графа G1, а второй конец линии u отождествляется с вершиной v2 графа G2. При этом, если один из соединяемых графов был полу- чен соединением двух других графов при помощи моста, то при его сочленении с мостом может быть выбрана любая вершина. Т.е. конец моста может сочленять- ся с вершиной, которая принадлежала мосту при его построении. Следовательно, если при построении квазидеревьев и квазиколец заменить операцию сочленения на операцию соединения через мост некоторой длины l, то получим квазикольца и квазидеревья, для которых будут справедливы аналогичные леммы следствия и теоремы. Сформулируем результаты, аналогичные следствиям 1 и 2 и теоремам 1 и 2, для случая, когда операция сочленения заменяется операцией соединения графов мостом длины l. Лемма 3. При выполнении агентом алгоритмов A, A2 на графе G вида линия агент использует не более трех различных камней и две различные краски, т.е. G ∈ M3 2 . Доказательство. Рассмотрим худший случай, когда агент попадает в вершину, не являющуюся концом линии. Тогда, согласно алгоритму, в ней он установит ка- мень номер 1, и перейдет в соседнюю вершину, и установит в ней камень номер 2, после чего перейдет в соседнюю вершину и пометит ее камнем номер 3, и при этом камень номер 2 станет свободным, а вершину агент пометит краской b. После пе- рехода в соседнюю, не помеченную вершину, агент пометит ее камнем 2, при этом камень номер 3 станет свободным, а вершину агент пометит b. И так далее, чередуя использование камней номер 2 и номер 3, агент дойдет до конца линии, а потом вернется в начальную вершину, и так же, чередуя использование камней номер 2 и 3, дойдет до другого конца линии и тем самым восстановит граф с использованием только трех красок. ¤ Лемма 4. При выполнении агентом алгоритма A1 на графе G агент использу- ет один камень и две различные краски, т.е. G ∈ M1 2 . Доказательство. Воспользуемся рассуждениями леммы 3, заметив, что верши- ны, которые агент метит камнями номер 2 и номер 3, будут вершинами, из которых будет видно только одну не помеченную вершину. Следовательно, агенту не потребу- ются камни для их пометки, а только один камень для пометки начальной вершины. ¤ Лемма 5. Пусть агент выполняет алгоритмы A, A1, A2, на графе G, который является деревом, у которого i вершин имеют степень больше двух. Тогда G ∈ Mp 2 , где p = i + 3 для A, A2 и p = p + 1 для A1. Доказательство. Для простоты рассуждений будем предполагать, что такое де- рево получается из графа вида линия путем его сочленения с i графами lj вида ли- ния j = 1, .., i. Наихудшим случаем является случай, когда длины этих линий больше трех и они сочленяются путем отождествления их вершин с разными вершинами ис- ходного графа, поскольку, при этом установленные в них камни не освобождаются сразу после установки. Согласно лемме 3 при выполнении агентом A агент использу- 209 Е.А. Татаринов ет три различных камня для восстановления исходной линии. Согласно лемме 4 при выполнении агентом эвристики A1 агент использует один камень для восстановле- ния исходной линии l. Согласно лемме 4 при выполнении агентом эвристики A2 агент использует три различных камня для восстановления исходной линии. Во всех трех случаях камни используются повторно. Повторное использование камней обуслав- ливается тем, что они либо освобождаются, либо вершины относятся к вершинам специального вида (эвристика A1). В полученном графе будет i вершин, которые не будут принадлежать к вершинам особого вида, камни, установленные в них, не будут сразу освобождаться. Для восстановления вершин линий lj j = 1, .., i агент будет использовать камни, которые использовались при восстановлении исходной линии l, и на момент начала восстановления добавленной линии lj j = 1, .., i стали свободны. Таким образом, в i вершинах появятся камни, которые не освободятся сразу же после установки. Для A, A1 камни не будут освобождаться, поскольку сте- пень вершины будет больше двух. То есть, после перехода в следующую вершину в окрестности предыдущей остается одна не посещенная вершина и камень не осво- бодится. В случае выполнения эвристики A2 при пометке 1− окрестности вершины степени больше двух в силу тех же причин один камень останется не свободным. Следовательно, агенту потребуется i дополнительных камней для всех трех случаев. ¤ Теорема 3. Пусть G ∈ T k, а Gj ∈ M pj 2 , где j = 1, .., k и вместо операции сочленения используется операция соединения графов при помощи моста. Тогда G ∈ Mp 2 , при выполнении агентом алгоритмов A, A2 p = ∑k j=1 pj + p1 + (k− 2) + 4, а при выполнении алгоритма A1 – p = ∑k j=1 pj + p1 + (k − 2) + 2. Доказательство. В данном случае граф G получен сочленением компонент Gj j = 1, .., k и k − 1 мостов, которые могут образовывать деревья. В худшем случае будет образовано одно дерево с k − 2 вершинами степени больше двух или же бу- дет образовано большее количество деревьев, но количество вершин в них степени больше двух не превзойдет k − 2. Следовательно, по лемме 5 для восстановления такого или каждого из таких деревьев с i вершинами степени больше двух потребует дополнительно камней i + 3 при выполнении агентом A, A2 и i + 3 камня при вы- полнении агентом A2. При этом дополнительные камни, которые используются для восстановления вершин степени меньше трех будут использоваться повторно. При этом, если агент изначально помещается в вершину, принадлежащую одному из мо- стов, то в начале восстановления один камень останется не свободным, а остальные камни, будут повторно использоваться при восстановлении вершин степень меньше трех. Так как, по следствию 2, верхняя оценка числа камней, используемых агентом, будет равна сумме верхних оценок всех компонент. Тогда, всего агенту потребуется при выполнении алгоритмов A, A2 p = ∑k j=1 pj + p1 + (k − 2) + 3 + 1 камней, а при выполнении алгоритмов A1 – p = ∑k j=1 pj + p1 + (k − 2) + 1 + 1 камней. ¤ Теорема 4. При выполнении агентом алгоритмов A, A1, A2 на G ∈ Sk, где Gj ∈ M pj 2 , G ∈ Mp 2 , где j = 1, .., k и вместо операции сочленения используется операция соединения графов при помощи моста. Тогда G ∈ Mp 2 , при выполнении 210 Сложность восстановления графов, являющихся квазикольцами и квазидеревьями агентом A, A2 – p = ∑k j=1 pj+p1+(k−2)+4, а при A1 – p = ∑k j=1 pj+p1+(k−2)+2. Доказательство. В данном случае граф G получен сочленением компонент Gj j = 1, .., k и k − 1 мостов, которые могут образовывать деревья. В худшем случае будет образовано одно дерево с k − 2 вершинами степени больше двух или же бу- дет образовано большее количество деревьев, но количество вершин в них степени больше двух не превзойдет k − 2. Следовательно, по лемме 5 для восстановления такого или каждого из таких деревьев с i вершинами степени больше двух потре- буется дополнительно камней i + 3 при выполнении агентом A, A2, а для A1 – i + 1 камней, при этом дополнительные камни, которые используются для восстановле- ния вершин степени меньше трех будут использоваться повторно. При этом, если агент изначально помещается в вершину, принадлежащую одному из мостов, то в начале восстановления один камень останется не свободным, а остальные камни, будут повторно использоваться при восстановлении вершин степень меньше трех. Так как, по теореме 2 верхняя оценка числа камней, используемых агентом, будет равна сумме верхних оценок всех компонент и дополнительно числа камней, исполь- зуемых для восстановления начальной компоненты. Тогда, всего агенту потребуется при выполнении алгоритмов A, A2 p = ∑k j=1 pj + p1 + (k − 2) + 3 + 1 камней, а при выполнении алгоритма A1 – p = ∑k j=1 pj + p1 + (k − 2) + 1 + 1 камней. ¤ Доказанные выше утверждения обобщают результаты, полученные для операции сочленения. 7. Выводы. Найдены оценки числа камней, используемых для восстановления графов из классов квазикольца и квазидеревья. Для квазидеревьев число камней используемых агентом, выражается через сумму числа камней, используемых для восстановления компонент. Для квазиколец число камней, используемых агентом, – через сумму числа камней, используемых для восстановления компонент и дополни- тельного числа камней, используемых для восстановления компоненты, из которой агент начал восстановления графа. Результаты, полученные для классов T k Sk, обобщаются для случая, когда со- членение заменяется соединением двух графов мостом. Для операции соединения двух графов мостом получены результаты, аналогичные результатам для операции сочленения. 1. Килибарда Г., Кудрявцев В.Б., Ушчумлич Щ.Коллективы автоматов в лабиринтах // Дискрет- ная математика. – 2003. – Т. 15, вып. 3. – С. 3–40. 2. Килибарда Г., Кудрявцев В.Б., Ушчумлич Щ. Независимые системы автоматов в лабиринтах // Дискретная математика. – 2003. – Т. 15, вып. 2. – С. 3–39. 3. Килибарда Г., Кудрявцев В.Б., Ушчумлич Щ. О поведении автоматов в лабиринтах // Дис- кретная математика. – 1992. – Т. 4, вып. 3. – С. 3–28. 4. Кудрявцев В.Б., Алешин С.В., Подколзин А.С. Введение в теорию автоматов. – М: Наука, 1985, – 320 с. 5. Dudek G., Jenkin M. Computational principles of mobile robotic // Cambridge Univ. Press. – 2000. – 280 p. 6. Татаринов Е.А. Базовый алгоритм восстановления графа // Труды ИПММ НАН Украины. – 2010. – T. 21. – С. 492-497. 7. Татаринов Е.А. Восстановление графа при помощи камней // Збiрник наукових праць "Пи- 211 Е.А. Татаринов тання прикладної математики i математичного моделювання". – Днiпропетровськ: Вид. Днiпр. нац. ун-та. – 2011. – С. 232-255. 8. Грунский И.С., Татаринов Е.А. Распознавание конечного графа блуждающим по нему агентом // Вестник Донецкого университета. Серия А. Естественные науки. – 2009. – Вып. 1. – С. 492- 497. 9. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. – М.: Мир, 1979. – 536 с. 10. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. – М.: МЦНМО, 2001. – 960 с. 11. Касьянов В.Н., Евстигнеев В.А. Графы в программировании: обработка, визуализация и при- менение. – СПБ.: БХВ – Петербург, 2003. – 1104 с. 12. Харари Ф. Теория графов. – М.: Мир, 1973. – 300 с. E.A. Tatarinov Basic algorithm for reconstructing a finite graph. The modifications of the reconstruction a graph algorithm by agent moving moving through his edges, read and modify marks on the elements of the graph are analyzed. Found and research operations on graphs. The resulting graph of these operations is reconstructed with the use of stone, which is the sum of the number of stones needed to reconstruct the original components. Keywords: graph reconstraction, agent, complexity of the algorithm, move on graph. Є.О. Татаринов Складн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ть алгоритму, блукання по графу. Ин-т прикл. математики и механики НАН Украины, Донецк MDgerelo@yandex.ru Получено 02.12.11 212

Сложность восстановления графов, являющихся квазикольцами и квазидеревьями

Репозитарії

Схожі ресурси