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

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

1. Задача раскраски графов.

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

1.3 Многокритериальная задача раскраски предфрактального графа

1 1
1.4 Выводы
Глава 2. Особенности раскраски фрактальных и предфраюальных графов свойства и характеристики .

2.1 Бихроматические предфрактальные графы.

2.2. Хроматическое число предфрактального графа,

порожденного с сохранением смежности старых ребер.

2.3. Об однозначной раскраске предфрактальных графов

2.4. О критических подграфах предфрактального графа.

2.5. О раскраске фрактальных графов.
2.6. Раскраска плоских и планарных фрактальных
предфрактальных графов
2.6. Выводы.
Глава 3. Алгоритмы вершинной раскраски предфрактальных графов
3.1. Алгоритмы раскраски простых графов.
3.2 Алгоритм раскраски предфрактального графа, смежность старых ребер которого сохраняется, а затравка полный граф.
3.3 Алгоритм 2 раскраски предфрактального графа, смежность старых ребер которого сохраняется
3.4 Алгоритм 3 раскраски предфрактального графа, порожденного
множеством затравок, смежность старых ребер которого сохраняется
3.5 Алгоритм раскраски предфрактального графа, старые ребра
которого не пересекаются, а затравка полный граф.
3.6 Алгоритм у раскраски предфрактального графа, старые ребра которого не пересекаются
3.7 Алгоритм у з раскраски предфрактального графа, порожденного множеством заравок, старые ребра которого не пересекаются
3.8 Сетевая модель оптимального монтажнокоммутационного пространства и раскраска е вершин
3.9 Выводы
Заключение
Лигериура .
Введение


Системы с простой структурой, к примеру иерархической, могут демонстрировать очень сложное нетривиальное поведение 3. Каждый элемент го уровня состоит из трех элементов Ыого уровня. Элементы системы могут быть исправны или дефектны показаны заливкой. Состояние каждого элемента определяется состоянием образующих его элементов предыдущего уровня, а также его собственной восприимчивостью к дефектам. Многие системы обладают простой иерархической структурой, фрагмент которой изображен на рис. Например, литосферу Земли можно представить как систему блоков, разделенных разломами. Каждый из этих блоков делится на более мелкие, те, в свою очередь, на еще более мелкие и т. Геофизики выделяют более иерархических уровней в земной коре от тектонических плит протяженностью в тысячи километров до зерен горных пород миллиметрового размера. Большие землетрясения обычно сопровождаются многочисленными повторными толчками афтершоками, которые каскадом перераспределяют напряжение вниз по иерархии разломов. А подготовка землетрясения происходит посредством обратного каскада передачи напряжения, восходящего с нижних уровней иерархии к верхним. Напрашивающимся примером иерархической системы, связанной с деятельностью человека, служит система административного или военного руководства. Успех в решении задач на некотором уровне управления определяется эффективностью функционирования нижележащих уровней. Иерархической системой является и электорат. Он также делится на несколько групп со своими интересами. Каждая из них складывается из более мелких подгрупп и т. Мы можем наблюдать поведение иерархических систем только на верхних уровнях иерархии землетрясения, исполнение распоряжений, результаты голосования. Однако причины событий лежат на нижних уровнях, и важно представлять, как происходит взаимодействие уровней. Но, как говорилось ранее, сложное поведение системы может наблюдаться и при простых процессах, протекающих в ней. В такой ситуации сложность в системе обосновывается сложностью структуры системы. Именно такой сложности и посвящена настоящая диссертационная работа. Термин фрактал лат. Бенуа Мандельбротом в году. И хотя в математике похожие конструкции в той или иной форме появились уже много десятков лет назад, ценность подобных идей в науке была осознана лишь в е годы прошлого столетия. Важную роль в широком распространении идей фрактальной геометрии сыграла книга Б. Мандельброта Фрактальная геометрия природы 4. Фрактальные объекты, согласно своему начальному определению, обладают размерностью, строго превышающей топологическую размерность элементов, из которых они построены, причем эта размерность является дробной под размерностью понимается размерность ХаусдорфаБезиковича, введенная в году Ф. Хаусдорфом и развитая впоследствии Безиковичем 6, , 4, 7, 7, 9, 1, 8. Основой новой геометрии является идея самоподобия 6, , 4, 7, 7, 9, 1, 8. Она выражает тот факт, что иерархический принцип организации фрактальных структур не претерпевает значительных изменений при рассмотрении их с различным увеличением. В результате эти структуры на малых масштабах выглядят в среднем так же, как и на больших. Здесь следует провести разницу между геометрией Евклида, имеющей дело исключительно с гладкими кривыми, и бесконечно изрезанными самоподобными фрактальными кривыми. Элементы кривых у Евклида всегда самоподобны, но тривиальным образом все кривые являются локально прямыми, а прямая всегда самоподобна. Фрактальная же кривая в идеале, на любых, даже самых малень
ких масштабах, не сводится к прямой и является в общем случае геометрически нерегулярной, хаотичной 6, , 4, 7, 7, 9, 1, 8. Рисунок 3 Множество Мандельброта
Фракталами являются, например, странные аттракторы рис. Вообще говоря, существует классификация фрактальных объектов 4. Среди них можно выделить множество Мандельброта, изображенное на рис. Работы, связанные с исследование фрактальных объектов фрактальных множеств, долгое время считались занимательными, но не имеющими значительных приложений. Мнения в мировой научной среде изменились с изданием книги 8.