Исследование свойств и распознавание предфрактальных графов тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат физико-математических наук Резников, Андрей Владимирович

• Резников, Андрей Владимирович
• кандидат физико-математических наук
• 2013

Оглавление диссертации кандидат физико-математических наук Резников, Андрей Владимирович

ВВЕДЕНИЕ.

ГЛАВА 1. ОПРЕДЕЛЕНИЕ, ПОНЯТИЯ, СВОЙСТВА ПРЕДФРАКТАЛЬНЫХ ГРАФОВ И ИХ ЗАТРАВОК.

1.1. Основные определения и понятия.

1.2. Свойства предфрактальных графов, порожденных регулярными затравками.

1.3. Свойства затравок предфрактальных графов.

1.4. Свойства предфрактальных графов при несмежности старых ребер.

1.5. Свойства предфрактальных графов при сохранении смежности старых ребер.

ГЛАВА 2. МЕТРИЧЕСКИЕ СВОЙСТВА ПРЕДФРАКТАЛЬНЫХ ГРАФОВ.

2.1. Основные метрические характеристики графов.

2.2. Оценки диаметра предфрактальных графов, порожденных затравками, удовлетворяющими условию Оре.

2.3. Оценки радиуса предфрактальных графов, порожденных затравками, удовлетворяющими условию Оре.

ГЛАВА 3. АЛГОРИТМЫ РАСПОЗНАВАНИЯ ПРЕДФРАКТАЛЬНЫХ ГРАФОВ.

3.1. Алгоритм распознавания предфрактальных графов с регулярной п-вер шинной затравкой степени не менее п/2.

3.2. Алгоритмы распознавания предфрактальных графов, в траектории которых старые ребра не смежны.

3.3. Алгоритмы распознавания предфрактальных графов, в траектории которых смежность старых ребер сохраняется.

3.4. Алгоритм распознавания предфрактальных графов с п -вершинной затравкой,

2п -1 0/1 степень каждой вершины которой не менее —-—.

Введение диссертации (часть автореферата) на тему «Исследование свойств и распознавание предфрактальных графов»

Актуальность диссертационного исследования

Любые сложные системы [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 наименований.

Заключение диссертации по теме «Дискретная математика и математическая кибернетика», Резников, Андрей Владимирович

Выводы: алгоритм а4, будучи примененный к произвольному графу, обозначаемому здесь как G = (V, Е), будет давать положительный результат в тех и только тех случаях, когда граф G окажется предфрактальным графом, порожденным затравкой, обозначаемой здесь как п -вершинный граф Н = (Ж, Q), причем степень

2п -1 каждой вершины затравки не меньше —-—.

Алгоритм а4, помимо положительного ответа на вопрос о предфрактальности графа G, определяет затравку Н, которая породила граф G, т.е. определяет количество вершин затравки, степень каждой вершины затравки, а также информацию о смежности вершин затравки. Такая информация может быть представлена, например, в виде матрицы смежности. Также алгоритм а4 вычисляет номер L этапа построения предфрактального графа G.

В том случае, если граф G принадлежит одновременно сразу нескольким траекториям построения предфрактальных графов, причем траектории порождены

2п-1 п -вершинными затравками, степень каждой вершины которых не меньше —-—, то алгоритм а4 определит все такие затравки и для каждой траектории вычислит номер

L этапа построения, на котором возникнет граф G.

Во всех остальных случаях, в том числе и когда граф G не является предфрактальным графом; и когда граф G является предфрактальным графом, но порожден п -вершинной затравкой, степень не каждой вершины которой не меньше

2п-1 ~ ,

-—, алгоритм а4 выдаст отрицательный ответ на вопрос о предфрактальности графа G.

Теорема 3.4 Всякий предфрактальный граф Оь = (уь, Еь), порожденный п -вершинной затравкой Н = (Ж , О), степень каждой вершины которой не менее , распознается алгоритмом а4, причем, если п = о(1п| Еь |), то т(а4) ~ о(еь |2 L), где т(а4) — трудоемкость алгоритма а4.

Доказательство.

Распознаваемость предфрактального графа GL = (уь, Еь), порожденного затравкой Н = (Ж, О), доказана в описании алгоритма а4.

Пусть А — произвольный алгоритм, принимающий вход длины т . Обозначим за /(А, т) — число элементарных операций, которые потребуются для его выполнения.

Алгоритм а4 начинается с проверки необходимых условий предфрактальности. Обозначим за В алгоритм такой проверки. Следуя доказательству теоремы 3.1, сложность проверки необходимых условий предфрактальности графа оценивается следующим образом: / (в, уь |) = |).

Оценим сложность алгоритма выделения затравки /34 на шаге р. Алгоритм состоит из следующих операций:

1) операция С1: выделение неотмеченной вершины V, степени меньшей п ;

2) операция С2: выделение окружения и1 вершины vl;

3) операция С3: выделение максимальной компоненты связности О" подграфа, порожденного множеством и1;

4) операция С4: составление и2 — множества вершин подграфа О";

5) операция С5: выделение множества вершин и3, каждая из которых смежна хотя бы с двумя вершинами множества и2 ;

6) операция С6: проверка изоморфности подграфа на множестве вершин {^}и и2 и и3 регулярному графу, полученному на предыдущих шагах.

Действуя аналогично доказательству теоремы 3.1, оценим сложность операций

С -Сб: /С,) = ), /(С2,|Еь|) = о(Еь|), /(с4,|Еь\) = о(1), /(с5,|Еь\) = о(Еь|),

С6, п)= о(еь |). Для оценки сложности операции С3 нужно заметить, что компоненты связности можно найти алгоритмом обхода графа в глубину. А сложность этого алгоритма — линейная. Поэтому / (с3 , |) = |).

Следовательно, сложность алгоритма выделения затравки (4 оценивается следующим образом: / ((4, |Ei |) = о( Еь |).

Обозначим за алгоритм выполнения этапа р = г. Действуя аналогично доказательству теоремы 3.1, имеем /(яг,|Ei|) = о(еь|2). Окончательное обоснование верхней оценки трудоемкости алгоритма а4 получаем из того, что число этапов этого алгоритма не превосходит Ь. ■

ЗАКЛЮЧЕНИЕ

В диссертационной работе исследованы свойства предфрактальных графов и свойства затравок предфрактальных графов. Получены следующие новые результаты:

1. Разработан и обоснован алгоритм распознавания предфрактальных графов, порожденных регулярными затравками; получена оценка его сложности.

2. Разработан и обоснован алгоритм распознавания предфрактальных графов, порожденных затравками, удовлетворяющими условию Оре, при несмежности старых ребер; получена оценка его сложности.

3. Разработан и обоснован алгоритм распознавания предфрактальных графов, порожденных затравками, удовлетворяющими условию Оре, при сохранении смежности старых ребер; получена оценка его сложности.

4. Разработан и обоснован алгоритм распознавания предфрактальных графов, порожденных п-вершинными затравками, степень каждой вершины которых не

2п -1 менее —-—; получена оценка его сложности.

5. Получены следующие оценки диаметра предфрактальных графов, порожденных затравками, удовлетворяющими условию Оре, при сохранении смежности старых ребер: 2Ь - 2 + d (Н )< d (GL )< d (Н )(2Ь -1), где d (Н) — диаметр затравки.

6. Получены следующие оценки радиуса предфрактальных графов, порожденных затравками, удовлетворяющими условию Оре, при сохранении смежности старых ребер: Ь • г(н )< )<(ь -1)-d (Н)+ г(н ), где г(н ), d (Н) — соответственно радиус и диаметр затравки.

7. Сформулирована и доказана теорема об окружении старой вершины предфрактального графа, в траектории которого смежность старых ребер сохраняется.

8. Сформулирована и доказана теорема об окружении старой вершины предфрактального графа, в траектории которого старые ребра не смежны.

СПИСОК СОКРАЩЕНИЙ И УСЛОВНЫХ ОБОЗНАЧЕНИЙ

ЗВЗ — замещение вершины затравкой;

G = (V,Е) — простой граф, у которого V - множество вершин, Е - множество ребер; р (у) — степень вершины V; Мвх^) — показатель блока Z.

Список литературы диссертационного исследования кандидат физико-математических наук Резников, Андрей Владимирович, 2013 год

1. Лоскутов, А.Ю. Основы теории сложных систем / А.А. Лоскутков,

2. A.С. Михайлов. М.: Ижевск: НИЦ «Регулярная и стохастическая динамика», 2007. - 620 с.

3. Растригин, Л.А. Адаптация сложных систем / Л.А. Растригин. Рига: Зинатне, 1981. - 375 с.

4. Мамчур, Е.А. Принцип простоты и меры сложности / Е.А. Мамчур, Н.Ф. Овчинников, А.И. Уемов. М.: Наука, 1989. - С. 162-164.

5. Боулдинг, К. Общая теория систем скелет науки / К. Боулдинг // Исследования по общей теории систем. - М.: Прогресс, 1969. - С. 106-124.

6. Сегал, В.В. Анализ и синтез сложных систем / В.В. Сегал. К.: ЦЭМИ «Тридента», 1994. - 157 с.

7. Бусленко, И.В. Лекции по теории сложных систем / И.В. Бусленко,

8. B.В. Калашников, И.Н. Коваленко. М.: Советское радио, 1975. - 441 с.

9. Strogatz, S. Exploring complex networks / S. Strogatz // Nature. 2001. - № 410. -P. 268-276.

10. Watts, D.J. Small Worlds / D.J. Watts. Princeton: Princeton University Press, 1999. - 280 p.

11. Dorogovtsev, S.N. Evolution of networks / S.N. Dorogovtsev, J.F.F. Mendes // Adv. Phys. 2002. - № 51. - P. 1079-1187.

12. Dorogovtsev, S.N. Evolution of networks: From Biological Nets to the Internet and WWW / S.N. Dorogovtsev, J.F.F. Mendes. Oxford: Oxford University Press, 2003. -280 p.

