Многокритериальная задача Эйлера на предфрактальных графах

• Автор: Коркмазова, Зарема Османовна
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2006
• Место защиты: Ставрополь
• Количество страниц: 121 с. : ил.

ОГЛАВЛЕНИЕ
Г ВВЕДЕНИЕ.

ГЛАВА 1. МНОГОКРИТЕРИАЛЬНАЯ ЗАДАЧА ПОКРЫТИЯ

ПРЕДФРАКТАЛЬНОГО ГРАФА ЭЙЛЕРОВЫМИ ПОДГРАФАМИ

1.1. Эйлеровы графы и задача китайского почтальона

1.2. Фрактальные и предфрактальные графы

1.3. Многокритериальная задача покрытия предфрактального графа эйлеровыми подграфами.
1.4. Вывод

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

2.1. Алгоритм ах построения покрытия ранговыми циклами

2.2. Алгоритм а2 выделения эйлерова цикла на предфракталыюм графе, смежность старых ребер которого сохраняется.
2.3. Алгоритм аъ выделения смешанных циклов.
2.4. Алгоритм аА выделения эйлерова подграфа
2.4.1. Алгоритм аг выделения эйлерова подграфа на полном графе.
2.4.2. Алгоритм аР выделения эйлерова подграфа на полном графе.
2.5. Алгоритм а5 выделения эйлерова цикла на предфрактальном графе, смежность старых ребер одного ранга которого сохраняется.
2.6. Алгоритм а6 выделения эйлерова подграфа на предфрактальном графе,
I смежность старых ребер которого сохраняется
2.7. Выводы.
ГЛАВА 3. АЛГОРИТМЫ ПОРОЖДЕНИЯ ЭЙЛЕРОВЫХ ПРЕДФРАКТАЛЬНЫХ ГРАФОВ. НЕКОТОРЫЕ ХАРАКТЕРИСТИКИ НЕЭЙЛЕРОВЫХ ПРЕДФРАКТАЛЬНЫХ ГРАФОВ
3.1. Алгоритм Д порождения эйлерова пред фрактального графа.
3.2. Алгоритм Д2 порождения ориентированного эйлерова нредфрактального графа
3.3. Выводы
ЗАКЛЮЧЕНИЕ.
ЛИТЕРАТУРА


Определенное специальным образом допустимое решение хеХ является отличительной особенностью многокритериальных задач на графах. В качестве критериев /*}(х), / = 1,и, в таких задачах используются степень подграфа [-] х, его диаметр [-], количество компонент связности [ - ] и общий (суммарный) вес, если граф С взвешен [ - ]. Современные исследования сложных систем, таких, как информационные, электроэнергетические, VWV (Ітетеї), коммуникационные системы показывают, что структуры этих систем по истечении времени претерпевают определенные изменения, вызываемые различными внешними обстоятельствами [0- 4]. Структуру системы произвольной природы (социальной, социально-экономической, технической, химико-биологической и т. Изменения, происходящие в структуре сложной системы, могут быть описаны простейшими теоретико-графовыми операциями: стягивание ребра, удаление (добавление) ребра, удаление (добавление) вершины. Изменения структуры системы могут быть разовыми, а могут быть постоянными. Для второго случая разумно ввести понятие структурной динамики - изменение структуры системы с течением времени. Несомненно, для описания структурной динамики лучше всего подходит аппарат теории графов. Одним из наиболее распространенных сценариев структурной динамики является рост структуры. Рост структуры - это регулярное появление новых элементов и связей в структуре системы. Рост структуры может происходит по строго сформулированным правилам, не исключая наличие в них фактора случайности [0 - 4]. В настоящей работе рассматривается одно из возможных правил, задающих структурную динамику сложных систем. Формальными представлениями изменения структуры систем по этому правилу являются масштабноинвариантные или самоподобные графы (self-similar graphs) большой размерности, называемые фрактальными (предфрактальными). Фрактальный граф - сложный абстрактный объект, совмещающий в себе свойства, характеристики и достоинства фракталов и “обычных” графов. Понятие фрактал, введенное Бенуа Мандельбротом [5], объединило объекты, обладающие особым свойством - свойством самоподобия (selfsimilarity) или масштабной инвариантности. Работы, связанные с исследованием фрактальных объектов (фрактальных множеств), долгое время считались занимательными, но неимеющими значительных приложений. Мнения в мировой научной среде изменились с изданием книги [6]. Chaos, Solitons & Fractals”), целиком посвященных соответствующей тематике и множеству книг (учебников и монографий) [5-1]. Это позволяет говорить о сформировавшемся круге прикладных физических модельных задач на основе фрактальных множеств [2- 4]. Среди них выделяются задачи и модели, где фрактальные множества представлены как самоподобные (фрактальные или масштабноинвариантные) графы большой размерности, т. К ним относятся, например, задачи о броуновском движении (случайном блуждании), диффузии и просачиваемости. Кроме того, самоподобные графы нередко выступают в качестве моделей структур сложных многоэлементных систем [3], таких как коммуникационные сети. Активное изучение фрактальных графов и областей их приложения ведется в научной школе профессора А. М. Кочкарова. Исследования ведутся по трем направлениям: распознавание фрактальных графов [8, 5], их свойства и характеристики [6- 0], задачи многокритериальной оптимизации в системах с масштабно-инвариантной структурой [1 - 6]. Надо отметить, что масштабная инвариантность структур моделируемых систем является следствием структурной динамики в этих системах. В настоящей диссертационной работе проведено исследование, которое лежит на стыке нескольких направлений современной математической науки - моделирования систем с переменной структурой (структурная динамика), многокритериальной комбинаторной оптимизацией и синергетикой. Публикации. По результатам выполненной работы имеется публикация, в том числе 2 статьи в журналах из списка ВАК РФ, 3 статьи, депонированные в ВИНИТИ, 2 препринта, тезисы докладов в материалах 4 международных конференций, тезисы докладов в материалах 2 Всероссийских симпозиумов и т.