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

• Автор: Узденов, Ахмат Абдуллахович
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2011
• Место защиты: Черкесск
• Количество страниц: 157 с. : ил.

СОДЕРЖАНИЕ
ВВЕДЕНИЕ
1 МОДЕЛИ РАЗМЕЩЕНИЯ ЦЕНТРОВ НА ГРАФАХ
1.1 Задачи размещения центров и медиан на графах
1.2 Классическая постановка задачи размещения центров
в графах и сетях
1.3 Задача размещения р-центра и алгоритм её решения
1.4 Выводы
2 МНОГОКРИТЕРИАЛЬНАЯ МОДЕЛЬ РАЗМЕЩЕНИЯ ЦЕНТРОВ НА ПРЕДФРАКТАЛЬНЫХ ГРАФАХ
2.1 Фрактальные и предфрактальные графы. Определение
фрактального и предфрактального графов
2.2 Многокритериальная модель размещения р-центра
на предфрактальных графах
2.3 Математическая модель крупномасштабной кластеризации
материи во Вселенной
2.4 Метрические характеристики предфрактальных графов,
порождённых затравкой-звездой
2.5 Выводы
3 АЛГОРИТМЫ ПОИСКА ЦЕНТРОВ ПРЕДФРАКТАЛЬНЫХ ГРАФОВ И ИХ ПРОГРАММНАЯ РЕАЛИЗАЦИЯ
3.1 Алгоритм о.1 поиска внешнего центра предфрактального
графа
3.2 Алгоритм а2 поиска внутреннего центра предфрактального
графа, смежность «старых» рёбер которого сохраняется
3.3 Алгоритм «з поиска внешне-внутреннего центра предфрактального графа, смежность «старых» рёбер
которого сохраняется
3.4 Алгоритм а4 поиска центра предфрактального графа,

смежность «старых» рёбер которого сохраняется
3.5 Алгоритм р, поиска /;-центра (р = п1') предфрактального
графа, смежность «старых» рёбер которого сохраняется
3.6 Алгоритм р2 поиска р-центра (р = п ~2) предфрактального
графа, смежность «старых» рёбер которого сохраняется
3.7 Алгоритм р поискар-центра предфрактального графа,
смежность «старых» рёбер которого сохраняется
3.8 Описание программного комплекса и результаты расчётов
3.9 Выводы
ОСНОВНЫЕ РЕЗУЛЬТАТЫ, ПОЛУЧЕННЫЕ В
ДИССЕРТАЦИОННОМ ИССЛЕДОВАНИИ
БИБЛИОГРАФИЧЕСКИЙ СПИСОК ИСПОЛЬЗОВАННЫХ
МАТЕРИАЛОВ
ПРИЛОЖЕНИЕ. ПРОГРАММНЫЙ КОМПЛЕКС «НАХОЖДЕНИЕ ЦЕНТРАЛЬНЫХ ВЕРШИН ФРАКТАЛЬНОГО ГРАФА».
ТЕКСТ ПРОГРАММ С КОММЕНТАРИЯМИ

ВВЕДЕНИЕ
В современном мире всё чаще приходится проектировать, строить, обслуживать системы, состоящие из большого количества элементов, соединённых многими связями друг с другом, так называемые «сложные системы». При этом связи (бинарные отношения) между элементами с навешиваемыми на них скалярными характеристиками могут изменяться во времени. Порождение и исследование процессов изменения связей между элементами системы или способов изменения инцидентора графа (сети) и других структурных преобразований в системе относят к новой математической дисциплине, называемой «структурной динамикой». К таким практическим системам в первую очередь следует отнести современные коммуникационные и информационные сети, объём и масштаб которых в процессе роста, развития и эксплуатации может претерпевать значительные топологические, пространственные и количественные метрические изменения, при этом системы остаются структурно инвариантными.
В таких сетях хорошо известная в дискретной математике задача о назначениях, в частности, о размещении центров, приобретает новый смысл. Для решения современных задач структурной динамики становится где-то сложно, а где-то невозможно использовать классическую теорию графов, поскольку необходимо приходится моделировать динамические структуры с большим количеством элементов и ещё большим количеством отношений (связей) между ними. Связи между элементами перестают быть тривиальными бинарными отношениями, они часто приобретают фрактальную природу. Для успешного математического моделирования подобных новых систем приходится пользоваться и достаточно новыми математическими объектами - «фрактальными и предфрактальными графами».
В практической деятельности постоянно возникают задачи «наилучшего» размещения оборудования или средств обслуживания в сетях или на графах. В частности, если граф представляет сеть дорог, а вершины графа соот-

травкой Н = (IV,О), и (п,Ь)-графом, если затравка Н = (IV, О) представляет из себя регулярный граф.
Использование операции ЗВЗ в процессе порождения предфрактально-го графа Сь для элементов б/ = (У/,Е[), I е {1,2
<РУ1) = УШ, 1 = 1,2
В (2.1) множество У!+/ - образ множества V), а множество У1 - прообраз множества У!+1.
Для предфрактального графа б1 рёбра, появившиеся на / -ом ( I е{1,2
Блоки предфрактального графа. Если из предфрактального графа Сь, порождённого «-вершинной затравкой Н, последовательно удалить все «старые» рёбра (рёбра ранга /, / = 1,2
на множество связных компонент {В}, каждая из которых изоморфна [48]
затравке Я. Множество компонент [В(})} будем называть блоками первого ранга. Аналогично, при удалении из предфрактального графа Оь всех «старых» рёбер рангов / = 1,2