13. Albert, R. Statistical mechanics of complex networks / R. Albert, A. Bambasi // Reviews of Modem Physics. 2002. - № 74. - P. 47-97.

14. Лекции по теории графов / В.А. Емеличев и др.. М.: Наука, 1990. - 384 с.

15. Асанов, М.О. Дискретная математика: графы, матроиды, алгоритмы / М.О. Асанов, В.А. Баранский, В.В. Расин. Ижевск: НИЦ «РХД», 2001. - 288 с.

16. Ловас, Л. Прикладные задачи теории графов. Теория паросочетаний в математике, физике, химии / Л. Ловас, М. Пламмер. М.: Мир, 1998. - 658 с.

17. Свами, М. Графы, сети и алгоритмы / М. Свами, К. Тхуласираман. М.: Мир, 1984. - 455 с.

18. Майника, Э. Алгоритмы оптимизации на графах и сетях/ Э. Майника. М.: Мир, 1981. - 323 с.

19. Кристофидес, Н. Теория графов. Алгоритмический подход / Н. Кристофидес. -М.: Мир, 1978. 432 с.

20. Фляйшнер, Г. Эйлеровы графы и смежные вопросы / Г. Фляйшнер. М.: Мир, 2002. - 335 с.

21. Татт, У. Теория графов / У. Татт. М.: Мир, 1988. - 424 с.

22. Басакер, Р. Конечные графы и сети / Р. Басакер, Т. Саати. М.: Наука, 1974. -368 с.

23. Зыков, А.А. Теория конечных графов / А.А. Зыков. Новосибирск: Наука, 1969.- 554 с.

24. Берж, К. Теория графов и ее применения / К. Берж. М.: Изд-во иностр. лит., 1962. - 320 с.

25. Ope, О. Теория графов / О. Оре. М.: Наука, 1968. - 352 с.

26. Оре, О. Графы и их применение / О. Оре; пер. с англ. Л.И. Головиной; под ред. И.М. Яглома. Новокузнецк (Кемеров. обл.) : ИО НФМИ, 2000. - 173 с.

27. Уилсон, Р. Введение в теорию графов / Р. Уилсон. М.: Мир, 1977. - 208 с.

28. Березина, Л.Ю. Графы и их применение: пособие для учителей / Л.Ю. Березина.- М.: Просвещение, 1979. 143 с. с ил.

29. Дистель, Р. Теория графов / Р. Дистель. Новосибирск: Издательство Института Математики СО РАН, 2002. - 336 с.

30. Харари, Ф. Теория графов / Ф. Харари; пер. с англ. и предисл. В.П. Козырева; под ред. Г.П. Гаврилова. Изд. 2-е. - М.: Едиториал УРСС, 2003. - 296 с.

31. Ерусалимский, Я.М. Нестандартная достижимость на ориентированных графах и сетях: автореф. дис. . д-ра физ.-мат. наук: 01.01.09 / Я.М. Ерусалимский; Ярославский государственный университет им. П.Г. Демидова. Ярославль, 2012. - 36 с.

32. Круглый, А.Л. Модель динамики дискретного пространства времени / А.Л. Круглый. М.: Монолог, 2000. - 88 с.

33. Кочкаров, А. А. Структурная динамика: Свойства и количественные характеристики предфрактальных графов: монография / А. А. Кочкаров. М.: Вега-Инфо, 2012. - 120 с.

34. Мэлроуз, Дж. Иерархические фрактальные графы и блуждания в них / Дж. Мэлроуз // Фракталы в физике. М.: Мир, 1988. C. 507-512.

35. Riehl, J. Fractal graph optimization algorithms / J. Riehl, J.P. Hespanha // Proc, of the 44th Conf. on Decision and Contr., 2005. P. 2188-2193.

36. Krön, B. Green functions on self-similar graphs and bounds for the spectrum of the Laplacian/ B. Krön // Ann. Inst. Fourier (Grenoble). 2002. - 52(6). - P. 1875-1900

37. Krön, B. Growth of self-similar graphs / B. Krön // Journal Graph Theory. 2004. -Vol. 45, №3. - P. 224-239.

38. Krön, В. Asymptotics of the transition probabilities of the simple random walk on self-similar graphs / B. Krön, E. Teufl // Trans. Amer. Math. Soc. 2004. - Vol. 356, №1. - P. 393-414.

39. Teufl, E. The number of spanning trees of finite sierpinski graphs / E. Teufl, S. Wagner // Fourth Colloquium on Mathematics and Computer Science, volume AG of DMTCS Proceedings. 2006. - P. 411-414.

40. Arenas, F. Every Graph is a Self-Similar Set / F. Arenas, M. Sanchez-Granero // Divulgaciones Matematicas . 2000. - Vol. 8, №. 1. - P. 51-56.

41. Malozemov, L. Self-Similarity, Operators and Dynamics / L. Malozemov, Teplyaev A. // Mathematical Physics, Analysis and Geometry. 2003. - Vol. 6, №.3. -P. 201-218.

42. Nekrashevych, V. Hyperbolic spaces from self-similar group actions / V. Nekrashevych // Algebra and Discrete Mathematics. -2003. № 2. - P. 68-77.

