Исследование свойств и распознавание предфрактальных графов тема автореферата и диссертации по математике, 01.01.09 ВАК РФ
|
Резников, Андрей Владимирович
АВТОР
|
||||
|
кандидата физико-математических наук
УЧЕНАЯ СТЕПЕНЬ
|
||||
|
Черкесск
МЕСТО ЗАЩИТЫ
|
||||
|
2013
ГОД ЗАЩИТЫ
|
|
01.01.09
КОД ВАК РФ
|
||
|
|
||||
На правах рукописи
Резников Андрей Владимирович
ИССЛЕДОВАНИЕ СВОЙСТВ И РАСПОЗНАВАНИЕ ПРЕДФРАКТАЛЬНЫХ ГРАФОВ
01.01.09 - Дискретная математика и математическая кибернетика
Автореферат
диссертации на соискание ученой степени кандидата физико-математических наук
Ярославль - 2013
Работа выполнена в федеральном государственном бюджетном образовательном учреждении высшего профессионального образования «Северо-Кавказская государственная гуманитарно-технологическая академия» (Карачаево-Черкесская Республика, г. Черкесск)
Научный руководитель: доктор физико-математических наук,
профессор Кочкаров Ахмат Магомедович
Официальные оппоненты:
Бондаренко Владимир Александрович, доктор физико-математических наук, профессор, заведующий кафедрой дискретного анализа ФГБОУ ВПО «Ярославский государственный университет им. П.Г. Демидова»
Пастор Алексей Владимирович, кандидат физико-математических наук, научный сотрудник лаборатории математической логики Санкт-Петербургского отделения Математического института им. В.А. Стеклова Российской академии наук
Ведущая организация:
Федеральное государственное образовательное учреждение
профессионального образования федеральный университет»
автономное высшего «Южный
Защита диссертации состоится 20 декабря 2013 г. в 12:30 на заседании диссертационного совета Д 212.002.03 при ФГБОУ ВПО «Ярославский государственный университет им. П.Г. Демидова» по адресу: 150008, г. Ярославль, ул. Союзная, 144, аудитория 426.
С диссертацией можно ознакомиться в библиотеке ФГБОУ ВПО «Ярославский государственный университет им. П.Г. Демидова».
Автореферат разослан « » ноября 2013 г.
Ученый секретарь диссертационного совета
Яблокова С.И
Общая характеристика работы
Диссертация посвящена исследованию и анализу основных свойств предфрактальных графов, а также разработке и анализу алгоритмов распознавания предфрактальных графов.
Актуальность темы. Любые сложные системы, такие как информационные, энергетические, управленческие, претерпевают с течением времени определенные, вызванные внешними причинами, изменения. Довольно часто структуры таких систем уместно представлять в виде графа. В работах F. Harari (1973), C. Berge (1962), В.А. Емеличева (1990) и других рассматриваются операции над графами, такие как объединение, соединение, произведение, композиция, стягивание дуги и пр. С помощью этих операций можно описать изменения, происходящие в структурах сложных систем. Структуры систем могут претерпевать как разовые, так и регулярные изменения. Обобщением случая регулярных изменений является понятие структурной динамики.
Общеизвестным сценарием структурной динамики является рост структуры — регулярное появление элементов и связей в структуре системы. В некоторых случаях для описания роста структуры используется перечень правил, причем такие правила могут допускать элемент случайности.
В настоящей работе рассматривается правило, задающее структурную динамику сложных систем. Результатом применения этого правила являются так называемые самоподобные (self-similar graphs) или фрактальные графы.
Фрактальный граф — это сложная абстрактная структура, обладающая свойствами фракталов и «простых» графов. В разных научных школах применяются различные правила построения структурной динамики, что в результате приводит к различным, по строению, самоподобным графам. По данной тематике написано множество статей в российских и зарубежных научных журналах. В статье F.G. Arenas, M.A. Sanchez-Granero (2000) исследуются графы, построенные на множестве точек отрезка [0,1]. В работах
E. Teufl, S. Wagner (2000); B. Krön (2002); B. Krön, E. Teufl (2004); L. Malozemov, A. Teplyaev (2003); D. D'Angeli, A. Donno (2010) изучаются свойства графов, каждый из которых состоит из множества изоморфных подграфов, причем последние могут иметь ровно одну общую вершину. Свойства графов, полученных «дискретизацией» фрактальных множеств, описали в своих трудах V. Nekrashevych (2007); D. Guido, T. Isola, M. Lapidus (2009). Самоподобные графы древовидной структуры исследованы в статье J. Neunhäuserer (2007).
Другие способы построения самоподобных графов, а также вопросы практического применения фрактальных множеств рассмотрены в работах
F. Comellas, A. Miralles (2009); C. Lee, P-S. Loh, B. Sudakov (2012); В.А. Бондаренко, В.Л. Дольникова (1994).
Понятие фрактал, введенное Бенуа Мандельбротом, объединило объекты, обладающие особым свойством — свойством самоподобия (self-similar). Работы, связанные с исследованием фрактальных объектов, фрактальных множеств, долгое время считались интересными, но не имеющими серьезных практических приложений. Мнения в мировой научной среде изменились после издания книги «Фракталы в физике». В настоящее время о перспективности и значимости исследований можно судить по регулярно проводимым конференциям и периодическим изданиям, полностью посвященным соответствующей тематике, и большому количеству книг, учебников и монографий. Это позволяет говорить о сформировавшемся круге прикладных физических задач на основе фрактальных множеств. Среди них выделяются задачи и модели, в которых фрактальные множества представлены как самоподобные, масштабно-инвариантные графы большой размерности, т.е. с большим количеством вершин. К ним относятся, например задачи о броуновском движении, диффузии и просачиваемости. Кроме того, самоподобные графы нередко выступают в качестве моделей структур сложных многоэлементных систем, таких как коммуникационные сети.
Изучение фрактальных графов и их приложений ведется под руководством профессора А.М. Кочкарова. Наиболее активно прорабатываются задачи многокритериальной оптимизации в системах с фрактальной структурой и вопросы выявления свойств и характеристик графов. Метрические свойства исследуются в работах А.М. Кочкарова.
В работе Д.А. Павлова построены оценки метрическим характеристикам предфрактального графа с затравкой простая цепь, в монографии Кочкарова А.А. получены оценки диаметра и радиуса произвольных предфрактальных графов и некоторых классов графов при сохранении смежности старых ребер.
Другим направлением исследования является распознавание фрактальных (предфрактальных) графов. Предфрактальные графы состоят из конечного количества элементов (вершин и ребер), поэтому любая задача распознавания таких графов допускает переборное решение. Для практических задач важен не факт существования алгоритма распознавания, а важно наличие эффективного алгоритма решения поставленной задачи. Наиболее «быстрыми» являются, как известно, полиномиальные алгоритмы. Разработка таких алгоритмов является одной из целей данной работы.
В частности, А.М. Кочкаровым (1998) разработаны полиномиальные алгоритмы распознавания предфрактальных графов с полными затравками, некоторых предфрактальных деревьев, некоторых предфрактальных графов с регулярными затравками. Вопросы распознавания предфрактальных графов также исследуются в работах Е.В. Бобылевой (2005); Е.М. Киселевой, Е.В. Бобылевой (2005); И.Х. Утакаевой (2007); Л.Х. Хапаевой, А.М. Кочкарова (2011).
Цели и задачи исследования.
1. Исследование структуры предфрактальных графов.
2. Выявление свойств и характеристик предфрактальных графов с различными затравками.
3. Разработка алгоритмов распознавания предфрактальных графов.
Методы исследования. В диссертационной работе используются методы исследования операций, теории графов, теории предфрактальных и фрактальных графов, теории алгоритмов и сложности алгоритмов, ком бинаторики.
Научная новизна.
1. Предложен алгоритм распознавания предфрактальных графов, порожденных регулярными затравками.
2. Предложен алгоритм распознавания предфрактальных графов, порожденных затравками, удовлетворяющими условию Оре, при несмежности старых ребер.
3. Предложен алгоритм распознавания предфрактальных графов, порожденных затравками, удовлетворяющими условию Оре, при сохранении смежности старых ребер.
4. Предложен алгоритм распознавания предфрактальных графов, порожденных ^вершинными затравками, степень каждой вершины
2п -1
которых не менее —-—.
5. Получены оценки диаметра предфрактальных графов, порожденных затравками, удовлетворяющими условию Оре, при сохранении смежности старых ребер.
6. Получены оценки радиуса предфрактальных графов, порожденных затравками, удовлетворяющими условию Оре, при сохранении смежности старых ребер.
Практическая ценность и теоретическая значимость работы. В
диссертационной работе получен ряд результатов, позволяющих расширить область применения теории графов.
Апробация работы. Основные результаты работы докладывались на конференциях:
1. Первая Всероссийская конференция молодых ученых «Математическое моделирование фрактальных процессов, родственные проблемы анализа и информатики», Россия, п. Терскол, 2010;
2. Всероссийская научно-методическая конференция «Актуальные проблемы углубленного математического образования», Майкоп, 2010;
3. Международная научно-практическая конференция «Перспективные инновации в науке, образовании, производстве и транспорте 2010», Одесса, 2010;
4. VI Всероссийская научно-практическая конференция «Математические методы и информационно-технические средства», Краснодар, 2010;
5. VII Международная научная конференция молодых ученых «Наука. Образование. Молодежь», Майкоп, 2011.
Публикации. По результатам выполненной работы имеется 8 публикаций, в том числе, 3 статьи в журналах из списка ВАК, тезисы докладов в материалах двух Всероссийских конференций, тезисы докладов в материалах двух международных конференций. На разработанные алгоритмы получено 2 свидетельства о государственной регистрации программ для ЭВМ.
Структура диссертации. Поставленные задачи определили структуру работы и содержание отдельных разделов. Диссертация состоит из введения, трех разделов, заключения, списка использованных источников и приложения. Она изложена на 117 страницах машинописного текста (без приложений), содержит 42 рисунка, одно приложение, список использованных источников из 189 наименований.
Основные положения, выносимые на защиту.
1. Эффективные полиномиальные алгоритмы распознавания предфрактальных графов.
2. Теорема об окружении вершины предфрактального графа, в траектории которого старые ребра не смежны (теорема 1.6).
3. Теорема об окружении старой вершины предфрактального графа, в траектории которого смежность старых ребер сохраняется (теорема 1.9).
4. Оценки диаметра и радиуса предфрактальных графов, порожденных затравками, удовлетворяющими условию Оре, при сохранении смежности старых ребер.
Содержание работы
Во введении обоснована актуальность темы диссертации, ее новизна, практическая значимость. Дается обзор основных направлений исследования, близких к изучаемой тематике. Сформулированы цели и задачи исследования, представлены основные положения, выносимые на защиту. Дается краткое изложение содержания диссертации.
Первый раздел диссертации содержит общую теорию предфрактальных графов, формулировки и доказательства утверждений, касающихся особенностей устройства окружения вершин предфрактальных графов.
Основным элементом определения фрактального графа является затравка. Термином затравка условимся называть какой-либо фиксированный связный граф H = (ж, Q).
Определим операцию замещения вершины затравкой (ЗВЗ): в данном графе G = (у, Е) у намеченной для замещения вершины v0 выделяется ее окружение, т.е. множество и0 всех вершин, смежных с вершиной v0. Далее, из графа G удаляется вершина v0 и все инцидентные ей ребра. Вместо нее в граф G добавляется затравка Н. Затем каждая вершина множества и0 соединяется ребром с одной из вершин затравки Н. Вершины соединяются случайным образом или по определенному правилу при необходимости.
Предфрактальный граф будем обозначать через GL = (УЬ, Еь), где Уь, Еь -множества вершин и ребер графа соответственно. Определим его рекуррентно, поэтапно заменяя каждый раз в построенном на предыдущем этапе I = 1,2,..., Ь -1 графе Gl =(Уі, Е1) каждую его вершину затравкой Н. На этапе I = 1 предфрактальному графу соответствует затравка G1 = Н. В таком случае говорят, что предфрактальный граф GL порожден затравкой Н. В процессе порождения определяется последовательность графов G1,G2,...,GL. Эта последовательность называется траекторией предфрактального графа GL.
Ребра, появившиеся на і -ом этапе порождения і є {1,2,...,Ь}, будем называть ребрами ранга і. Ребра ранга і называются новыми ребрами предфрактального графа GL, остальные ребра - старыми.
Если из графа GL удалить все ребра рангов 1,...,Ь-1, то исходный граф распадается на множество связных компонент В^, каждая из которых изоморфна затравке Н. Множество компонент В^1 будем называть блоками первого ранга. Аналогично, при удалении из GL ребер рангов 1,...,Ь - 2 получим множество ВЬ> блоков второго ранга. Подобным образом определяются множества блоков остальных рангов В^,...,вЬЬ-1). Всякий блок ранга k (k = 1, Ь -1) является предфрактальным графом ранга k.
На рисунке 1 изображена траектория предфрактального графа G3 =(¥3, Е3), порожденного затравкой Н = (ж,Q) - треугольником. Линиями удвоенной толщины обозначены старые ребра предфрактальных графов G1, G2, G3, тонкими линиями - новые ребра.
Gl = H G2
Gз
Рисунок 1. Траектория предфрактального графа G3 =(кз, E3).
Показателем блока первого ранга 1 (1 є В^}) предфрактального графа GL =(уь, Еь) назовем степень такой вершины V графа GL_1 =(УЬ_1, Еь_х) (V є¥ь_1), из которой был получен блок 1 с помощью операции ЗВЗ. Обозначают: Мєх(і).
Свойства предфрактальных графов, порожденных регулярными затравками, описаны в следующих утверждениях:
Теорема о существовании блока первого ранга, показатель которого не превосходит п_1:
Теорема 1.1 В предфрактальном графе GL =(уь, Еь) найдется блок первого ранга 1 = (ж', Q') (1 є В{1)), показатель которого не превосходит п _ 1,
Мєх(і) < п _ 1.
Теорема о существовании блока первого ранга, показатель которого не превосходит п _ 1, в предфрактальном графе, из которого удалены несколько таких блоков:
Теорема 1.2 После удаления из предфрактального графа GL =(уь, Еь) множества блоков первого ранга М = Мь),•••,М^В^ со всеми инцидентными их вершинам ребрами во вновь образовавшемся графе G' = (VЕ') найдется блок первого ранга 1 = (жQ'), такой что ¡Мєх (1) < п _ 1.
В зависимости от взаимного расположения старых ребер предфрактального графа выделяют:
1) предфрактальные графы, в траектории которых старые ребра не смежны;
2) предфрактальные графы, в траектории которых старые ребра сохраняют смежность;
3) предфрактальные графы общего вида.
Вершину v предфрактального графа GL = (уь, EL) назовем старой вершиной, если она инцидентна хотя бы одному старому ребру. Остальные вершины будем называть новыми вершинами.
Будем говорить, что п -вершинный граф H = (ж, Q) удовлетворяет условию Оре, если для любой пары его вершин V и v2 (v1, v2 є Ж) выполняется условие р(уг) + р(у2) > п, где р(у) - степень вершины V .
Получен ряд свойств затравок предфрактальных графов.
Следующая теорема дает достаточные условия, при которых для выбранных вершин всегда можно подобрать две общие, смежные с ними, вершины.
Теорема 1.3 Если п -вершинный граф Н = (ж, Q) (п > 3) удовлетворяет условию Оре и если V и v2 (v1, v2 є Ж) — две несмежные вершины ( Є = v1v2 £ Q) графа Н, то в Н найдутся вершины w1 и (w1, w2 є Ж), такие что v1w2,v2w1,v2w2 }е Q). Другими словами, найдутся, по меньшей мере, две вершины, каждая из которых смежна одновременно с вершинами V и v2.
Следующая лемма доказывает отсутствие висячих вершин в графе, удовлетворяющем условию Оре.
Лемма 1.4 Если Н = (к, Е) — п -вершинный граф (\¥\ = п),
удовлетворяющий условию Оре, п > 2, то все вершины Н имеют степень не меньше 2 (VV є V^р(у)> 2).
Следующая лемма доказывает, что в графе, удовлетворяющем условию Оре, «почти все» вершины имеют степень п.
Лемма 1.5 Если Н = (у, Е) — п -вершинный граф (VI = п), удовлетворяющий условию Оре, V — вершина минимальной степени графа Н (V є V), то все, отличные от V, вершины графа Н, имеют степень не меньше п,
т.е. V и єV / и ф V ^ р(и)> п .
У ' 2
Следующая лемма дает достаточное условие связности графа.
Лемма 1.6 Если Н = (у, Е) — п -вершинный граф, степень каждой вершины которого не менее , то Н является связным графом.
Следующая теорема дает достаточное условие связности окружения произвольно выбранной вершины.
Теорема 1.4 Если H = (у, E) — п -вершинный граф, степень каждой
вершины которого не менее , у — произвольная вершина графа H (у є¥),
U — окружение вершины у (и е V), то подграф, порожденный множеством и, является связным.
Получен ряд утверждений о свойствах предфрактальных графов, в траектории которых старые ребра не смежны.
Следующая теорема доказывает, что окружение выбранной вершины «почти полностью» лежит в том же блоке, что и сама вершина.
Теорема 1.5 Если GL = (уь, Еь) — предфрактальный граф, в траектории которого старые ребра не смежны, Н = (ж, Q) — затравка GL, 7 = (жQ') — блок первого ранга GL (7 є В^}), у — вершина 7 (у є Ж'), и — окружение вершины у, то либо все вершины множества и принадлежат блоку 7, либо все, за исключением одной, вершины множества и принадлежат блоку 7 .
Следующая теорема доказывает, что вершины, смежные с двумя вершинами окружения выбранной вершины, лежат в том же блоке, что и сама вершина.
Теорема 1.6 Если GL = (уь, Еь) — предфрактальный граф, в траектории которого старые ребра не смежны, Н = (ж, Q) — затравка GL, 7 = (жQ') — блок первого ранга GL (7 є В), у — вершина 7 (у є Ж'), и — окружение вершины у, и2 — множество вершин GL = , ) (и2 е VL), каждая из которых смежна хотя бы с двумя вершинами множества и, то все вершины множества и2 принадлежат блоку 7 = (жQ').
Получен ряд утверждений о свойствах предфрактальных графов, в траектории которых старые ребра сохраняют смежность.
Пусть GL = (^, Еь) — предфрактальный граф, в траектории которого смежность старых ребер сохраняется. Следующая теорема устанавливает, что в каждом блоке не более одной вершины «большой» степени.
Теорема 1.7 Если 7 = (жQ') — блок первого ранга (7 є В^) предфрактального графа GL = ^, Еь), в траектории которого смежность старых ребер сохраняется, Н = (ж, Q) — п -вершинная затравка, породившая GL, N — множество вершин блока 7, степень каждой из которых не менее п (N е ж'), то
N1 -1.
Пусть GL = ^, Еь) — предфрактальный граф, в траектории которого смежность старых ребер сохраняется. Следующая теорема устанавливает факты для окружения новой вершины.
Теорема 1.8 Если GL = (уь, Еь) — предфрактальный граф, в траектории которого смежность старых ребер сохраняется, Н = (Ш, Q) — п -вершинная затравка, породившая GL, V — новая вершина GL, 2 = (Ш', О') — блок первого ранга (2 є В^), содержащий вершину V (VєШ'), и — окружение вершины V (и е ), N — подмножество вершин множества и, степень каждой из которых не менее п (N е и), то верны следующие два утверждения:
а) и е Ш', т.е. все вершины, смежные с V, принадлежат блоку 2;
б) N < і.
Пусть GL =(уь, Еь) — предфрактальный граф, в траектории которого смежность старых ребер сохраняется. Следующая теорема устанавливает факты для окружения старой вершины.
Теорема 1.9 Если GL =(УЬ, Еь) — предфрактальный граф, в траектории которого смежность старых ребер сохраняется, Н = (Ш, Q) — п -вершинная затравка, породившая GL, Н удовлетворяет условию Оре, V — старая вершина GL, степень вершины V меньше п (р(у)< п), 2 = (ШО) — блок первого ранга (2 є В^), содержащий вершину V (VєШ'), и — окружение вершины V (ие УL), N — подмножество вершин множества и, степень каждой из которых не менее п (N е и), то верны следующие три утверждения:
а) N1 - 2;
б) любая вершина множества N не лежит в блоке 2, т.е.
Уи / и є N ^ и £ Ш';
в) любая вершина множества и \ N лежит в блоке 2, т.е.
Уи / и є и \ N ^ и є Ш'.
Пусть GL =(уь, Еь) — предфрактальный граф, в траектории которого смежность старых ребер сохраняется. Следующая теорема дает оценку степени старой вершины.
Теорема 1.10 Если GL =(уь, Еь) — предфрактальный граф, в траектории которого смежность старых ребер сохраняется, Н = (Ш, О) — п -вершинная
^ тт п
затравка, породившая GL, степень каждой вершины Н не меньше —, V —
старая вершина GL, то степень вершины V не меньше п, т.е. р(у) - п.
Второй раздел диссертации содержит исследование метрических свойств предфрактальных графов, порожденных затравками, удовлетворяющими условию Оре.
Следующая лемма оценивает диаметр графа, удовлетворяющего условию
Оре.
Лемма 2.2 Если Н = (Ш, О) — п -вершинный граф, удовлетворяющий условию Оре, то d (Н )< 2.
Следующая лемма оценивает радиус графа, удовлетворяющего условию
Оре.
Лемма 2.3 Если Н = (ж, Q) — п -вершинный граф, удовлетворяющий условию Оре, то г (Н) < 2.
Следующие теоремы дают оценки диаметра предфрактального графа, в траектории которого смежность старых ребер сохраняется.
Теорема 2.1 Пусть GL =(уь, Еь) — предфрактальный граф, в траектории которого смежность старых ребер сохраняется, Н = (ж, Q) — п -вершинная затравка, породившая GL, Н удовлетворяет условию Оре, тогда верно неравенство d )< d (Н -1).
Теорема 2.2 Пусть GL =(уь, Еь) — предфрактальный граф, в траектории которого смежность старых ребер сохраняется, Н = (ж, Q) — п -вершинная затравка, породившая GL, Н удовлетворяет условию Оре, тогда верно неравенство d )> 2 L -1 + d (Н)-1.
Следующие теоремы дают оценки радиуса предфрактального графа, в траектории которого смежность старых ребер сохраняется.
Теорема 2.3 Пусть GL =(уь, Еь) — предфрактальный граф, в траектории которого смежность старых ребер сохраняется, Н = (ж, Q) — п -вершинная затравка, породившая GL, Н удовлетворяет условию Оре, тогда верно неравенство г -1)- d (Н)+г (Н).
Теорема 2.4 Пусть GL =(уь, Еь) — предфрактальный граф, в траектории которого смежность старых ребер сохраняется, Н = (ж, Q) — п -вершинная затравка, породившая GL, Н удовлетворяет условию Оре, тогда верно неравенство г )> L - г (Н).
Теорема 2.5 Пусть GL =(уь, Еь) — предфрактальный граф, в траектории которого смежность старых ребер сохраняется, Н = (ж, Q) — п -вершинная затравка, породившая GL, Н удовлетворяет условию Оре, степень каждой вершины Н меньше п -1, тогда верно неравенство г(GL) = 2L.
Третий раздел диссертации содержит описание и обоснование алгоритмов а1, ..., а4 распознавания предфрактальных графов.
Такие алгоритмы условно можно разделить на следующие группы:
• алгоритмы, распознающие предфрактальные графы общего вида, т.е.
графы, в траектории которых взаимное расположение старых ребер
может быть произвольным - алгоритмы а;, а4;
• алгоритмы, распознающие предфрактальные графы, в траектории
которых старые ребра не смежны - алгоритмы а2,а2';
• алгоритмы, распознающие предфрактальные графы, в траектории которых смежность старых ребер сохраняется - алгоритмы а3, а3'.
Алгоритм а1 распознает предфрактальные графы, порожденные
~ п
регулярной п-вершиннои затравкой степени не менее —.
Теорема 3.1 Всякий предфрактальный граф GL ={уь, Еь), порожденный затравкой, являющейся регулярным п -вершинным графом степени ^, с
условием ^ > п, распознается алгоритмом а1, причем если п = о(іп|EL |), то
т(а1) ~ o(EL |2 L), где т(а1) — трудоемкость алгоритма а1.
Алгоритмы а2,а2' распознают предфрактальные графы с затравкой, удовлетворяющей условию Оре, при несмежности старых ребер.
Теорема 3.2 Всякий предфрактальный граф GL =(уь, Еь), порожденный затравкой, удовлетворяющей условию Оре, при несмежности старых ребер распознается алгоритмом а2, причем если п = о(іпЕ|), то г(а2)~о(е1^|2L), где г(а2) — трудоемкость алгоритма а2, п — количество вершин затравки.
Теорема 3.2.1 Всякий предфрактальный граф GL =(уь, Еь), порожденный
п
п -вершинной затравкой, степень каждой вершины которой не меньше —, при
несмежности старых ребер, распознается алгоритмом а2', причем если п = о(іп|EL |), то г(а2') ~ o(EL|2L), где т(а2') — трудоемкость алгоритма а2'.
Алгоритмы а3,а3' распознают предфрактальные графы, порожденные затравкой, удовлетворяющей условию Оре, при сохранении смежности старых ребер.
Теорема 3.3 Всякий предфрактальный граф GL =(уь, Еь), порожденный затравкой, удовлетворяющей условию Оре, при сохранении смежности старых ребер распознается алгоритмом а3, причем если п = о(іп| EL |), то г(а3) ~ o(EL |2 L), где г(а3) — трудоемкость алгоритма а3, п — количество вершин затравки.
Теорема 3.3.1 Всякий предфрактальный граф GL =(уь, Еь), порожденный
п
п -вершинной затравкой, степень каждой вершины которой не меньше —, при
сохранении смежности старых ребер, распознается алгоритмом а3', причем если п = o(ln\EL|), то г(а3')~о(еі^|2L), где т(а3') — трудоемкость алгоритма а3'.
Алгоритм а4 распознает предфрактальные графы с п -вершинной
2п -1
затравкой, степень каждой вершины которой не менее
Теорема 3.4 Всякий предфрактальный граф GL = (V, Еь), порожденный п -вершинной затравкой Н = (ж, Q), степень каждой вершины которой не менее
—__—, распознается алгоритмом а4, причем если п = о(іпЕ|), то т(а4)~о(еь|2ь),
где г(а4) — трудоемкость алгоритма а4.
Основные результаты, полученные в диссертации:
1. Разработан и обоснован алгоритм распознавания предфрактальных графов, порожденных регулярными затравками; получена оценка его сложности.
2. Разработан и обоснован алгоритм распознавания предфрактальных графов, порожденных затравками, удовлетворяющими условию Оре, при несмежности старых ребер; получена оценка его сложности.
3. Разработан и обоснован алгоритм распознавания предфрактальных графов, порожденных затравками, удовлетворяющими условию Оре, при сохранении смежности старых ребер; получена оценка его сложности.
4. Разработан и обоснован алгоритм распознавания предфрактальных графов, порожденных п-вершинными затравками, степень каждой
2п _ 1
вершины которых не менее —-—; получена оценка его сложности.
5. Получены следующие оценки диаметра предфрактальных графов, порожденных затравками, удовлетворяющими условию Оре, при сохранении смежности старых ребер: 2L_2 + d(н)<d(GL)<d(н)■ ^_ 1), где d (Н) — диаметр затравки.
6. Получены следующие оценки радиуса предфрактальных графов, порожденных затравками, удовлетворяющими условию Оре, при сохранении смежности старых ребер: L■ г(н)<r(GL)<^_ 1)-d(н)+г(н), где г(н), d(н) — соответственно радиус и диаметр затравки.
7. Сформулирована и доказана теорема об окружении старой вершины предфрактального графа, в траектории которого смежность старых ребер сохраняется.
8. Сформулирована и доказана теорема об окружении старой вершины предфрактального графа, в траектории которого старые ребра не смежны.
Основные положения диссертации отражены в следующих публикациях:
Статьи в ведущих рецензируемых научных журналах и изданиях, входящих в перечень ВАК
1. Резников А.В. Распознавание предфрактальных графов с затравкой, удовлетворяющей условию Оре [текст] / А.В. Резников // Вестник Адыгейского государственного университета. - Майкоп, 2010. -Выпуск 2. - С. 34-39.
2. Резников А.В. Алгоритм распознавания предфрактальных графов с регулярной N-вершинной затравкой степени не менее N/2 [текст] / А.В. Резников, А.А. Кочкаров // Экологический вестник научных центров черноморского экономического сообщества. - Краснодар, 2010. - Выпуск 2. - С. 63-69.
3. Резников А.В. Распознавание предфрактальных графов с затравкой, удовлетворяющей условию Оре, при условии что смежность «старых» ребер в траектории предфрактального графа сохраняется [текст] / А.В. Резников // Вестник Адыгейского государственного университета. - Майкоп, 2011. - Выпуск 1. - С. 25-33.
Свидетельства о государственной регистрации программ для ЭВМ
4. Резников А.В. Программный комплекс для распознавания предфрактальных графов с регулярными затравками («Recognize 1.0») / А.В. Резников, А.А. Кочкаров // Свидетельство о государственной регистрации программы для ЭВМ, № 2010613649, 03.06.2010.
5. Резников А.В. Программный комплекс для распознавания предфрактальных графов с затравками, о структуре которых информация отсутствует («Recognize 2.0») / А.В. Резников, А.А. Кочкаров // Свидетельство о государственной регистрации программы для ЭВМ, № 2011611836, 28.02.2011.
Материалы и тезисы конференций, статьи в сборниках
6. Резников А.В. Об изучении алгоритмов распознавания образов [текст] / А.В. Резников // Актуальные проблемы углубленного математического образования: Материалы XXVII Пленума Учебно-методического совета по математике и механике и Всероссийской научно-методической конференции. - Майкоп, 2010. - С. 177-180.
7. Резников А.В. Распознавание предфрактальных графов с затравкой удовлетворяющей условию Оре [текст] / А.В. Резников // Сборник научных трудов по материалам международной научно-практической конференции «Перспективные инновации в науке, образовании, производстве и транспорте 2010». - Одесса, 2010. - С. 52-55.
8. Резников А.В. Распознавание предфрактальных графов, при условии сохранения смежности «старых» ребер [текст] / А.В. Резников // Математическое моделирование фрактальных процессов, родственные проблемы анализа и информатики: Материалы Первой Всероссийской конференции молодых ученых. - Терскол, 2010. - С. 140-143.
9. Резников А.В. Распознание предфрактальных графов [текст] / А.В. Резников // Математические методы и информационно-технические средства: труды VI Всерос. Науч.-практ. конф. -Краснодар, 2010. - С. 145-147.
10.Резников А.В. Алгоритм распознавания предфрактальных графов, при условии сохранения смежности «старых» ребер [текст] / А.В. Резников // «Наука. Образование. Молодежь»: Материалы VIII Международной научной конференции молодых ученых. - Майкоп, 2011. - С. 363-366.
Подписано в печать 6.11.2013 г. Формат 60*84/16. Бумага офсетная. Печать офсетная. Усл. печ. л. 1,0.
На правах рукописи
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
СЕВЕРО-КАВКАЗСКАЯ ГОСУДАРСТВЕННАЯ ГУМАНИТАРНО-ТЕХНОЛОГИЧЕСКАЯ АКАДЕМИЯ
РЕЗНИКОВ АНДРЕЙ ВЛАДИМИРОВИЧ
ИССЛЕДОВАНИЕ СВОЙСТВ И РАСПОЗНАВАНИЕ ПРЕДФРАКТАЛЬНЫХ ГРАФОВ
01.01.09 - Дискретная математика и математическая кибернетика
ДИССЕРТАЦИЯ
на соискание ученой степени кандидата физико-математических наук
Научный руководитель доктор физико-математических наук, профессор КОЧКАРОВ А.М.
Черкесск - 2013
ОГЛАВЛЕНИЕ
ВВЕДЕНИЕ...............................................................................................................................4
ГЛАВА 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. Алгоритм распознавания предфрактальных графов с регулярной п-вер шинной затравкой степени не менее п/2............................................................................................43
3.2. Алгоритмы распознавания предфрактальных графов, в траектории
которых старые ребра не смежны........................................................................................53
3.3. Алгоритмы распознавания предфрактальных графов, в траектории
которых смежность старых ребер сохраняется.................................................................67
3.4. Алгоритм распознавания предфрактальных графов с п -вершинной затравкой,
2п -1 0/1 степень каждой вершины которой не менее —-—............................................................84
ЗАКЛЮЧЕНИЕ.......................................................................................................................96
СПИСОК СОКРАЩЕНИЙ И УСЛОВНЫХ ОБОЗНАЧЕНИЙ......................................98
ЛИТЕРАТУРА........................................................................................................................99
ПРИЛОЖЕНИЕ A. КОМПЛЕКС ПРОГРАММ ПО РАСПОЗНАВАНИЮ ПРЕДФРАКТАЛЬНЫХ ГРАФОВ.....................................................................
118
ВВЕДЕНИЕ
Актуальность диссертационного исследования
Любые сложные системы [1-6], такие как информационные, энергетические, управленческие, претерпевают с течением времени определенные, вызванные внешними причинами, изменения [7-11]. Довольно часто структуры таких систем уместно представлять в виде графа [12-29]. В работах F. Harari (1973) [28], C. Berge (1962) [22], В.А. Емеличева (1990) [12] и других рассматриваются операции над графами, такие как объединение, соединение, произведение, композиция, стягивание дуги и пр. С помощью этих операций можно описать изменения, происходящие в структурах сложных систем. Структуры систем могут претерпевать как разовые, так и регулярные изменения. Обобщением случая регулярных изменений является понятие структурной динамики [30-32].
Общеизвестным сценарием структурной динамики является рост структуры — регулярное появление элементов и связей в структуре системы. В некоторых случаях для описания роста структуры используется перечень правил, причем такие правила могут допускать элемент случайности [7-11].
В настоящей работе рассматривается правило, задающее структурную динамику сложных систем. Результатом применения этого правила являются так называемые самоподобные (self-similar graphs) [33-49] или фрактальные графы [5092].
Фрактальный граф — это сложная абстрактная структура, обладающая свойствами фракталов и «простых» графов. В разных научных школах применяются различные правила построения структурной динамики, что в результате приводит к различным, по строению, самоподобным графам. По данной тематике написано множество статей в российских и зарубежных научных журналах. В статье F.G. Arenas, M.A. Sanchez-Granero (2000) [39] исследуются графы, построенные на множестве точек отрезка [0,1]. В работах E. Teufl, S. Wagner (2000) [38]; B. Krön
(2002) [35]; B. Krön, E. Teufl (2004) [36, 37]; L. Malozemov, A. Teplyaev (2003) [40]; D. D'Angeli, A. Donno (2010) [48] изучаются свойства графов, каждый из которых состоит из множества изоморфных подграфов, причем последние могут иметь ровно одну общую вершину. Свойства графов, полученных «дискретизацией» фрактальных множеств, описали в своих трудах V. Nekrashevych (2007) [44]; D. Guido, T. Isola, M. Lapidus (2009) [46]. Самоподобные графы древовидной структуры исследованы в статье J. Neunhäuserer (2007) [45].
Другие способы построения самоподобных графов, а также вопросы практического применения фрактальных множеств рассмотрены в работах F. Comellas, A. Miralles (2009) [47]; C. Lee, P-S. Loh, B. Sudakov (2012) [49]; В.А. Бондаренко, В.Л. Дольников (1994) [93].
Понятие фрактал [93-142], введенное Бенуа Мандельбротом [117], объединило объекты, обладающие особым свойством — свойством самоподобия (self-similar). Работы, связанные с исследованием фрактальных объектов, фрактальных множеств, долгое время считались интересными, но не имеющими серьезных практических приложений. Мнения в мировой научной среде изменились после издания книги «Фракталы в физике» [138, 143]. В настоящее время о перспективности и значимости исследований можно судить по регулярно проводимым конференциям и периодическим изданиям, полностью посвященным соответствующей тематике, и большому количеству книг, учебников и монографий [95, 117, 136, 138, 141, 143, 144]. Это позволяет говорить о сформировавшемся круге прикладных физических задач на основе фрактальных множеств [33-37, 145-152]. Среди них выделяются задачи и модели, в которых фрактальные множества представлены как самоподобные, масштабно-инвариантные графы большой размерности, т.е. с большим количеством вершин. К ним относятся, например задачи о броуновском движении, диффузии и просачиваемости. Кроме того, самоподобные графы нередко выступают в качестве моделей структур сложных многоэлементных систем, таких как коммуникационные сети.
Изучение фрактальных графов и их приложений ведется под руководством профессора А.М. Кочкарова. Наиболее активно прорабатываются задачи многокритериальной оптимизации в системах с фрактальной структурой [67-92] и вопросы выявления свойств и характеристик графов [32, 50-66, 71, 79-80, 84]. Метрические свойства исследуются в работах А.М. Кочкарова [50].
В работе Д.А. Павлова [71] построены оценки метрическим характеристикам предфрактального графа с затравкой простая цепь, в монографии Кочкарова А.А. [32] получены оценки диаметра и радиуса произвольных предфрактальных графов и некоторых классов графов при сохранении смежности старых ребер.
Другим направлением исследования является распознавание фрактальных (предфрактальных) графов [42, 43, 50, 52]. Предфрактальные графы состоят из конечного количества элементов (вершин и ребер), поэтому любая задача распознавания таких графов допускает переборное решение. Для практических задач важен не факт существования алгоритма распознавания [153-172], а важно наличие эффективного алгоритма решения поставленной задачи. Наиболее «быстрыми» являются, как известно, полиномиальные алгоритмы [173-176]. Разработка таких алгоритмов является одной из целей данной работы.
В частности, А.М. Кочкаровым (1998) [50] разработаны полиномиальные алгоритмы распознавания предфрактальных графов с полными затравками, некоторых предфрактальных деревьев, некоторых предфрактальных графов с регулярными затравками. Вопросы распознавания предфрактальных графов также исследуются в работах Е.В. Бобылевой (2005) [42]; Е.М. Киселевой, Е.В. Бобылевой (2005) [43]; И.Х. Утакаевой (2007) [177]; Л.Х. Хапаевой, А.М. Кочкарова (2011) [178] и других [180-189].
Цель и задачи исследования 1. Исследование структуры предфрактальных графов.
2. Выявление свойств и характеристик предфрактальных графов с различными затравками.
3. Разработка алгоритмов распознавания предфрактальных графов.
Методы исследования
В диссертационной работе используются методы исследования операций,
теории графов, теории предфрактальных и фрактальных графов, теории алгоритмов
и сложности алгоритмов, комбинаторики.
Научная новизна исследования
1. Предложен алгоритм распознавания предфрактальных графов, порожденных регулярными затравками.
2. Предложен алгоритм распознавания предфрактальных графов, порожденных затравками, удовлетворяющими условию Оре, при несмежности старых ребер.
3. Предложен алгоритм распознавания предфрактальных графов, порожденных затравками, удовлетворяющими условию Оре, при сохранении смежности старых ребер.
4. Предложен алгоритм распознавания предфрактальных графов, порожденных п-
2п -1
вершинными затравками, степень каждой вершины которых не менее —-—.
5. Получены оценки диаметра предфрактальных графов, порожденных затравками, удовлетворяющими условию Оре, при сохранении смежности старых ребер.
6. Получены оценки радиуса предфрактальных графов, порожденных затравками, удовлетворяющими условию Оре, при сохранении смежности старых ребер.
Основные положения (научные выводы), выносимые на защиту
1. Эффективные полиномиальные алгоритмы распознавания предфрактальных графов.
2. Теорема об окружении вершины предфрактального графа, в траектории которого старые ребра не смежны (теорема 1.6).
3. Теорема об окружении старой вершины предфрактального графа, в траектории которого смежность старых ребер сохраняется (теорема 1.9).
4. Оценки диаметра и радиуса предфрактальных графов, порожденных затравками, удовлетворяющими условию Оре, при сохранении смежности старых ребер.
Практическая ценность и теоретическая значимость исследования
В диссертационной работе получен ряд результатов, позволяющих расширить область применения теории графов.
Апробация результатов исследования
Основные результаты работы докладывались на конференциях:
1. Первая Всероссийская конференция молодых ученых «Математическое моделирование фрактальных процессов, родственные проблемы анализа и информатики», Россия, п. Терскол, 2010;
2. Всероссийская научно-методическая конференция «Актуальные проблемы углубленного математического образования», Майкоп, 2010;
3. Международная научно-практическая конференция «Перспективные инновации в науке, образовании, производстве и транспорте 2010», Одесса, 2010;
4. VI Всероссийская научно-практическая конференция «Математические методы и информационно-технические средства», Краснодар, 2010;
5. VII Международная научная конференция молодых ученых «Наука. Образование. Молодежь», Майкоп, 2011.
По теме диссертации имеются 8 публикаций, в том числе 3 статьи в журналах из списка ВАК, тезисы докладов в материалах двух Всероссийских конференций, тезисы докладов в материалах двух международных конференций. На разработанные алгоритмы получено 2 свидетельства о государственной регистрации программ для ЭВМ.
Статья «Алгоритм распознавания предфрактальных графов с регулярной N вершинной затравкой степени не менее N/2» [180] была написана в соавторстве с А.А. Кочкаровым. В ней автором А.В. Резниковым было дано определение
показателя блока первого ранга; были сформулированы и доказаны самостоятельно леммы 1, 2 и 4, теоремы 1 и 2; самостоятельно был получен и обоснован алгоритм распознавания. Всего А.В. Резникову принадлежит 0,625 п. л. из 0,875 п. л. в указанной статье.
Программный комплекс для распознавания предфрактальных графов с регулярными затравками («Recognize 1.0») [182] был разработан в соавторстве с А.А. Кочкаровым. В нем А.В. Резниковым были самостоятельно созданы процедуры проверки необходимых условий предфрактальности графов и процедуры распознавания графов. Всего А.В. Резникову принадлежит 75% программного кода в указанном комплексе.
Программный комплекс для распознавания предфрактальных графов с затравками, о структуре которых информация отсутствует («Recognize 2.0») [183] был разработан в соавторстве с А.А. Кочкаровым. В нем А.В. Резниковым были самостоятельно созданы процедуры проверки необходимых условий предфрактальности графов и процедуры распознавания графов. Всего А.В. Резникову принадлежит 77% программного кода в указанном комплексе.
В приложении А приведен текст программы, реализующей все, приведенные в диссертации, алгоритмы распознавания предфрактальных графов.
Структура диссертации
Поставленные задачи определили структуру работы и содержание отдельных разделов. Диссертация состоит из введения, трех разделов, заключения, списка использованных источников и приложения. Она изложена на 117 страницах машинописного текста (без приложений), содержит 42 рисунка, одно приложение, список использованных источников из 189 наименований.
ГЛАВА 1. ОПРЕДЕЛЕНИЕ, ПОНЯТИЯ, СВОЙСТВА ПРЕДФРАКТАЛЬНЫХ ГРАФОВ И ИХ ЗАТРАВОК
1.1. Основные определения и понятия
Основными рассматриваемыми объектами данной работы являются предфрактальные графы [50].
Определению предфрактального графа предшествуют дополнительные определения и понятия.
Термином затравка [50] условимся называть какой-либо фиксированный связный п -вершинный граф H = (ж, Q) с непомеченными вершинами.
Определим операцию замещения вершины затравкой (ЗВЗ) [50], которая является обобщением операции расщепления вершины графа [12]. Суть операции ЗВЗ состоит в следующем. В данном графе G = (¥, Е) у намеченной для замещения вершины у0 ( у0 е V) выделяется ее окружение [12], т.е. множество и0 всех вершин, смежных с вершиной у0 , и множество ребер R0, инцидентных вершине у0 , R0 = {е = v0u / е е Е, и е и0}.
Определим некоторое отображение р множества вершин и0 во множество вершин затравки Ж:
р: и0 ^Ж ,
т.е. каждой вершине и' (и'е и0) ставим в соответствие, определяемую с помощью р, вершину затравки V = р(и').
После этого, у каждого ребра е = v0u (е е R0) из множества R0 конец V, заменяется на определяемую отображением р вершину V = р(и) затравки Н.
«Старое» ребро е = у0и удаляется из графа G и появляется в нем в «новом» измененном виде е = уи .
Множеством вершин получаемого графа является исходное множество вершин V, за исключением замещаемой вершины у0, но с добавлением множества вершин затравки W, т.е. множеством вершин получаемого графа будет являться множество
V и Ж \ {у0} (рисунок 1).
G
H
G
Рисунок 1. Применение операции ЗВЗ к вершине у2 графа G = ({у, у2, у3}, {е1, е2}) и затравке Н = (^, q2}),
с использованием отображения р/р(у) = w1, рру3) = .
Результат операции — граф G' = ({у, у3, w1, w2, w3}, {е/, е2', q1, q2}).
Определим поэтапный процесс выполнения операции ЗВЗ. На этапе я = 1 затравку Н = (Ж, обозначаем как граф G1 = V Е1).
Пусть выполнены этапы я = 1,2,...,/, и по завершению этапа / получен граф 01 = V,Е), который назовем предфрактальным графом. На этапе я = / +1 для каждой вершины у (у еV/) осуществляется операция ЗВЗ, т.е. замещение каждой вершины затравкой Н. В процессе выполнения всех операций ЗВЗ на данном этапе все ребра е е Е1 сохраняются и называются старыми ребрами по отношению ко всем графам ^+1,.^+2,..,ОЬ, где Ь > 1. Причем, старые ребра, инцидентные замещаемой вершине у е¥1, становятся, случайным или регулярным образом, инцидентными некоторым вершинам затравки, заместившей вершину у . Ребра каждой из таких появившихся
затравок называют новыми ребрами, т.е. множество всех новых ребер есть множество Е1+1 \ Е1.
Далее будем рассматривать предфрактальный граф GL =(УЬ, Еь), порожденный произвольной п -вершинной затравкой Н = (ж, Q).
Ребра, появившиеся на I-ом этапе порождения I е{1,2,...,ь\, будем называть ребрами ранга I [50].
Если из графа Оь удалить все ребра рангов 1,...,L -1, то исходный граф распадается на множество связных компонент В<1), каждая из которых изоморфна затравке Н. Множество компонент В([> будем называть блоками первого ранга [50]. Аналогично, при удалении из ребер рангов 1,...,L - 2, получим множество В{р блоков второго ранга. Очевидно, что всякий блок второго ранга является предфрактальным графом ранга 2, порожденным затравкой Н. Аналогично определяются множества блоков остальных рангов В{3,...,вLL-1) [50]. Всякий блок ранга к (к = 1,L -1) является предфрактальным графом ранга к.
1.2. Свойства предфрактальных графов, порожденных регулярными затравками
Следующая лемма устанавливает, что существует не более одного ребра, соединяющего два блока одного ранга.
Лемма 1.1 Для любых двух блоков М{[] =(г(1),Е(1)) и =(к(2),Е(2)) ранга к (к = 1,L -1) (м£),М{1 В(1)) существует не более одного ребра е = у1у2, такого что
V е¥(1),у2 е¥(2).
Доказательство.
Иными словами, требуется доказать, что блоки М{[} и соединены не более чем одним ребром. Пусть блоки М^ и МL2) сое�
