Содержание к диссертации
Введение
ГЛАВА 1. Определение, понятия, свойства предфрактальных графов и их затравок .10
1.1. Основные определения и понятия 10
1.2. Свойства предфрактальных графов, порожденных регулярными затравками 12
1.3. Свойства затравок предфрактальных графов 20
1.4. Свойства предфрактальных графов при несмежности старых ребер 25
1.5. Свойства предфрактальных графов при сохранении смежности старых ребер 27
ГЛАВА 2. Метрические свойства предфрактальных графов 35
2.1. Основные метрические характеристики графов 35
2.2. Оценки диаметра предфрактальных графов, порожденных затравками, удовлетворяющими условию Оре 36
2.3. Оценки радиуса предфрактальных графов, порожденных затравками, удовлетворяющими условию Оре 38
ГЛАВА 3. Алгоритмы распознавания предфрактальных графов ...42
3.1. Алгоритм распознавания предфрактальных графов с регулярной n-вершинной затравкой степени не менее n/2 43
3.2. Алгоритмы распознавания предфрактальных графов, в траектории которых старые ребра не смежны 53
3.3. Алгоритмы распознавания предфрактальных графов, в траектории которых смежность старых ребер сохраняется 67
3.4. Алгоритм распознавания предфрактальных графов с п -вершинной затравкой, 2и-1
степень каждой вершины которой не менее 84
Заключение 96
Список сокращений и условных обозначений 98
Литература 99
- Свойства предфрактальных графов, порожденных регулярными затравками
- Свойства предфрактальных графов при несмежности старых ребер
- Оценки диаметра предфрактальных графов, порожденных затравками, удовлетворяющими условию Оре
- Алгоритмы распознавания предфрактальных графов, в траектории которых старые ребра не смежны
Введение к работе
Диссертация посвящена исследованию и анализу основных свойств предфрактальных графов, а также разработке и анализу алгоритмов распознавания предфрактальных графов.
Актуальность темы. Любые сложные системы, такие как информационные, энергетические, управленческие, претерпевают с течением времени определенные, вызванные внешними причинами, изменения. Довольно часто структуры таких систем уместно представлять в виде графа. В работах F. Harari (1973), С. Berge (1962), B.A. Емеличева (1990) и других рассматриваются операции над графами, такие как объединение, соединение, произведение, композиция, стягивание дуги и пр. С помощью этих операций можно описать изменения, происходящие в структурах сложных систем. Структуры систем могут претерпевать как разовые, так и регулярные изменения. Обобщением случая регулярных изменений является понятие структурной динамики.
Общеизвестным сценарием структурной динамики является рост структуры — регулярное появление элементов и связей в структуре системы. В некоторых случаях для описания роста структуры используется перечень правил, причем такие правила могут допускать элемент случайности.
В настоящей работе рассматривается правило, задающее структурную динамику сложных систем. Результатом применения этого правила являются так называемые самоподобные (self-similar graphs) или фрактальные графы.
Фрактальный граф — это сложная абстрактная структура, обладающая свойствами фракталов и «простых» графов. В разных научных школах применяются различные правила построения структурной динамики, что в результате приводит к различным, по строению, самоподобным графам. По данной тематике написано множество статей в российских и зарубежных научных журналах. В статье F.G. Arenas, М.А. Sanchez-Granero (2000) исследуются графы, построенные на множестве точек отрезка [0,lj. В работах
E. Teufl, S.Wagner (2000); В. Kron (2002); В. Kron, Е. Teufl (2004);
L. Malozemov, A. Teplyaev (2003); D. D'Angeli, A. Donno (2010) изучаются
свойства графов, каждый из которых состоит из множества изоморфных
подграфов, причем последние могут иметь ровно одну общую вершину.
Свойства графов, полученных «дискретизацией» фрактальных множеств,
описали в своих трудах V. Nekrashevych (2007); D. Guido, Т. Isola, М. Lapidus
(2009). Самоподобные графы древовидной структуры исследованы в статье
J. Neunhauserer (2007).
Другие способы построения самоподобных графов, а также вопросы практического применения фрактальных множеств рассмотрены в работах
F. Cornelias, A. Miralles (2009); С. Lee, P-S. Loh, В. Sudakov (2012);
B.A. Бондаренко, В.Л. Дольникова (1994).
Понятие фрактал, введенное Бенуа Мандельбротом, объединило объекты, обладающие особым свойством — свойством самоподобия (self-similar). Работы, связанные с исследованием фрактальных объектов, фрактальных множеств, долгое время считались интересными, но не имеющими серьезных практических приложений. Мнения в мировой научной среде изменились после издания книги «Фракталы в физике». В настоящее время о перспективности и значимости исследований можно судить по регулярно проводимым конференциям и периодическим изданиям, полностью посвященным соответствующей тематике, и большому количеству книг, учебников и монографий. Это позволяет говорить о сформировавшемся круге прикладных физических задач на основе фрактальных множеств. Среди них выделяются задачи и модели, в которых фрактальные множества представлены как самоподобные, масштабно-инвариантные графы большой размерности, т.е. с большим количеством вершин. К ним относятся, например задачи о броуновском движении, диффузии и просачиваемости. Кроме того, самоподобные графы нередко выступают в качестве моделей структур сложных многоэлементных систем, таких как коммуникационные сети.
Изучение фрактальных графов и их приложений ведется под руководством профессора A.M. Кочкарова. Наиболее активно прорабатываются задачи многокритериальной оптимизации в системах с фрактальной структурой и вопросы выявления свойств и характеристик графов. Метрические свойства исследуются в работах A.M. Кочкарова.
В работе Д.А. Павлова построены оценки метрическим характеристикам предфрактального графа с затравкой простая цепь, в монографии Кочкарова А. А. получены оценки диаметра и радиуса произвольных предфрактальных графов и некоторых классов графов при сохранении смежности старых ребер.
Другим направлением исследования является распознавание фрактальных (предфрактальных) графов. Предфрактальные графы состоят из конечного количества элементов (вершин и ребер), поэтому любая задача распознавания таких графов допускает переборное решение. Для практических задач важен не факт существования алгоритма распознавания, а важно наличие эффективного алгоритма решения поставленной задачи. Наиболее «быстрыми» являются, как известно, полиномиальные алгоритмы. Разработка таких алгоритмов является одной из целей данной работы.
В частности, A.M. Кочкаровым (1998) разработаны полиномиальные алгоритмы распознавания предфрактальных графов с полными затравками, некоторых предфрактальных деревьев, некоторых предфрактальных графов с регулярными затравками. Вопросы распознавания предфрактальных графов также исследуются в работах Е.В. Бобылевой (2005); Е.М. Киселевой, Е.В. Бобылевой (2005); И.Х. Утакаевой (2007); Л.Х. Хапаевой, A.M. Кочкарова (2011).
Цели и задачи исследования.
-
Исследование структуры предфрактальных графов.
-
Выявление свойств и характеристик предфрактальных графов с различными затравками.
-
Разработка алгоритмов распознавания предфрактальных графов.
Методы исследования. В диссертационной работе используются методы исследования операций, теории графов, теории предфрактальных и фрактальных графов, теории алгоритмов и сложности алгоритмов, ком бинаторики.
Научная новизна.
-
Предложен алгоритм распознавания предфрактальных графов, порожденных регулярными затравками.
-
Предложен алгоритм распознавания предфрактальных графов, порожденных затравками, удовлетворяющими условию Оре, при несмежности старых ребер.
-
Предложен алгоритм распознавания предфрактальных графов, порожденных затравками, удовлетворяющими условию Оре, при сохранении смежности старых ребер.
-
Предложен алгоритм распознавания предфрактальных графов,
порожденных n-вершинными затравками, степень каждой вершины
2и-1
которых не менее .
-
Получены оценки диаметра предфрактальных графов, порожденных затравками, удовлетворяющими условию Оре, при сохранении смежности старых ребер.
-
Получены оценки радиуса предфрактальных графов, порожденных затравками, удовлетворяющими условию Оре, при сохранении смежности старых ребер.
Практическая ценность и теоретическая значимость работы. В
диссертационной работе получен ряд результатов, позволяющих расширить область применения теории графов.
Апробация работы. Основные результаты работы докладывались на конференциях:
1. Первая Всероссийская конференция молодых ученых «Математическое моделирование фрактальных процессов, родственные проблемы анализа и информатики», Россия, п. Терскол, 2010;
-
Всероссийская научно-методическая конференция «Актуальные проблемы углубленного математического образования», Майкоп, 2010;
-
Международная научно-практическая конференция «Перспективные инновации в науке, образовании, производстве и транспорте 2010», Одесса, 2010;
-
VI Всероссийская научно-практическая конференция «Математические методы и информационно-технические средства», Краснодар, 2010;
-
VII Международная научная конференция молодых ученых «Наука. Образование. Молодежь», Майкоп, 2011.
Публикации. По результатам выполненной работы имеется 8 публикаций, в том числе, 3 статьи в журналах из списка ВАК, тезисы докладов в материалах двух Всероссийских конференций, тезисы докладов в материалах двух международных конференций. На разработанные алгоритмы получено 2 свидетельства о государственной регистрации программ для ЭВМ.
Структура диссертации. Поставленные задачи определили структуру работы и содержание отдельных разделов. Диссертация состоит из введения, трех разделов, заключения, списка использованных источников и приложения. Она изложена на 117 страницах машинописного текста (без приложений), содержит 42 рисунка, одно приложение, список использованных источников из 189 наименований.
Основные положения, выносимые на защиту.
-
Эффективные полиномиальные алгоритмы распознавания предфрактальных графов.
-
Теорема об окружении вершины предфрактального графа, в траектории которого старые ребра не смежны (теорема 1.6).
-
Теорема об окружении старой вершины предфрактального графа, в траектории которого смежность старых ребер сохраняется (теорема 1.9).
-
Оценки диаметра и радиуса предфрактальных графов, порожденных затравками, удовлетворяющими условию Оре, при сохранении смежности старых ребер.
Свойства предфрактальных графов, порожденных регулярными затравками
Основными рассматриваемыми объектами данной работы являются предфракталъные графы [50]. Определению предфрактального графа предшествуют дополнительные определения и понятия. Термином затравка [50] условимся называть какой-либо фиксированный связный п -вершинный граф Н = (w,Q) с непомеченными вершинами.
Определим операцию замещения вершины затравкой (ЗВЗ) [50], которая является обобщением операции расщепления вершины графа [12]. Суть операции ЗВЗ состоит в следующем. В данном графе G = (V,E) у намеченной для замещения вершины v0 (v0 eV) выделяется ее окружение [12], т.е. множество U0 всех вершин, смежных с вершиной v0, и множество ребер R0, инцидентных вершине v0, R0 = \е = v0u / є є Е, и є U0}.
Определим некоторое отображение ер множества вершин U0 во множество вершин затравки W: т.е. каждой вершине и (u eU0) ставим в соответствие, определяемую с помощью ср, вершину затравки v =(p(u ).
После этого, у каждого ребра e = v0u (eeR0) из множества R0 конец v0 заменяется на определяемую отображением ср вершину v = cp{u) затравки Н. «Старое» ребро e = v0u удаляется из графа G и появляется в нем в «новом» измененном виде е = vu .
Множеством вершин получаемого графа является исходное множество вершин V, за исключением замещаемой вершины v0, но с добавлением множества вершин затравки W, т.е. множеством вершин получаемого графа будет являться множество Fuf\{vJ (рисунок 1).
Определим поэтапный процесс выполнения операции ЗВЗ. На этапе s = \ затравку И = (w,Q) обозначаем как граф Gl ={vi,El).
Пусть выполнены этапы s = l,2,...,l, и по завершению этапа / получен граф Gl ={yl,El), который назовем предфрактальным графом. На этапе s = 1 + \ для каждой вершины v (VGF,) осуществляется операция ЗВЗ, т.е. замещение каждой вершины затравкой Н. В процессе выполнения всех операций ЗВЗ на данном этапе все ребра eeEt сохраняются и называются старыми ребрами по отношению ко всем графам
GM,.Gl+2,..,GL, где Ь \. Причем, старые ребра, инцидентные замещаемой вершине veVj, становятся, случайным или регулярным образом, инцидентными некоторым вершинам затравки, заместившей вершину v. Ребра каждой из таких появившихся затравок называют новыми ребрами, т.е. множество всех новых ребер есть множество Еы \Et.
Далее будем рассматривать предфрактальный граф GT =(vT,ET), порожденный произвольной и -вершинной затравкой Н = (w,Q).
Ребра, появившиеся на 1-ом этапе порождения / є {1,2,...,}, будем называть ребрами ранга I [50].
Если из графа GL удалить все ребра рангов 1,...,L-1, то исходный граф распадается на множество связных компонент В , каждая из которых изоморфна затравке Н. Множество компонент В будем называть блоками первого ранга [50]. Аналогично, при удалении из GL ребер рангов 1,...,L-2, получим множество В(2) блоков второго ранга. Очевидно, что всякий блок второго ранга является предфрактальным графом ранга 2, порожденным затравкой Н. Аналогично определяются множества блоков остальных рангов Bf,...,B [50]. Всякий блок ранга k (k = 1,L-1) является предфрактальным графом ранга к.
Свойства предфрактальных графов, порожденных регулярными затравками Следующая лемма устанавливает, что существует не более одного ребра, соединяющего два блока одного ранга. Лемма 1.1 Для любых двух блоков М(1 =\V(1 ,E(1) и М[2) _ J/(2) f2) ранга к (к = 1,Ь-1) (М 1 ,м2 efif) существует не более одного ребра e = v1v2, такого что V1eV(1 ,v2eV(2).
Замечание: если к = 1, то м_\ и Mf\ представляют собой вершины графа GL_X. В графе GL_X рассмотрим ребро 4-і? 4-ІЄ ІІ (4-і 4-і є Еь-\X которое, в процессе получения графа GL из графа GL_15 сохранилось в качестве ребра 4 (42))-Ребро 4-і (4-і) соединяет вершины блоков м_\ и М } . Если к = \, т.е. м_\ и М{1\ представляют собой вершины графа GL1, то эти вершины соединяются двумя ребрами 4-і и 4-і чт0 приводит к противоречию: G не мультиграф.
В противном случае (к \), перейдем к графу GL_2=(yL_2,EL_2). Аналогичным образом определим блоки М }2, М }2 (М }2,М }2 єВ ) и ребра 4-2 4-2 (е _2, e\z2 є i?L_2).
И вновь, если & = 2, т.е. М _2 и М 2 представляют собой вершины графа GL_2, то каждая из них инцидентна двум ребрам 4_2 и 4-2 чт0 приводит к противоречию, ведь GL_2 не мультиграф.
Продолжая, придем к графу GL_k = (vL-k,EL_k), в котором аналогичным образом определены блоки М{1\, М \ и ребра е \, 4-І (4- 4-1 еЕь-к) причем М{1\ и М{1\ представляют собой вершины графа GL_к (М ]к,М }к eVL_к). Эти вершины соединяются двумя ребрами 4- и 4-1 чт0 приводит к противоречию, ведь GL_fc не мультиграф.
Введем понятие слияние блоков. Рассмотрим некоторое множество М = Щ{1\...,М{р) В{р (\ Т nLl) блоков первого ранга предфрактального графа GL=(yL,EL). Обозначим VM=\y1,...,vu] — множество вершин, входящих в блоки множества М (\fi U 3j T/v Mj), Ем = {e1,e2,...,eR} — множество ребер, каждое из которых инцидентно хотя бы одной из вершин множества VM. Удалим из предфрактального графа GL блоки М 1 ,...,М р. К графу GL присоединим новый блок первого ранга Z = (W,Q ).
Рассмотрим все такие ребра e, принадлежащие множеству E что e = abeEM,aeVM,b VM. Вместо ребра е в граф GL добавим ребро ? , соединяющее вершину Ъ и одну из вершин d множества W (d eW). Эту вершину d выбираем произвольно. Результатом операции слияния блоков является мультиргаф. В качестве примера рассмотрим слияние блоков первого ранга М2 и М3. На рисунке 2 слева изображен исходный предфрактальный граф, справа — граф, полученный слиянием блоков первого ранга М2 и М3.
Свойства предфрактальных графов при несмежности старых ребер
Рассмотрим траекторию Gl ={yl,El\ l = 1,L построения предфрактального графа GL=(j/L,EL), порожденного затравкой H = (jV,Q). На этапе s рассматриваемой траектории в графе Gs каждая вершина с помощью операции замены вершины затравкой (ЗВЗ) заменяется затравкой H = (jV,Q). В процессе замены каждое старое ребро становится, случайным или регулярным образом, инцидентным некоторой вершине затравки Н.
Определение 1.2 Предфрактальным графом, в траектории которого старые ребра сохраняют смежность, называется предфрактальный граф GL=(vL,EL) такой, при поэтапной генерации которого, в процессе выполнения каждой операции ЗВЗ каждого этапа s (s = 1,L-1) старые ребра сохраняют смежность. Определение 1.3 Вершина v предфрактального графа GL=(j/L,EL) (veVL) называется старой, если она инцидентна хотя бы одному старому ребру. Остальные вершины предфрактального графа GL ={yL,EL) называются новыми. Пусть GL =(vL,EL) — предфрактальный граф, в траектории которого смежность старых ребер сохраняется. Следующая лемма устанавливает, что в каждом его блоке первого ранга не более одной старой вершины.
Пусть GLч =(vL_1,ELч) — предфрактальный граф, входящий в траекторию построения GL. В графе GL_1 рассмотрим такую вершину v0 (v0 є VL_1), из которой был получен блок Z с помощью операции ЗВЗ. Пусть Е0 — множество ребер, каждое из которых инцидентно вершине v0 (0сн). Поскольку в траектории графа GL смежность старых ребер сохраняется, то в GL все ребра множества Е0 останутся попарно смежными, а значит, инцидентными одной и той же вершине блока Z. Обозначим эту вершину — v (veW). Вершина v будет единственной старой вершиной блока Z .
Пусть GL =(vL,EL) — предфрактальный граф, в траектории которого смежность старых ребер сохраняется. Следующая теорема устанавливает, что в каждом блоке не более одной вершины «большой» степени.
Теорема 1.7 Если Z = (j ,Q ) — блок первого ранга (Z є В ) предфрактального графа GL=(VL,EL), в траектории которого смежность старых ребер сохраняется, Н = (w, Q) — п -вершинная затравка, породившая GL, N — множество вершин блока Z, степень каждой из которых не менее п (N с W), то liVl 1.
Каждая из новых вершин блока Z инцидентна только новым ребрам, а значит, имеет степень не более п-1. Следовательно, ни одна новая вершина блока Z не принадлежит множеству N. Поэтому livl 1. Пусть GT =(vT,ET) — предфрактальный граф, в траектории которого смежность старых ребер сохраняется. Следующая теорема устанавливает факты для окружения новой вершины.
Теорема 1.8 Если GL=(j/L,EL) — предфрактальный граф, в траектории которого смежность старых ребер сохраняется, Н = (jV,Q) — и-вершинная затравка, породившая GL, v — новая вершина GL, Z = (w ,Q ) — блок первого ранга (Z еВ ), содержащий вершину v (veW), U — окружение вершины v (U VL), N — подмножество вершин множества U, степень каждой из которых не менее п (N с U), то верны следующие два утверждения:
Пусть GL =(vL,EL) — предфрактальный граф, в траектории которого смежность старых ребер сохраняется. Следующая теорема устанавливает факты для окружения старой вершины.
Теорема 1.9 Если GL=(j/L,EL) — предфрактальный граф, в траектории которого смежность старых ребер сохраняется, Н = (jV,Q) — и-вершинная затравка, породившая GL, Н удовлетворяет условию Оре, v — старая вершина GL, степень вершины v меньше п (p(v) n), Z = {fV ,Q ) — блок первого ранга (ZeBf), содержащий вершину v (veW), U — окружение вершины v (f/cFj, N — подмножество вершин множества U, степень каждой из которых не менее п (N с U), то верны следующие три утверждения:
Пусть и0 ={щ,...,ик} (к = \и0\). Выберем и. — произвольную вершину множества U0 (uteU0, \ і к). В результате применения операций ЗВЗ к вершинам v0 и и. ребро v0w. є EL_X удалится из GL_X и появится в GL в виде ?. = vgt є EL. Рассмотрев операцию ЗВЗ для каждой пары вершин v0 и и., получим множество Ul ={gl,...,gk} (U1 cFj, причем [/jJ = \U01 2. Докажем, что каждая из вершин множества U1 имеет степень не меньше п,
Следовательно, tL = tL_1 = d1. Рассмотрим gi (1 i k) — произвольную вершину множества U1 (g. єС/1). В свою очередь, степень вершины gi в графе GL складывается из трех составляющих: h L-1 ,h-2 (p(gi) = tL+tL-1 +tL-2 ), где fL — количество инцидентных gi ребер ранга L, tL_1 — количество инцидентных gi ребер ранга L-1, tL_2 — количество инцидентных gi ребер ранга не больше L-2. С другой стороны, число tL_1 равно количеству смежных с ut (ut eU0) вершин блока Z0. Поскольку в блоке Z0 p(v0) = tL_1 =d1, то p(u.) = tL_1 d2. Имеем неравенство: p(gt) tL +tL_1 d1+d2 n. Значит, каждая из вершин множества U1 имеет степень не меньше п, следовательно U1 с N. Откуда iV \U1 J 2.
б) согласно лемме 1.7, блок Z = {fV ,Q ) содержит ровно одну старую вершину, значит, все, отличные от v, вершины блока Z, новые. Степень каждой из них не более п-1, т.е. VMEF/« VZ P(M) B-1. Из последнего неравенства вытекает, что
все, отличные от v, вершины блока Zне принадлежат множеству N, т.е. \/UEW /U V U N. Получили, что любая вершина множества N не лежит в блоке Z.
в) обозначим за s произвольную вершину множества U\N, не принадлежащую блоку Z = (w,Q ) (seU,szN,seVL,siW ,p{s) n-1). Пусть r — ранг ребра e = vseEL (1 r L-1). Рассмотрим в графе Gr=(Vr,Er) ребро e0=v0s0eEr (v0eVr,s0eVr), из которого, после применения операций ЗВЗ, образовалось ребро е = vs. Ребро е0 в графе Gr имеет тот же ранг, что и ребро е в графе GL. Поэтому в графе Gr ребро е0 новое. Рассмотрим в Gr блок первого ранга Z0 =(w0,Q0), которому принадлежат вершины v0,s0 (v0 eW0,s0 eW0).
Степень вершины v в графе GL складывается из трех составляющих: tL,tr,t, т.е. p(v) = tL+tr+t, где tL — количество инцидентных v ребер ранга L, tr — количество инцидентных v ребер ранга г, t — количество инцидентных v ребер рангов, отличных от L и г. С другой стороны, число tL равно количеству смежных с v вершин блока Z. Поскольку в GL смежность старых ребер сохраняется, то число tr равно количеству смежных с v0 вершин блока Z0. Т.к. блоки Z и Z0 удовлетворяют условию Оре, и каждый из них изоморфен затравке Н, то
Оценки диаметра предфрактальных графов, порожденных затравками, удовлетворяющими условию Оре
В противном случае, работа процедуры (53 завершается проверкой на изоморфность графа Z = (w0,Q0) и графа, образованного множествами выделенных таким образом вершин и ребер. Если эти графы изоморфны, то шаг, включающий в себя описанную процедуру (33, завершается результативно, и следует переход к следующему шагу первого этапа. В противном случае, работа шага считается безрезультатной, и алгоритм а3 заканчивает свою работу.
Этап р = 1 завершает свою работу как только все вершины множества V окажутся выделенными. Далее осуществляем процедуру стягивания каждой выделенной затравки в одну вершину. После чего, полученный граф GL_1 предъявляем на вход следующего этапа алгоритма а3.
Представленное выше описание работы первого этапа является общим, т.е. все его операции и процедуры остаются неизменными по отношению к каждому графу строящейся последовательности. В случае результативной работы каждого из L-1 этапов, в качестве последнего члена полученной последовательности получаем п-вершинный граф, изоморфный графу Z = (w0,Q0). Этот результат означает получение положительного ответа на вопрос, является ли данный граф G предфрактальным графом, порожденным п -вершинной затравкой, удовлетворяющей условию Оре, при сохранении смежности старых ребер.
Выводы: алгоритм а3, будучи примененный к произвольному графу, обозначаемому как G = (V,E), дает положительный результат в тех и только тех случаях, когда граф G окажется предфрактальным графом, порожденным затравкой, удовлетворяющей условию Оре, обозначаемой здесь как граф Н = (w,Q), при сохранении смежности старых ребер. В том случае, если граф G принадлежит одновременно сразу нескольким траекториям построения предфрактальных графов, причем траектории порождены затравками, удовлетворяющими условию Оре, а в траекториях смежность старых ребер сохраняется, то алгоритм а3 определит все такие затравки и для каждой траектории вычислит номер L этапа построения, на котором возникнет граф G.
Во всех остальных случаях алгоритм а3 выдаст отрицательный ответ на вопрос о предфрактальности графа G.
Теорема 3.3 Всякий предфрактальный граф GL=(vL,EL), порожденный затравкой, удовлетворяющей условию Оре, при сохранении смежности старых ребер распознается алгоритмом а3, причем, если и = 0(ln ), то т(а3) 0\ Еь\2Lj, где т(а3) — трудоемкость алгоритма а3, п — количество вершин затравки..
Распознаваемость предфрактального графа GL=(vL,EL), порожденного затравкой Н = (jV,Q), доказана в описании алгоритма а3.
Пусть А — произвольный алгоритм, принимающий вход длины т . Обозначим за f(A,m) — число элементарных операций, которые потребуются для его выполнения.
Алгоритм а3 начинается с проверки необходимых условий предфрактальности. Обозначим за В алгоритм такой проверки. Следуя доказательству теоремы 3.1, сложность проверки необходимых условий предфрактальности графа оценивается следующим образом: /(i?,FL) = 0( L).
Окончательное обоснование верхней оценки трудоемкости алгоритма а3 получаем из того, что число его этапов не превосходит L. Алгоритм распознавания предфрактальных графов, порожденных п -вершинной затравкой, степень каждой вершины которой не меньше п2, при сохранении смежности старых ребер Постановка задачи Пусть задан граф G = (V,E). Необходимо проверить, является ли он предфрактальным графом GL=(vL,EL), порожденным и-вершинной затравкой H = (w,o), в которой степень каждой вершины не меньше %, при сохранении смежности старых ребер.
В доказательстве следствия 1.3.2 было показано, что и-вершинная затравка Н = (w,o), степень каждой вершины которого не меньше %, удовлетворяет условию
Оре. Таким образом, для решения поставленной задачи можно использовать алгоритм а3.
На практике, для сформулированной задачи можно воспользоваться новым алгоритмом а3 с целью упростить программную реализацию алгоритма.
Если в процессе распознавания графа GL процедура (53 выполняется впервые, то работа процедуры (53 завершается тем, что множество выделенных таким образом вершин и ребер запоминается как п -вершинный граф Z = (w0,Q0).
В противном случае, работа процедуры (53 завершается проверкой на изоморфность графа Z = (w0,Q0) и графа, образованного множествами выделенных таким образом вершин и ребер. Если они изоморфны, то шаг, включающий в себя описанную процедуру /?3 , завершается результативно, и следует переход к следующему шагу первого этапа. В противном случае, работа шага считается безрезультатной и алгоритм а3 заканчивает свою работу.
Алгоритмы распознавания предфрактальных графов, в траектории которых старые ребра не смежны
Постановка задачи Пусть задан граф G = (V,E). Необходимо проверить, является ли он предфрактальным графом GL=(vL,EL), порожденным затравкой, являющейся п-вершинным графом H = (w,o), степень каждой вершины которого не меньше %, при несмежности старых ребер. В доказательстве следствия 1.3.2 было показано, что и-вершинная затравка Н = (w,o), степень каждой вершины которого не меньше % , удовлетворяет условию Оре. Таким образом, для решения поставленной задачи можно использовать алгоритм а2. На практике, для сформулированной задачи можно воспользоваться новым алгоритмом а2 с целью упростить программную реализацию алгоритма. Единственным отличием алгоритмов а2 и а2 является замена процедуры выделения затравки (52 процедурой (52 .
Описание процедуры (52 для G = (V,E) Во множестве V выделяем очередную неотмеченную вершину V1, т.е. вершину, которая не принадлежит какой-либо уже выделенной затравке из множества V.
Если такую вершину выделить не удалось, то процедура (52, а с ней и алгоритм а2 , заканчивают свою работу безрезультатно. Выделенная вершина v1 смежна с некоторыми неотмеченными вершинами множества V. Обозначим множество этих вершин как U1= i1,...,ut}, t = p1\.
Считаем вершины множества U1 выделенными. Согласно теореме 1.5, все, за исключением, может быть, одной, вершины множества и1, принадлежат текущей затравке H = (w,Q). Для выделения оставшихся вершин затравки Н воспользуемся следствием 1.3.2. А именно, среди невыделенных вершин множества V выделяем такие вершины, которые смежны хотя бы с двумя вершинами множества U1. Обозначим множество этих вершин как и2. Согласно следствию 1.6.1, все вершины множества U2 принадлежат текущей затравке Н.
Рассматривая вершину v1 и произвольную вершину v0 затравки Н (v0eW), получаем, что либо v1 и v0 смежны (v0 є[/1), либо, согласно следствию 1.3.2, v0eU2. Поэтому произвольная вершина v0 затравки Н принадлежит множеству {V1} JU1 U2 , т.е., с учетом сказанного выше, получаем, что либо множества {V1} JU1 U2 и W совпадают, либо W {V1} JU1 U2, причем в {V1} JU1 U2 на одну вершину больше, чем в W. Значит, если Цу + + и (с/2 и-?-1) и Ц І + ІС/1 + ІС/ и + 1 ([/2 и-г), то процедура (52 , а с ней и алгоритм а2 , заканчивают свою работу безрезультатно. Иначе, если \U2\ = n-1, то результатом работы процедуры (52 считаем множество вершин W = {vJuC/1 uC/2.
Если же \U2\ = n, то из множества U1 необходимо исключить одну такую вершину v2 (v2 є U1), которая не смежна ни с одной из вершин множества [/1и[/2. Действительно, согласно лемме 1.1, два блока первого ранга — Я и z1=( 1,Q1), где Z1 — блок, в котором лежит вершина v2 (v2eW1), соединены не более, чем одним ребром, и это ребро инцидентно вершине V1 (v1V2e). Значит, вершина v2 не смежна ни с одной из оставшихся вершин затравки Я, т.е. не смежна ни с одной из вершин множества U1yjU2. С другой стороны, любая вершина v3 затравки Я (v3eW) смежна не менее, чем с 2 вершинами Я, и, значит, не менее, чем с двумя вершинами Я (и 2). Получили, что любая вершина v3 затравки Я смежна хотя бы с одной вершиной множества [/1и[/2.
Значит, если не найдется вершина, не смежная ни с одной из вершин множества [/1uf/2, то процедура (52, а с ней и алгоритм а2, заканчивают свою работу безрезультатно. Иначе результатом работы процедуры (52 считаем множество вершин W{0) = {vJuC/1 uC/2 \ {v2}.
Выделяем и отмечаем все ребра, у каждого из которых концы принадлежат множеству W0.
Если в процессе распознавания графа GL процедура /32 выполняется впервые, то работа (52 завершается тем, что множество выделенных таким образом вершин и ребер запоминается как п -вершинный граф Z = (w0,Q0).
В противном случае, работа процедуры (52 завершается проверкой на изоморфность графа Z = (w0,Q0) и графа, образованного множествами выделенных таким образом вершин и ребер. Если они изоморфны, то шаг, включающий в себя описанную процедуру (52 , завершается результативно, и следует переход к следующему шагу этапа. В противном случае, работа шага считается безрезультатной, и алгоритм а2 заканчивает свою работу.
Аналогом теоремы 3.2 является следующая Теорема 3.2.1 Всякий предфрактальный граф GL=(vL,EL), порожденный п вершинной затравкой, степень каждой вершины которой не меньше %, при несмежности старых ребер, распознается алгоритмом а2 , причем, если и = 0(ln,), то T(CC2 ) O EL\2LJ, где т(а2 ) — трудоемкость алгоритма а2 . Доказательство. Доказательство, очевидно, вытекает из теоремы 3.2.
Алгоритмы распознавания предфрактальных графов, в траектории которых смежность старых ребер сохраняется Постановка задачи Пусть задан граф G = (V,E). Необходимо проверить, является ли он предфрактальным графом GL=(vL,EL), порожденным затравкой H = (w,Q), удовлетворяющей условию Оре, при сохранении смежности старых ребер. Алгоритм а3 Алгоритм а3 предназначен для распознавания свойства предфрактальности данного граф G = (V,E) в случае, когда G, предположительно, является предфрактальным графом, порожденным и-вершинной затравкой H = (w,Q), удовлетворяющей условию Оре, при сохранения смежности старых ребер, если значение п считается априори заданным. Единственным отличием данного алгоритма от алгоритма а2 является содержание процедуры выделения затравки (52. Предварим алгоритм а3 процедурой проверки необходимых условий предфрактального графа, применив такую процедуру к графу G. В качестве примера рассмотрим граф, представленный на рисунке 21. Процедура проверки необходимых условий дает следующие результаты: количество вершин И = 36, количество ребер \Е\ = 77 , количество этапов построения L = 2, количество вершин в затравке п = 6, количество ребер в затравке — 11.
Похожие диссертации на Исследование свойств и распознавание предфрактальных графов