43. Бобылева, Е. В. Частный случай задачи распознавания полного неканонического предфрактального графа / Е. В. Бобылева // Математичт машини 14 i системи. -2005. № 2. - C. 3-14.

44. Киселева, Е. М. Обобщенный алгоритм распознавания предфрактального графа / Е. М. Киселева, Е. В. Бобылева // Проблемы управления и информатики. 2005. - № 2. - C. 82-92.

45. Nekrashevych, V. Self-similar graphs, algebras and fractals / V. Nekrashevych. INI, Cambridge, 2007.

46. Neunhäuserer, J. Random walks on infinite self-similar graphs / J. Neunhäuserer // Electronic Journal of Probability. 2007. - Vol. 12. - P. 1258-1275.

47. Guido, D. A trace on fractal graphs and the ihara zeta function / D. Guido, T. Isola, M. Lapidus // Transactions of the american mathematical society. 2009. - V. 361, № 6. -P. 3041-3070.

48. Comellas, F. Modeling complex networks with self-similar outerplanar unclustered graphs / F. Comellas, A. Miralles // Preprint submitted to Physica A 2009. - Vol. 388, №.11. - С. 2227-2233.

49. D'Angeli, D. Weighted spanning trees on some self-similar graphs / D. D'Angeli, A. Donno // The electronic journal of combinatorics. 2001. - Vol. 18, №P16. - 28 p.

50. Lee, C. Self-similarity of graphs / C. Lee , P.-S. Loh, B. Sudakov. Preprint, 2012. -P. 959-972.

51. Кочкаров, A.M. Распознавание фрактальных графов. Алгоритмический подход. /

52. A. М. Кочкаров. Нижний Архыз: РАН САО, 1998. - 170 с.

53. Кочкаров, A. M. Фрактальные графы и их размерность / A. M. Кочкаров,

54. B. А. Перепелица, Л. Н. Сергеева. Черкесск, 1996. - Библиогр.: С. 1-34. - Деп. в ВИНИТИ, № 3284-В96.

55. Салпагаров, C. M. Распознавание предфрактального графа с полной двудольной затравкой / С. М. Салпагаров, А. М. Кочкаров. Черкесск: КЧГТА, 2003. -Библиогр.: С. 1-43. - Деп. в ВИНИТИ, № 2322-В2003.

56. Кочкаров, А. А. Число всевозможных предфрактальных графов / А. А. Кочкаров // IV Всероссийский симпозиум «Математическое моделирование и компьютерные технологии». Тез. докл., том 2. Кисловодск: КИЭП, 2000.1. C. 73-74.

57. Кочкаров, А. А. Исследование связности предфрактальных графов / А. А. Кочкаров, Р. А. Кочкаров // IV Всероссийский симпозиум «Математическое моделирование и компьютерные технологии». Тез. докл., том 2. Кисловодск: КИЭП, 2000. - С. 74-75.

58. Кочкаров, А. А. Плоские и планарные предфрактальные графы / А. А. Кочкаров // V Всероссийский симпозиум «Математическое моделирование и компьютерные технологии». Тез. докл. Кисловодск: КИЭН, 2002. - С. 35-35.

59. Кочкаров, А. А.Число мостов предфрактального графа / А. А. Кочкаров, С. И. Салпагаров // V Всероссийский симпозиум «Математическое моделирование и компьютерные технологии». Тез. докл. Кисловодск: КИЭН, 2002. - С. 36-37.

60. Кочкаров, А. А. О критериях планарности фрактальных графов / А. А. Кочкаров, Р. А. Кочкаров // Труды XLVI научной конференции МФТИ «Современные проблемы фундаментальных и прикладных наук». Часть VII. М.: МФТИ, 2003. -С. 186-186.

61. Кочкаров, А. А. Предфрактальные графы в проектировании и анализе сложных структур / А. А. Кочкаров, Р. А. Кочкаров . (Препринт / ИПМ им. М.В. Келдыша РАН). - М., 2003. - № 10.

62. Кочкаров, А. А. О планарности и других топологических свойствах фрактальных графов / А. А. Кочкаров, Р. А. Кочкаров. (Препринт / ИПМ им. М.В. Келдыша РАН).- М., 2003. - № 83.

63. Кочкаров, А. М. Хроматическое число и хроматический индекс фрактальных графов / А. М. Кочкаров // Республиканская конференция преподавателей и аспирантов КЧТИ. Тез. докл. Черкесск: КЧТИ, 1997. - С. 56-57.

64. Кочкаров, А. М. Топологические характеристики теоретико-графовой модели крупномасштабной кластеризации материи во Вселенной / А. М. Кочкаров. -(Препринт / РАН САО). Нижний Архыз, 1998. - С. 1-6.

65. Кочкаров, А. М. Число внутренней устойчивости предфрактального и фрактального графа / А. М. Кочкаров, В. А. Перепелица // Сб. статей. РАН САО. 1999.

