О верхней оценке сложности восстановления результирующего графа, полученного сочленением графов-компонент

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

Повний опис

Збережено в:

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

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-124133
record_format	dspace
spelling	irk-123456789-1241332017-09-21T03:03:12Z О верхней оценке сложности восстановления результирующего графа, полученного сочленением графов-компонент Татаринов, Е.А. Анализируются композиции графов из компонент. Композиции представлены правильными и неправильными сочленениями. Предлагается способ и формулы для подсчета верхней оценки сложности восстановления результирующего графа, по известным верхним оценкам сложности восстановления его компонент. Полученные формулы обобщают формулы, полученные ранее для частных видов графов квазиколец и квазициклов. Анал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в. The components compositions of graphs are analyzed. Compositions can be regular and not regular connections. Provides the method and formulas to calculate the upper bound of the resulting graph reconstruction,by the known upper bounds of its components reconstruction. The formulas generalize the formulas obtained earlier for particular types of graphs. 2012 Article О верхней оценке сложности восстановления результирующего графа, полученного сочленением графов-компонент / Е.А. Татаринов // Труды Института прикладной математики и механики НАН Украины. — Донецьк: ІПММ НАН України, 2012. — Т. 25. — С. 224-234. — Бібліогр.: 11 назв. — рос. 1683-4720 http://dspace.nbuv.gov.ua/handle/123456789/124133 519.5 ru Труды Института прикладной математики и механики Інститут прикладної математики і механіки НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
description	Анализируются композиции графов из компонент. Композиции представлены правильными и неправильными сочленениями. Предлагается способ и формулы для подсчета верхней оценки сложности восстановления результирующего графа, по известным верхним оценкам сложности восстановления его компонент. Полученные формулы обобщают формулы, полученные ранее для частных видов графов квазиколец и квазициклов.
format	Article
author	Татаринов, Е.А.
spellingShingle	Татаринов, Е.А. О верхней оценке сложности восстановления результирующего графа, полученного сочленением графов-компонент Труды Института прикладной математики и механики
author_facet	Татаринов, Е.А.
author_sort	Татаринов, Е.А.
title	О верхней оценке сложности восстановления результирующего графа, полученного сочленением графов-компонент
title_short	О верхней оценке сложности восстановления результирующего графа, полученного сочленением графов-компонент
title_full	О верхней оценке сложности восстановления результирующего графа, полученного сочленением графов-компонент
title_fullStr	О верхней оценке сложности восстановления результирующего графа, полученного сочленением графов-компонент
title_full_unstemmed	О верхней оценке сложности восстановления результирующего графа, полученного сочленением графов-компонент
title_sort	о верхней оценке сложности восстановления результирующего графа, полученного сочленением графов-компонент
publisher	Інститут прикладної математики і механіки НАН України
publishDate	2012
url	http://dspace.nbuv.gov.ua/handle/123456789/124133
citation_txt	О верхней оценке сложности восстановления результирующего графа, полученного сочленением графов-компонент / Е.А. Татаринов // Труды Института прикладной математики и механики НАН Украины. — Донецьк: ІПММ НАН України, 2012. — Т. 25. — С. 224-234. — Бібліогр.: 11 назв. — рос.
series	Труды Института прикладной математики и механики
work_keys_str_mv	AT tatarinovea overhnejocenkesložnostivosstanovleniârezulʹtiruûŝegografapolučennogosočleneniemgrafovkomponent
first_indexed	2025-07-09T00:53:41Z
last_indexed	2025-07-09T00:53:41Z
_version_	1837128663325212672
fulltext	ISSN 1683-4720 Труды ИПММ НАН Украины. 2012. Том 25 УДК 519.5 c©2012. Е.А. Татаринов О ВЕРХНЕЙ ОЦЕНКЕ СЛОЖНОСТИ ВОССТАНОВЛЕНИЯ РЕЗУЛЬТИРУЮЩЕГО ГРАФА, ПОЛУЧЕННОГО СОЧЛЕНЕНИЕМ ГРАФОВ-КОМПОНЕНТ Анализируются композиции графов из компонент. Композиции представлены правильными и непра- вильными сочленениями. Предлагается способ и формулы для подсчета верхней оценки сложности восстановления результирующего графа, по известным верхним оценкам сложности восстановле- ния его компонент. Полученные формулы обобщают формулы, полученные ранее для частных видов графов квазиколец и квазициклов. Ключевые слова: восстановление графов, композиции графов, сложность восстановления гра- фов, графы-компоненты. 1. Введение. Анализ глобальных свойств графа одно из направлений, связан- ных с исследованием поведения автоматов в лабиринтах [1, 2]. Наиболее значимы- ми задачами из этой области являются задачи: самолокализации, проверки карты и полного восстановления графа [3]. Наибольший интерес представляет задача пол- ного восстановления графа, поскольку решение этой задачи позволяет получить решение двух других задач. Поэтому задача полного восстановления графа являет- ся важной в теоретическом и прикладном плане. В данной работе рассматривается задача полного восстановления неизвестного графа при помощи блуждающего по нему агента [4]. Ранее был предложен метод восстановления графа при помощи по- строения на его вершинах нумерации явной или неявной [2], предложен Базовый Алгоритм (БА) [6], его модификации и эвристики [7, 8], в данной работе предпола- гается, что агент использует Модификации 1-4 (М1, М2, М3, М4) БА [7], а также модификации БА [8], которые будем здесь называть М5, М5.1, М5.2. Далее будем предполагать, что агент выполняет М5, М5.1, М5.2, когда подсчитывается количе- ство используемых камней, и БА или его модификации – Модификации 1-4. Для Базового Алгоритма, его модификаций и эвристик были получены верхние оценки сложности восстановления графа. Все они выражаются через известные характе- ристики графа и являются достижимыми, однако, они достигаются на отдельных видах графов, множество которых не совпадает со всем классом исследуемых гра- фов. Поэтому нахождение нового способа вычисления верхней оценки сложности восстанволения графа для заданного графа из исследуемого класса является важ- ной и актуальной задачей. В работе предложен новый способ подсчета верхней оценки сложности восста- новления графа, этот способ заключается в том, что рассматривается композиция графов из компонент, для которых верхние оценки сложности уже известны. Эти композиции делятся на правильные и неправильные сочленения. Исследуются изме- нения сложности восстановления результирующего графа в зависимости от харак- 224 О сложности восстановления графа, полученного сочленением графов-компонент тера композиции. Даются формулы подсчета сложности для правильных и непра- вильных сочленений графов. Эти формулы являются обобщением соответствующих формул из [7, 9], полученных для частных видов графов квазидеревьев и квазицик- лов. 2. Необходимые определения и понятия. Пусть K – класс простых, неори- ентированных, связных графов, без петель и ератных ребер. Граф G (V,E) ∈ K, где V – множество вершин, мощности n, а E ⊆ V × V – множество ребер, мощности m. Тройку ((u, v), v) будем называть инцидентором ("точкой прикосновения") ребра (u, v) и вершины v. Множество таких троек обозначим I. Множество L = V ∪E ∪ I назовем множеством элементов графа G. Краской будем называть ресурс, который имеется у агента в неограниченном количестве, а камнем – ресурс, который имеется у агента в единичном экземпляре. Краски и камни образуют множество меток – M , которые могут быть использованы при раскраске элементов графа G. Если элемент графа метится некоторой краской, то предыдущая краска стирается и вместо нее наносится новая. Если элемент гра- фа метят камнем, то существующая на нем краска не уничтожается, а становит- ся "невидимой" до тех пор, пока камень будет находиться на элементе. Функцией раскраски графа G назовем отображение µ : L → M , где M = {w, b, r, 1.., p}, w интерпретируется как белый цвет (краска), r – красный, b – черный, а множество чисел 1, .., p интерпретируется как множество камней. Изоморфизмом графа G и графа H назовем такую биекцию φ : VG → VH , что (u, v) ∈ EG точно тогда, когда (φ(v), φ(u)) ∈ EH . Изоморфные графы равны с точностью до обозначения вершин и раскраски их элементов. Древесными ребрами называются ребра, порождающие дерево поиска при обходе графа в глубину, остальные ребра – обратными. Будем обозначать T ∗ (n) верхнюю оценку временной сложности выполнения алгоритма. Будем говорить, что граф G принадлежит классу Mp c , если он восстанавливается агентом с использованием p – камней и c – красок. 3. Постановка задачи. Пусть задан класс K графов конечных, неориентиро- ванных, без петель и кратных ребер, все элементы которых окрашены краской w. Задан мобильный агент (A), который обладает следующими свойствами. Он пе- редвигается по графу из вершины u в вершину v по ребру (v, u). При этом он может изменить окраску вершин u, v, ребра (v, u), инциденторов ((v, u), v), ((v, u), u) мет- ками из множества M . Находясь в вершине v A воспринимает ("видит") метки всех элементов окрестности O(v) и на этом основании определяет по какому ребру (v, u) он будет перемещаться и как будет перекрашивать элементы из O(v). A облада- ет конечной, неограниченно растущей внутренней памятью, в которой фиксируется результат его функционирования на каждом шаге, и, кроме того, выстраивается представление графа G, вначале неизвестного A, списками ребер и вершин. Требуется разработать такой алгоритм функционирования A (т.е. передвижения по графу и раскраски его элементов), что он, будучи помещен в произвольную вер- шину произвольного неизвестного ему графа G ∈ K, через конечное число шагов построит граф H, изоморфный G, т.е. восстановит G. 225 Е.А. Татаринов 4. Базовый Алгоритм и его модификации. Базовый алгоритм подробно описан в [6], напомним его. Предложенный алгоритм основан на стратегии поис- ка в глубину. Эта стратегия такова [10, 11]: идти “вглубь”, пока это возможно, и возвращаться назад, искать другой путь с еще не посещенными вершинами и не пройденными ребрами. Стратегия поиска в глубину хорошо известна. Известен ряд алгоритмов поиска в глубину для известного графа [10, 11]. Предлагаемая ниже стратегия обладает рядом особенностей. Во-первых, граф G агенту не известен и агент на каждом шаге обладает информацией о цветах элементов из окрестности O (v) рабочей вершины v. Во-вторых, при прохождении вершин графа G агент создает неявную нумерацию пройденных вершин: при первом посещении вершины u она окрашивается красным цветом и ей фактически ставится в соответствие номер, равный значению перемен- ной Сч. На основе этой нумерации и происходит восстановление (распознавание) графа путем построения графа H, изоморфного G. В процессе поиска агент строит неявное дерево поиска в глубину и относительно этого дерева все ребра разделяются на древесные, т.е. принадлежащие этому дереву и окрашиваемые красной краской при первом прохождении по ним, и обратные – не принадлежащие дереву и окра- шиваемые при первом прохождении в черный цвет. Древесные ребра проходятся, по крайне мере, 2 раза и при последнем проходе окрашиваются агентом черной крас- кой. Обратные ребра – проходятся один раз. Древесные ребра распознаются агентом при первом проходе агента по ним. При первом посещении вершины агент метит ее красной краской. Красные вершины графа G, на каждом шаге алгоритма, образуют красный путь. С помощью этого пути распознаются обратные ребра, при проходе в новую вершину красный путь удлиняется, при проходе назад – укорачивается, при распознавании обратного ребра – не изменяется. Вершина, у которой все инцидентные ребра распознаны, красится черным. Алгоритм оканчивает работу, когда красный путь становится пустым, а все вершины черными. Вход: граф G ∈ K неизвестный агенту, все элементы G окрашены в w, агент помещен в произвольную вершину v. Выход: все элементы графа G окрашены в b, агент находится в вершине v, список вершин VH и ребер EH графа H, изоморфного G. Данные: v – рабочая вершина графа G, в которой находится агент, VH , EH – списки вершин и ребер графа H, изоморфного G. – счетчик числа посещенных вершин G. k (1) k (2) ...k (t) – список номеров вершин красного пути, t – длина этого списка, j – счетчик, используемый для восстановления обратных ребер. 1. Сч:= 1; t := 1; k (t) := ; VH := {1} ; EH := ∅; 2. Агент красит: µ (v) := r; 3. if O (v) есть ребро (v, u), у которого µ (u, v) = w then goto 4 else goto 5 4. if O (v) есть ребро (v, u), у которого µ (u, v) = w и µ (u) = µ (v) = r then ВОСТ(v) else ВПЕРЕД(v) 5. if в O (v) есть ребро (v, u), у которого µ ((v, u) , v) = r then do НАЗАД(v) goto 3 end do 226 О сложности восстановления графа, полученного сочленением графов-компонент 6. Агент красит: µ (v) := b; ВПЕРЕД(v) – достраивание дерева и восстановление древесного ребра. При этом новая вершина добавляется в красный путь. НАЗАД(v) – возврат по дереву, когда все ребра, инцидентные текущей вершине, восстановлены. При этом текущая вершина удаляется из красного пути. ВОСТ(v) – восстановление обратного ребра. Базовый Алгоритм был модифици- рован с целью уменьшения верхней оценки сложности восстановления графа, одна- ко требовал использования дополнительных ресурсов или дополнительного анализа окрестности вершины, в которой находится агент. Подробно они описаны в [6-8]. Напомним в чем заключаются эти модификации. Модификация 1 (М1). Агент разделяется на два агента: агент-исследователь (АИ) и агент-экспериментатор (АЭ). АИ передвигается по графу, считывает и изменяет метки на элементах графа, передает сообщения АЭ и на основе разметки элементов графа выбирает дальнейшее направление движения. АЭ по сообщениям от агента АИ строит представление исследуемого графа в виде списка смежности. Модификация 2 (М2). Агент восстанавливает все обратные ребра, инцидент- ные одной вершине красного пути, за один проход по вершинам красного пути. Для этого ему необходим дополнительный камень. Модификация 3 (М3). Обратные ребра вершины восстанавливаются после восстановления всех ее древесных ребер. Модификация изменяет в БА только приоритет выполнения двух процедур ВОСТ(v), ВПЕРЕД(v). Модификация 4 (М4). Множество обратных ребер разбивается на подмноже- ства, ребра из которых восстанавливались за конечное число шагов. Множество вершин разбивается на ординарные и неординарные. Неординарные вершины метятся камнями. При этом используется дополнительно не более чем p камней. Модификация 5 (М5). Агент реализует нумерацию при помощи двух красок и набора попарно различных камней. Эвристика 5.1 (М5.1). Уменьшает число используемых камней. Выделяются два типа вершин для пометки, в которых не используются камни: 1. из которых не видно непомеченных; 2. из которых видно только одну непомеченную вершину; Эвристика 5.2 (М5.2). Уменьшает число используемых камней. Агент метит камнями все вершины, расположенные на расстоянии не более чем k от текущей вершины. При этом камни на расстоянии меньшем k – станут свобод- ными. 5. Правильные и неправильные сочленения. Пусть заданы графы G1 и G2 ∈ K. Сочленнием графов G1 и G2 будем называть такое преобразование над G1 и G2, что в результате будет получен новый граф G ∈ K. Графы G1 и G2 бу- дем называть компонентами результирующего графа G. Таким образом, сочленение 227 Е.А. Татаринов двух графов – это преобразование над графами, результирующий граф которого не выходит из рассматриваемого класса графов K. Преобразования, которые выведут результирующий графа из рассмариваемого класса графов K, не рассматриваются. Правильным сочленением G = G1 ¯ G2 будем называть такое преобразование, что в результате получается граф G, в котором нет циклов, ребра которых принадле- жат обоим компонентам G1 и G2. Если G1 = G2 то, будем рассматривать только те случаи, когда результирующий граф отличается от исходного. Т.е., в результате преобразования граф изменился. При этом сочленение будет правильным, если не образуются новые циклы в результирующем графе. Неправильным сочленением G = G1 ⊗ G2 будем называть такое преобразова- ние, что в результате получается граф G, в котором есть хотя бы один цикл, ребра которого принадлежат обоим компонентам G1 и G2. Если G1 = G2, то будем рас- сматривать только те случаи, когда результирующий граф отличается от исходно- го. Т.е., в результате преобразования граф изменился. При этом сочленение будет неправильным, если образуются новые циклы в результирующем графе. Далее будем предполагать, что для выполнения одного преобразования может быть добавлено константное количество ребер и/или вершин в результирующий граф. В противном случае будем рассматривать композицию преобразования ис- ходного графа на самого себя и одного или нескольких других графов, в результате которого может быть добавлено более чем константное количество ребер и вершин. Свойства правильных и неправильных сочленений сформулируем в виде лемм и теоремы. Лемма 1. Пусть G1, G2 ∈ K и G = G1¯G2, тогда T ∗ (G) ≤ T ∗ (G1)+T ∗ (G2)+ α∗0, где α∗0 – количество шагов, которое необходимо для восстановления вершин и ребер, добавленных в результирующий граф, и которые не содержатся в его ком- понентах G1 и G2. Доказательство. В результате правильного сочленения в результирующем гра- фе может быть часть вершин и ребер, принадлежащих компонентам G1 и / или G2, добавлены дополнительные ребра и вершины, по которым он может попасть только в одну из компонент G1 или G2. Если же при добавлении таких ребер возникли но- вые циклы, ребра которых содержатся в компоненте G1 (G2), то такие случаи будем рассматривать как G = (H ⊗G1)¯G2 (G = (H ⊗G2)¯G1), где H – граф, образо- ванный ребрами, добавленными в результирующий граф G и не содержащимися в его компонентах G1 и G2. Поскольку, сочленение правильное, то в графе не будет новых циклов при вос- становлении обратных ребер и, возможно, будет удалена часть ребер из компонент. Следовательно, при восстановлении графа общее время восстановления будет огра- ничено суммарным временем восстановления каждой компоненты. Действительно, проход по древесным ребрам суммируется, поскольку они проходятся в прямом и обратном направлении и учтены при подсчете T ∗ (G1) и T ∗ (G2). Восстановление об- ратных ребер будет проходить в пределах одной компоненты, в силу правильности сочленения, и так же учитывается при подсчете T ∗ (G1) и T ∗ (G2). Время, необходи- мое для восстановления части G, которая не принадлежит ни G1, ни G2 учитывается 228 О сложности восстановления графа, полученного сочленением графов-компонент в α∗0. Таким образом, общее время восстановления графа G оценивается T ∗ (G) ≤ T ∗ (G1) + T ∗ (G2) + α∗0. Что и требовалось показать. ¤ При этом, если G = G1 ¯G1, то T ∗ (G) ≤ T ∗ (G1) + α∗0. Следствие 1. Пусть Gk ∈ K,k = 1, .., i и G = G1 ¯ G2 ¯ .. ¯ Gi−1 ¯ Gi то- гда T ∗ (G) ≤ ∑i k=1 T ∗ (Gk) + ∑i−1 k=1 α∗k,0, где α∗k,0, k = 1, .., i− 1 – количество шагов, которое необходимо для восстановления вершин и ребер, добавленных в результи- рующий граф, и которые не содержатся в его компонентах Gk и Gk+1. Заметим, что, если G = G1 ¯ G1 ¯ .. ¯ G1 ¯ G1, где в правильном сочленении участвуют i графов G1, то T ∗ (G) ≤ T ∗ (G1) + (i− 1)α∗0. Лемма 2. Пусть G1, G2 ∈ K и G = G1⊗G2, тогда T ∗ (G) ≤ T ∗ (G1)+T ∗ (G2)+ α∗0 + β∗0 , где α∗0 – количество шагов, которое необходимо для восстановления вер- шин и ребер, добавленных в результирующий граф, и которые не содержатся в его компонентах G1 и G2, а β∗0 – количество шагов, которое необходимо для вос- становления новых циклов в G, ребра которых содержатся одновременно в обоих компонентах G1 и G2. Доказательство. При восстановлении результирующего графа G общее время его восстановления может быть ограничено суммарным временем восстановления его компонент. Так как не может быть затрачено меньше времени на восстановле- ние результирующего графа, чем суммарное время восстановления его компонент. С образованием новых циклов, ребра которых принадлежат обоим компонентам, уже будут совсем другие циклы для восстановления обратных ребер. Для учета этих изменений необходимо количество шагов, которое будет учтено в β∗0 . Время, необхо- димое для восстановления части графа G, которая не содержится ни в G1, ни в G2, как и в лемме 1, учитывается в α∗0. Если же эта часть образует новые циклы, ребра которых содержатся в компоненте G1 (G2), то такие случаи будем рассматривать как G = (H ⊗G1) ¯ G2 (G = (H ⊗G2) ¯ G1), где H – граф, образованный частью графа G, которая не содержится ни в G1, ни в G2. Таким образом, общее время восстановления графа G оценивается T ∗ (G) ≤ T ∗ (G1) + T ∗ (G2) + α∗0 + β∗0 . Что и требовалось показать. ¤ При этом, если G = G1 ⊗G1, то T ∗ (G) ≤ T ∗ (G1) + α∗0 + β∗0 . Следствие 2. Пусть Gk ∈ K, k = 1, .., i и G = G1 ⊗ G2 ⊗ .. ⊗ Gi−1 ⊗ Gi тогда T ∗ (G) ≤ ∑i k=1 T ∗ (Gk) + ∑i−1 k=1 ( α∗k,0 + β∗k,0 ) , где α∗k,0, k = 1, .., i − 1 – количество шагов, которое необходимо для восстановления вершин и ребер, добавленных в ре- зультирующий граф, и которые не содержатся в его компонентах Gk и Gk+1, а β∗k,0, k = 1, .., i − 1 – количество шагов, которое необходимо для восстановления новых циклов в G, ребра которых содержатся одновременно в обоих компонентах Gk и Gk+1. Заметим, что, если G = G1 ⊗G1 ⊗ ..⊗G1 ⊗G1, где в неправильном сочленении участвуют i графов G1, то T ∗ (G) ≤ T ∗ (G1) + (i− 1) (α∗0 + β∗0). Лемма 3. Пусть G1 ∈ Mp1 c , G2 ∈ Mp2 c и G = G1 ¯ G2, тогда G ∈ Mp c , где p ≤ p1 + p2 + α∗1, где α∗1 – количество камней, которое необходимо для восстановления 229 Е.А. Татаринов вершин и ребер, которые были добавлены в результирующий граф G, и которые не содержатся в обоих компонентах G1 и G2. Доказательство. Для восстановления части результирующего графа G, которая не содержится в его компонентах G1 и G2, потребуются дополнительные камни. Ко- личество этих камней учтено в α∗1. Если же эта часть графа образует новые циклы, ребра которых содержатся в компоненте G1 (G2), то такие случаи будем рассмат- ривать как G = (H ⊗G1) ¯ G2 (G = (H ⊗G2) ¯ G1), где H – граф, образованный частью графа G, которая не содержится ни в G1 ни в G2. Поскольку сочленение правильное, то не будет циклов содержащих ребра из обо- их компонент G1 и G2. А значит, при пометке вершины камнем не появятся дополни- тельные ребра, которые не дадут освободить камень в тот момент времени, как если бы агент восстанавливал одну из компонент G1 или G2 в отдельности. Следователь- но, при восстановлении каждой компоненты G1 и G2 графа G будет использовано не большее количество камней, чем необходимо для восстановления их в отдельности. Таким образом, суммарное количество камней может быть оценено p ≤ p1 +p2 + α∗1. Что и требовалось показать. ¤ При этом, если G = G1 ¯G1, то p ≤ p1 + α∗1. Следствие 3. Пусть Gk ∈ Mpk c , k = 1, .., i и G = G1¯G2¯ ..¯Gi−1¯Gi, тогда G ∈ Mp c , где p ≤ ∑i k=1 pk + ∑i−1 k=1 α∗k,1, и α∗k,1, k = 1, .., i − 1 – количество камней, которое необходимо для восстановления вершин и ребер, которые были добавлены в результирующий граф G, и которые не содержатся в обоих компонентах Gk и Gk+1. Заметим, что, если G = G1 ¯ G1 ¯ .. ¯ G1 ¯ G1, G1 ∈ Mp1 c , где в правильном сочленении участвуют i графов G1, то G ∈ Mp c , где p ≤ p1 + (i− 1)α∗1. Лемма 4. Пусть G1 ∈ Mp1 c , G2 ∈ Mp2 c и G = G1 ⊗ G2, тогда G ∈ Mp c , где p ≤ p1 + p2 + α∗1 + β∗1 , где α∗1 – количество камней, которое необходимо для восста- новления вершин и ребер, которые были добавлены в результирующий граф G, и которые не содержатся в обоих компонентах G1 и G2, а β∗1 – количество камней, которое необходимо для восстановления новых циклов в G, ребра которых содер- жатся одновременно в обоих компонентах G1 и G2. Доказательство. Для восстановления части результирующего графа G, которая не содержится в его компонентах G1 и G2, потребуются дополнительные камни. Количество этих камней учтено в α∗1. Если же эта часть образует новые циклы, ребра которых содержатся в компоненте G1 (G2), то такие случаи будем рассматривать как G = (H ⊗G1) ¯ G2 (G = (H ⊗G2) ¯ G1), где H – граф, образованный частью графа G, которая не содержится ни в G1, ни в G2. Поскольку сочленение неправильное, то будут циклы содержащие ребра из обоих компонент G1 и G2. А значит, при пометке вершины камнем появятся дополнитель- ные ребра, которые не дадут освободить камень, в тот момент времени, как если бы агент восстанавливал одну из компонент G1 или G2 в отдельности, а следователь- но при восстановлении каждой компоненты G1 и G2 графа G будет использовано большее количество камней, чем необходимо для восстановления их в отдельности. 230 О сложности восстановления графа, полученного сочленением графов-компонент Учитывая в β∗1 дополнительные камни, необходимые для восстановления каждой компоненты в связи с появившимися дополнительными циклами, суммарное коли- чество камей может быть оценено p ≤ p1 +p2 +α∗1 +β∗1 . Что и требовалось показать. ¤ При этом, если G = G1 ⊗G1, G1 ∈ Mp1 c1 , то p ≤ p1 + α∗1 + β∗1 Следствие 4. Пусть Gk ∈ Mpk ck , k = 1, .., i и G = G1 ⊗ G2 ⊗ .. ⊗ Gi−1 ⊗ Gi, тогда G ∈ Mp c , где p ≤ ∑i k=1 pk + ∑i−1 k=1 β∗k,1, где β∗k,1, k = 1, .., i − 1 – количество камней, которое необходимо для восстановления новых циклов в G, ребра которых содержатся одновременно в обоих компонентах Gk и Gk+1. Заметим, что, если G = G1⊗G1..G1⊗G1, G1 ∈ Mp1 c , где в правильном сочленении участвуют i графов G1, то G ∈ Mp c , где p ≤ p1 + (i− 1) (α∗1 + β∗1). Лемма 5. Если в результате удаления ребра из графа G ∈ K, результирующий граф не выходит из класса K, то он может быть представлен в виде правильного сочленение исходного графа G на самого себя. Доказательство. Действительно, при удалении ребра в результирующем гра- фе не могут образоваться новые циклы, следовательно, это правильное сочленение. Таким образом, удаление ребра может быть представлено в виде G¯G. Что и тре- бовалось показать. ¤ Лемма 6. Если в результате добавления ребра в граф G ∈ K, результирующий граф не выходит из класса K, то он может быть представлен в виде правильного или неправильного сочленения исходного графа G на самого себя, или правильного или неправильного сочленения G1, G2 ∈ K. Доказательство. При добавлении ребра в граф G могут, как образоваться но- вые циклы, так и не образоваться. В первом случае добавление ребра может быть представлено в виде G¯G, а во-втором – в виде G⊗G. При добавлении ребра в граф G = G1¯G2 могут, как образоваться новые циклы, ребра которых содержатся в обоих компонентах G1 и G2, так и не образоваться. В первом случае G = G¯G, а во-втором – в виде G = G⊗G. При добавлении ребра в граф G = G1⊗G2 могут, как образоваться новые циклы, ребра которых содержатся в обоих компонентах G1 и G2, так и не образоваться. В первом случае G = G¯G, а во-втором – в виде G = G⊗G. Что и требовалось показать.¤ Теорема 1. Любая операция ∆, которая не выводит результирующий граф из класса K, может быть представлена в виде последовательного применения пра- вильных и неправильных сочленений к множеству графов G1, G2, .., Gi ∈ K. Доказательство. Пусть ∆ некоторая операция, которая не выводит результи- рующий граф из класса K. Результирующий граф G будет состоять из всех или части вершин его компонент (в случае если ∆ унарная операция, то компонентами результирующего графа будет исходный граф). То есть, при выполнении операции результирующий граф содержит в себе все или часть вершин и / или ребер его компонент (часть из них может быть удалена, а часть новых – добавлена). По- скольку рассматриваются связные графы, то по сути своей удаление и добавление 231 Е.А. Татаринов новой вершины неразрывно связано с добавлением или удалением ребра, которым она соединяется с другой вершиной компонент графа. А в случае добавления но- вой вершины, не принадлежащей компонентам графа, она все равно должна быть соединена ребром с уже существующей в графе вершиной. Таким образом, любая операция ∆, которая не выводит результирующий граф из класса K, может быть представлена последовательным добавлением или удалением ребер. По леммам 5 и 6, ∆ может, быть представлена в виде последовательного применения правильных и неправильных сочленений к множеству графов G1, G2, .., Gi. ¤ Следствие 5. Пусть G ∈ K, тогда T ∗ (G) ≤ ∑i k=1 T ∗ (G′ k)+ ∑i−1 k=1 ( α∗k,0 + β∗k,0 ) , где G′ 1, G ′ 2, .., G ′ i ∈ K и G ∈ Mp c , где G′ k ∈ Mpk c , k = 1, .., i и p ≤ ∑i k=1 pk+∑i−1 k=1 ( α∗k,1 + β∗k,1 ) , при этом, если компоненты Gk и Gk+1 дают правильное со- членение и β∗k,l = 0. Доказательство. Поскольку любой граф G ∈ K может быть представлен в виде последовательного выполнения некоторых операций ∆k, k = 1, .., l, над множеством графов G1, G2, .., Gl+1, то каждая пара Gk∆Gk+1 может быть представлена в виде последовательного применения правильных и неправильных сочленений к некоторо- му множеству графов. Следовательно, любой граф G ∈ K может быть представлен в виде последовательного применения правильных и неправильных сочленений к множеству графов G′ 1, G ′ 2, .., G ′ i ∈ K, по теореме 1. ¤ Ранее было показано [7, 9], что для квазидеревьев (класс T k) и квазиколец (класс Sk) сложность восстановления выражается через сложность восстановления их ком- понент. В общем виде это можно сформулировать в виде следующих теорем. Теорема 2. При восстановлении графа G ∈ T k ∪ Sk агентом верхняя оценка временной сложности равна T ∗ (n) = ∑k j=1 T ∗ (nj)+α0+β0, где α0 и β0 могут быть найдены из приведенной ниже таблицы, а T ∗ (nj) – сложность восстановления Gj ∈ K – j-ой компоненты графа G. При этом результирующий граф может быть получен путем выполнения операции сочленения или соединения мостом. G ∈ T k Сочленение Соединение мо- стом α0 β0 α0 β0 БА,М2 0 0 2 ∑k−1 i=1 li 0 G ∈ Sk Сочленение Соединение мо- стом α0 β0 α0 β0 БА 0 O (\|E1\|n) 2 ∑k−1 i=1 li O (\|E1\|n) М2 0 O (\|V1\|n) 2 ∑k−1 i=1 li O (\|V1\|n) В таблице li – длина i-ого моста, E1 и V1 множество вершин компоненты графа, из которой агент начал восстановление результирующего графа G, принадлежащего классу Sk 232 О сложности восстановления графа, полученного сочленением графов-компонент Теорема 3. При восстановлении графа G ∈ T k∪Sk верхняя оценка числа камней равна ∑k j=1 pj + α1 + β1, где α1 и β1 могут быть найдены из приведенной ниже таблицы, а pj – количество камней, необходимых для восстановления Gj ∈ K – j-ой компоненты графа G. При этом результирующий граф может быть получен путем выполнения операции сочленения или соединения мостом. G ∈ T k Сочленение Соединение мо- стом α1 β1 α1 β1 М5,М5.2 0 0 (k − 2)+4 М5.1 0 0 (k − 2)+2 G ∈ Sk Сочленение Соединение мо- стом α1 β1 α1 β1 М5,М5.2 0 p1 (k − 2)+4 p1 М5.1 0 p1 (k − 2)+2 p1 В таблице p1 – количество камней, необходимых агенту для восстановления ком- поненты графа, из которой агент начал восстановление результирующего графа G, принадлежащего классу Sk. Таким образом, G ∈ T k является частным случаем правильного сочленения, а G ∈ Sk – неправильного. 6. Выводы. В работе предложены правильные и неправильные сочленения графов- компонент. Подсчитывается верхняя оценка сложности восстановления результиру- ющего графа, по известным верхним оценкам сложности восстановления компонент, при достаточно широких предположениях о свойствах сочленения. 1. Килибарда Г., Кудрявцев В.Б., Ушчумлич Щ. Коллективы автоматов в лабиринтах // Дискрет- ная математика. – 2003. – Т. 15. – Вып. 3. – С. 3-40. 2. Килибарда Г., Кудрявцев В.Б., Ушчумлич Щ. Независимые системы автоматов в лабиринтах // Дискретная математика. – 2003. – Т. 15. – Вып. 2. – С. 3-39. 3. Dudek G., Jenkin M., Milios E., Wilkes D. Map validation and Robot Self-Location in a Graph-Like World // Robotics and Autonomous Systems. – 1997. – Vol. 22. 4. Dudek G., Jenkin M. Computational principles of mobile robotic // Cambridge Univ. Press. – 2000. – 280 p. 5. Татаринов Е.А. M-нумерация, как метод распознавания графов // Збiрник наукових праць "Питання прикладної математики i математичного моделювання". – Днiпропетровськ: Вид. Днiпр. нац. ун-та. – 2010. – С. 260-272. 6. Грунский И.С., Татаринов Е.А. Распознавание конечного графа блуждающим по нему агентом // Вестник Донецкого университета. Серия А. Естественные науки. – 2009. – Вып. 1. – С. 492- 497. 7. Татаринов Е.А. Базовый алгоритм восстановления графа // Труды ИПММ НАН Украины. – 2010. – T. 21. – С. 492-497. 8. Татаринов Е.А. Восстановление графа при помощи камней //Збiрник наукових праць "Пи- тання прикладної математики i математичного моделювання". – Днiпропетровськ: Вид. Днiпр. нац. ун-та. – 2011. – С. 232-255. 233 Е.А. Татаринов 9. Татаринов Е.А. Сложность восстановления графов, являющихся квазикольцами и квазидере- вьями // Труды ИПММ НАН Украины. – 2011. – T. 23. – С. 202-212. 10. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. – М.: МЦНМО, 2001. – 960 с. 11. Касьянов В.Н., Евстигнеев В.А. Графы в программировании: обработка, визуализация и при- менение. – СПБ.: БХВ – Петербург, 2003. – 1104 с. E.A. Tatarinov About upper bound reconstruction resulting graph obtained graphs-component connections. The components compositions of graphs are analyzed. Compositions can be regular and not regular connections. Provides the method and formulas to calculate the upper bound of the resulting graph reconstruction,by the known upper bounds of its components reconstruction. The formulas generalize the formulas obtained earlier for particular types of graphs. Keywords: graph reconstruction, composition graphs, reconstruction graphs complexity, graph-component. Є.О. Татаринов Про верхню оцiнку складностi вiдновлення результуючого графа, отриманого зчлену- ванням графiв-компонент. Аналiзуються композицiї графiв iз компонент. Композицiї представлено правильними та непра- вильними зчленуваннями. Пропонується спосiб i формули для пiдрахунку верхньої оцiнки склад- ностi вiдновлення результуючого графа, за вiдомими верхнiми оцiнками складностi вiдновлення його компонент. Здобутi формули узагальнюють формули, отриманi ранiше для окремих видiв графiв квазiкiлець i квазiциклiв. Ключовi слова: вiдновлення графiв, композицiї графiв, складнiсть вiдновлення графiв, графи- компоненти. Ин-т прикл. математики и механики НАН Украины, Донецк MDgerelo@yandex.ru Получено 02.12.11 234

О верхней оценке сложности восстановления результирующего графа, полученного сочленением графов-компонент

Репозитарії

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