66. Kochkarov, A. Fractal Graphs and Their Properties / A. Kochkarov, V. Perepelitsa // ICM 1998 Berlin, International Congress of Mathematicians, Abstracts of Short Communications and Posters. 1998. - 347 p.

67. Айбазов, Б. А. Экономико-математическая модель с виртуальными каналами / Б.А. Айбазов, A.M. Кочкаров // IV Научно-практическая конференция «Решение научно-технических и социально-экономических проблем современности». Труд. конф. Черкесск: КЧТИ. - 2002.

68. Павлов, Д. А. Нахождение диаметральной простой цепи на фрактальном и предфрактальном графах / Д. А. Павлов // XVI Международная научнаяконференция «Математические методы в технике и технологиях ММТТ-16». Сб. труд. - С.-Пб.: СПбГТИ, 2004.

69. Павлов, Д. А. Полиномиальный алгоритм нахождения максимального паросочетания на предфрактальных графах / Д. А. Павлов // XVII Международная научная конференция «Математические методы в технике и технологиях -ММТТ-17». Сб. труд. Кострома: КГТУ, 2004.

70. Салпагаров, С. И. Задача о назначениях на фрактальных и предфрактальных графах. Многокритериальная постановка. Черкесск, КЧГТА, 2003. - Библиогр.: - С. 1-34.- Деп. в ВИНИТИ, № 2323-В2003.

71. Кочкаров, Р. А. Полиномиальные быстрые алгоритмы нахождения остовного дерева минимального веса / Р. А. Кочкаров, С. И. Салпагаров. Черкесск, Карачаево-Черкесская Гос. Технолог. Ак., 2002. - Библиогр.: - С. 1-75. - Деп. в ВИНИТИ, № 437-В2002.

72. Батчаев, И. З. Об одной многокритериальной задаче покрытия предфрактальных графов звездами одного рангового типа / И. З. Батчаев // Известия Кабардино-Балкарского научного центра РАН. 2002. - Т. 8, № 1. - С. 1-5.

73. Коркмазова, З. О. Эйлеровы предфрактальные графы / З. О. Коркмазова, А. А. Кочкаров // Известия ТРТУ. Специальный выпуск. Таганрог, 2004. - № 8. - С. 304-305.

74. Коркмазова, З. О. Многокритериальная задача разбиения на эйлеровые подграфы предфрактального графа / З. О. Коркмазова. Черкесск, Карачаево-Черкесская Гос. Технолог. Ак., 2004. - Библиогр.: - С. 1-25. - Деп. в ВИНИТИ № 1729-В2004.

75. Коркмазова, З. О. Параллельный алгоритм вычисления задачи Эйлера на предфрактальных графах / З. О. Коркмазова. Черкесск, Карачаево-Черкесская Гос. Технолог. Ак., 2004. - Библиогр.: - С. 1-20. - Деп. в ВИИИТИ № 1730-В2004.

76. Коркмазова, З. О. Выделение максимальных эйлеровых подграфов на предфрактальном графе / З. О. Коркмазова. Черкесск, Карачаево-Черкесская Гос. Технолог. Ак., 2004. - Библиогр.: - С. 1-25. - Деп. в ВИНИТИ № 1731-В2004.

77. Коркмазова, З. О. Многокритериальная задача покрытия предфрактального графа эйлеровыми подграфами / З. О. Коркмазова, Р. А. Кочкаров. (Препринт спец. астрофиз. обсерватории РАН № 208). - Нижний Архыз, 2005. - С. 1-15.

78. Коркмазова, З. О. Алгоритмы с оценками построения покрытия эйлеровыми циклами на предфрактальном графе / З. О. Коркмазова, Р. А. Кочкаров. -(Препринт спец. астрофиз. обсерватории РАН № 209). Нижний Архыз, 2005. -С. 1-27.

79. Коркмазова, З. О. Алгоритм порождения ориентированного эйлерова предфрактального графа / З. О. Коркмазова, А. А. Кочкаров // Вестник СевероКавказского государственного технического университета. Ставрополь: СевКавГТУ, 2006. - №3(7) - С. 55-61.

80. Коркмазова, З. О. Многокритериальная задача Эйлера на предфрактальных графах / З. О. Коркмазова, С. И. Салпагаров // V Всероссийский Симпозиум «Математическое моделирование и компьютерные технологии». Тез. докл. -Кисловодск: КИЭП, 2002. С. 7.

81. Бондаренко, В. А. Фрактальное сжатие изображений по Барнсли-Слоану /

82. B. А. Бондаренко, В. Л. Дольников // Автоматика и телемеханика. 1994. - № 5.1. C. 12-20.

83. Балханов, В. К. Введение в теорию фрактального исчисления / В. К. Балханов. -Улан-Удэ: БГУ, 2001. 58 с.

84. Божокин, С. В. Фракталы и мультифракталы / С. В. Божокин, Д. А. Паршин. -М.: Ижевск: РХД, 2001. -128 с.

85. Бородич, Ф. М. Энергия разрушения фрактальной трещины, распространяющейся в бетоне или горной породе / Ф. М. Бородич // Доклады РАН. -1992. Т. 325, № 3.

86. Бородич, Ф. М. Фрактальная шероховатость в задачах контакта и трения (простейшие модели) / Ф. М. Бородич, Д. А. Онищенко // Трение и износ.- 1993. -Т. 14, № 3. С. 452-459.

87. Витолин, Д. Применение фракталов в машинной графике / Д. Витолин // Сотри:етогЫ-Россия 1995. -№ 15. - С. 11.

88. Вишик, М.И. Фрактальная размерность множеств / М.И. Вишик // Соросовский образовательный журнал.- 1998. № 1. - С. 122-127.

89. Галиулин, Р. От мавританских орнаментов к фракталам / Р. Галиулин // Наука и жизнь. -1995. № 8. - С. 59-64.

90. Данилов, Ю. А. Красота фракталов / Ю. А. Данилов // Труды Московского Международного Синергетического Форума. 1997.

91. Дмитриев, А. Хаос, фракталы и информация / Дмитриев А. // Наука и жизнь. -2001. № 5. - С. 44-52.

92. Долбилин, Н. Игра «Хаос» и фракталы / Н. Долбилин // Квант. 1997. - № 2. -С. 22-31.

93. Долбилин, Н. Самоподобные мозаики / Н. Долбилин // Квант. 1998. - № 2. -С. 11-15.

94. Жиков, В. В. Фракталы / В. В. Жиков // Соросовский образовательный журнал. -1998. -№ 1.

95. Забарянский, С. Ф. Фрактальное сжатие изображений / С. Ф. Забарянский // Компьютеры + программы. 1993. - № 6. - С.39.

96. Зельдович, Я. Б. Фракталы, подобие, промежуточная асимптотика / Я. Б. Зельдович, Д. Д Соколов // УФН. 1985. - Т. 14, Вып. 3.

97. Иванов, С. С. Оценка фрактальной размерности самоаффинных множеств: метод встречного масштабирования дисперсий / С. С. Иванов // ДАН. 1993. -Т. 332, № 1. - С. 82-92.

98. Синергетика и фракталы в материаловедении / B.C. Иванова и др.. М.: Наука,1994. 383 с.

99. Иванова, В.С. Синергетика. Прочность и разрушение металлических материалов / B.C. Иванова. М.: Наука, 1992. - 157 с.

100. Иванюк, Г.Ю. Фрактальные геологические среды: размерность, основные типы, генетические следствия / Г.Ю. Иванюк // Физика Земли. 1997. - № 3. - С. 21-31.

101. Козинцев, С. Ландшафты фрактальных миров / С. Козинцев // Наука и жизнь.1995. № 12.

102. Кроновер, Р. Фракталы и хаос в динамических системах / Р. Кроновер. М.: Постмаркет, 2000. - 353 с.

103. Кулак, М.И. Структурные аспекты фрактальной механики древесно-полимерных композитов / М.И. Кулак // Известия АН БССР. Серия физико-технических наук. 1991. - № 2. - С. 18-22.

104. Лухнева, О. Ф. Фрактальная геометрия сетки активных разломов и рельефа Прибайкалья: применение метода встречного масштабирования дисперсий /

105. О. Ф. Лухнева, Ф. Л. Зуев // Геофизика на пороге третьего тысячелетия. Труды первой Байкальской молодежной школы-семинара. / под ред. Г.С. Вахромеева. -Иркутск: Изд-во ИрГТУ, 1999.

106. Мандельброт, Б. Самоаффинные фрактальные множества / Б. Мандельброт. -М.: Мир, 1988. 672 с.

107. Мандельброт, Б. Фрактальная геометрия природы / Б. Мандельброт. М.: Ижевск: РХД, 2002. - 656 с.

108. Математическое моделирование в синергетических системах // Материалы международной конференции. Томск, Улан-Удэ, 1999.

109. Меньшиков, М. В. Теория перколяции и некоторые приложения / М. В. Меньшиков, С. А. Молчанов, А.Ф. Сидоренко // Итоги науки и техники. Сер. Теория вероятностей. Математическая статистика. Теоретическая кибернетика. М.: ВИНИТИ, 1986. - Т. 24. - 188 с.

110. Милнор, Дж. Голоморфная динамика / Дж. Милнор. М.: Ижевск: РХД, 2000. -320 с.

111. Мичи, Д. Компьютер творец / Д. Мичи, Р. Джонсон. - М.: Мир, 1987. - 255 с.

112. Морозов, А. Д. Введение в теорию фракталов / А. Д. Морозов. Нижний Новгород: Изд-во НижГУ, 1999. - 160 с.

113. Найденов, В. И. Эффект Херста в геофизике / В. И. Найденов, И. А. Кожевникова // Природа. 2000. - № 1.

114. Наймарк, О. Б. Топологический фрактальный анализ кинетики накопления дефектов при оценке прочности углеродных композитов / О. Б. Наймарк, М. М. Давыдова // Механика композитных материалов. 1994. - Т. 30, № 1. -С. 19-30.

115. Нигматуллин, Р. Р. Фракталы: от узоров к движению / Р. Р. Нигматуллин, М. Н. Овчинников, Я. Е. Рябов // Природа. 1998. - № 2. - С. 61-72.

116. Пайтген, Х.-О. Красота фракталов / Х.-О. Пайтген, П. Х. Рихтер. М.: Мир, 1993. - 176 с.

117. Потапов, А. Фракталы в дистанционном зондировании / А. Потапов // Зарубежная радиоэлектроника. Успехи современной радиоэлектроники. 2ССС. -№ 6. - С. 3-65.

118. Пригожин, И. Р. Конец определенности. Время, Хаос и Новые Законы Природы / И. Р. Пригожин. М.: Ижевск: РХД, 2СС1. - 216 с.

119. Роджерс, Д. Алгоритмические основы машинной графики / Д. Роджерс. М.: Мир, 1989. - 512 с.

120. Самко, С. Г. Интегралы и производные дробного порядка и некоторые их приложения / С. Г. Самко, А. А. Килбас, О. И. Маричев. Минск: Наука и техника, 1987. - 688 с.

121. Смирнов, Б. М. Физика фрактальных кластеров / Б. М. Смирнов. М.: Наука, 1991. - 136 с.

122. Странные аттракторы / под редакцией Я. Г. Синая и Л. И. Шильникова. М.: Мир, 1981. - 253 с.

123. Транковский, С. Красота хаоса / С. Транковский // Наука и жизнь. 1994. - № 4. - С. 15.

124. Федер, Е. Фракталы / Е. Федер. М.: Мир, 1991. - 261 с.

125. Фоменко, А. Т. Наглядная геометрия и топология / А. Т. Фоменко. М.: МГУ-ЧеРо, 1998. - 416 с.

126. Фракталы в физике // Труды 6 Международного симпозиума. М.: Мир, 1988. -67С с.

127. Фракталы // Компьютерная газета. 1999. - № 36. - С. 226.

128. Шалагинов, А. А. Об отображениях самоподобных кривых / А. А. Шалагинов // Сибирский математический журнал. 1993. - Т. 34, № 6. - С. 210-215.

129. Шредер, М. Фракталы, хаос, степенные законы / М. Шредер. М.: Ижевск: РХД, 2001. - 528 с.

130. Эфрос, А. Л. Физика и геометрия беспорядка / А. Л. Эфрос. М.: Наука, 1982. -176 с.

131. Нестационарные структуры и диффузионный хаос / Т. С. Ахромеева и др.. -М.: Наука, 1992. 544 с.

132. Турбин, А. Ф. Фрактальные множества. Функции, распределения / А.Ф. Турбин, Н. В. Працевитый. Киев: Наукова думка, 1992. - 208 с.

133. Schulman, L.S. Complex systems under stochastic dynamics / L.S. Schulman, B. Gaveau // Att. Fond. G. Ronchi, 2003. V. LVIII, № 805.

134. Li., Alderson D., Tanaka R., Doyle J.C, Willinger W. Towards a Theory of Scale-Free Graphs: Definition, Properties, and Implications (Extended Version) // Technical Report CIT-CDS-04-006, Cal Tech, 2005.

135. Bollt, E. M. What is Special about Diffusion on Scale-Free Nets? / E. M. Bollt, D. Ben-Avraham // New J. Phys. 2005. - V. 7, № 26. - P. 1-21.

136. Malozemov, L. Pure point spectrum of the Laplacians on fractal graphs / L. Malozemov, A. Teplyaev // Journal of Functional Analysis. 1995. - Vol. 129, №2. - P. 390-405.

137. Woess, W. Random walks on infinite graphs and groups / W. Woess // Volume 138 of Cambridge Tracts in Mathematics. Cambridge University Press, Cambridge, 2000.

138. Barlow, M. T. Diffusions on fractals / M. T. Barlow // Lectures on probability theory and statistics. Springer Verlag, Berlin, 1998. - P. 1-121.

139. Kigami, J. Analysis on fractals / J. Kigami //Volume 143 of Cambridge Tracts in Mathematics. Cambridge University Press, Cambridge, 2001.

140. Song, С. Self-similarity of Complex Networks / C. Song, S. Havlin, H. A. Makse // Nature 433. 2005. - P.392-395.

141. Вапник, В. Н. Теория распознавания образов / В. Н. Вапник, А. Я. Червоненкис. М.: Наука, 1974. - 416 с.

142. Ту, Дж. Принципы распознавания образов / Дж. Ту, Р. Гонсалес; пер. с англ. -М.: Мир, 1978. 412 с.

143. Горелик, А.Л. Методы распознавания / А. Л. Горелик, В.А. Скрипкин.- М.: ВШ, 1989. 264 с.

144. Оссовский, С. Нейронные сети для обработки информации / С. Оссовский. М.: Финансы и статистика, 2002. - 344 с.

145. Дьяконов, В. П. MATLAB 6.5 SP1/7 SP2+Simulink 5/6. Инструменты искусственного интеллекта и биоинформатики / В. П. Дьяконов. М.: Солон, 2006. - 456 с.

146. Нейронные сети. STATISTICA Neural Networks; пер. с англ. М.: Горячая Линия - Телеком, 2000. - 182 с.

147. Хайкин, С. Нейронные сети. Полный курс / С. Хайкин; пер. с англ. 2-е изд. -М.: Издательский дом «Вильямс», 2006. - 1104 с.

148. Кузин, Л. Т. Основы кибернетики: учеб. пособие / Л. Т. Кузин. М.: Энергия, 1979. - Т. 2. - 584 с.

149. Фор, А. Восприятие и распознавание образов / А. Фор; пер. с фр. А. В. Серединского; под ред. Г. П. Катыса. М.: Машиностроение, 1989. - 272 с.

150. Браверман, Э. М. Структурные методы обработки эмпирических данных / Э.М. Браверман, И. Б. Мучник. М.: Наука, 1983. - 464 с.

151. Васильев, В. И. Проблемы обучения распознаванию образов. Принципы, алгоритмы реализация / В. И. Васильев. Киев: ВШ, 1989. - 64 с.

152. Распознавание образов. Состояние и перспективы / К. Верхаген и др.; пер. с англ. М.: Радио и связь, 1985. - 104 с.

153. Вишняков, Ю. М. Учебно-методическое пособие для самостоятельной работы по курсам «Системы искусственного интеллекта», «Методы распознаванияобразов» / Ю. М. Вишняков, В. И. Кодачигов, С. И. Родзин. Таганрог: Изд-во ТРТУ, 1999. - 132 с.

154. Горелик, А. Л. Современное состояние проблемы распознавания / А. Л. Горелик, И. Б. Гуревич, В. А. Скрипкин. М.: Радио и связь, 1985. - 160 с.

155. Мелихов, А. Н. Методы распознавания изоморфизма и изоморфного вложения четких и нечетких графов / А. Н. Мелихов, В. П. Карелин. Изд. ТРТУ, Таганрог, 1995. - 112 с.

156. Орлов, В. А. Граф-схемы алгоритмов распознавания / В. А. Орлов. М.: Наука, 1982. - 120 с.

157. Распознавание, классификация, прогноз. Математические методы и их применение: Ежегодник; под. ред. Журавлева Ю. И. М.: Наука, 1989. - Вып. 2. -С. 5-72.

158. Растригин, Л. А. Метод коллективного распознавания / Л. А. Растригин, Р. Х. Эренштеин. М.: Энергоиздат, 1981. - 79 с.

159. Реброва, М. П. Автоматическая классификация в системах обработки информации. Поиск документов / М. П. Реброва. М.: Радио и связь, 1983. - 97 с.

160. Хант, Э. Искусственный интеллект, ч. 2. распознавание образов / Э. Хант. М.: Мир, 1978. - С. 63-244.

161. Кук, С. А. Сложность процедур вывода теорем / С. А. Кук // Кибернетический сборник, новая серия. 1975. - Вып.12. - С. 5-15.

162. Карп, Р. М. Сводимость комбинаторных проблем / Р. М. Карп // Кибернетический сборник, новая серия. 1975. - Вып.12. - С. 16-38.

163. Левин, Л. А. Универсальные задачи перебора / Л. А. Левин // Проблемы передачи информации. 1973. - Т. 9, № 3. - С. 115-116.

164. Гэри, М. Вычислительные машины и труднорешаемые задачи / М. Гэри, Д. Джонсон. М.:Мир. - 1982. - 416 с.

165. Утакаева, И. Х. Об одной модели распознавания предфрактального графа / И. Х. Утакаева // Международная конференция «Дифференциальные уравнения, теория функций и приложения». 2007. - С. 634-635.

166. Кочкаров, А. М. Структурное распознавание предфрактальных деревьев с множеством затравок /А. М. Кочкаров, Л. Х. Хапаева // Научный журнал КубГАУ. 2011. - №69(05). - С. 448-459.

167. Пролубников, А. В. Прямой алгоритм проверки изоморфизма графов : дис. . канд. физ.-мат. наук : 05.13.17 / Пролубников Александр Вячеславович. Омск, 2004. - 99 с.

168. Резников, А. В. Распознавание предфрактальных графов с затравкой, удовлетворяющей условию Оре текст. / А. В. Резников // Вестник Адыгейского государственного университета. Майкоп, 2010. - Выпуск 2. - С. 34-39.

169. Резников А. В. Программный комплекс для распознавания предфрактальных графов с регулярными затравками («Recognize 1.0») / А. В. Резников, А. А. Кочкаров // Свидетельство о государственной регистрации программы для ЭВМ, № 2010613649, 03.06.2010.

170. Резников А. В. Программный комплекс для распознавания предфрактальных графов с затравками, о структуре которых информация отсутствует

171. Recognize 2.0») / А. В. Резников, А. А. Кочкаров // Свидетельство о государственной регистрации программы для ЭВМ, № 2011611836, 28.02.2011.

172. Резников А. В. Распознание предфрактальных графов текст. / А. В. Резников // Математические методы и информационно-технические средства: труды VI Всерос. Науч.-практ. конф. Краснодар, 2010. - С. 145-147.