Исследование свойств и распознавание предфрактальных графов

• Автор: Резников, Андрей Владимирович
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2013
• Место защиты: Черкесск
• Количество страниц: 168 с. : ил.

ОГЛАВЛЕНИЕ
ВВЕДЕНИЕ
ГЛАВА 1. ОПРЕДЕЛЕНИЕ, ПОНЯТИЯ, СВОЙСТВА ПРЕДФРАКТАЛЬНЫХ ГРАФОВ И ИХ ЗАТРАВОК
1.1. Основные определения и понятия
1.2. Свойства предфрактальных графов, порожденных регулярными
затравками
1.3. Свойства затравок предфрактальных графов
1.4. Свойства предфрактальных графов при несмежности старых ребер
1.5. Свойства предфрактальных графов при сохранении смежности
старых ребер
ГЛАВА 2. МЕТРИЧЕСКИЕ СВОЙСТВА ПРЕДФРАКТАЛЬНЫХ ГРАФОВ
2.1. Основные метрические характеристики графов
2.2. Оценки диаметра предфрактальных графов, порожденных затравками, удовлетворяющими условию Оре
2.3. Оценки радиуса предфрактальных графов, порожденных затравками, удовлетворяющими условию Оре
ГЛАВА 3. АЛГОРИТМЫ РАСПОЗНАВАНИЯ ПРЕДФРАКТАЛЬНЫХ ГРАФОВ
3.1. AiropiiTM распознавания предфрактальных графов с регулярной п-вершинной затравкой степени не менее п/
3.2. Алгоритмы распознавания предфрактальных графов, в траектории
которых старые ребра не смежны
3.3. Алгоритмы распознавания предфрактальных графов, в траектории
которых смежность старых ребер сохраняется
3.4. Алгоритм распознавания предфрактальных графов с п -вершинной затравкой,
2п—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] или фрактальные графы [50-92].
Фрактальный граф — это сложная абстрактная структура, обладающая свойствами фракталов и «простых» графов. В разных научных школах применяются различные правила построения структурной динамики, что в результате приводит к различным, по строению, самоподобным графам. По данной тематике написано множество статей в российских и зарубежных научных журналах. В статье F.G. Arenas, М.А. Sanchez-Granero (2000) [39] исследуются графы, построенные на множестве точек отрезка [0,1]. В работах E.Teufl, S. Wagner (2000) [38]; В. Krön

ГЛАВА 2. МЕТРИЧЕСКИЕ СВОЙСТВА ПРЕДФРАКТАЛЬНЫХ ГРАФОВ
2.1. Основные метрические характеристики графов
Пусть Я = (И'Д) — »-вершинный связный граф, у, и v1 — две его вершины (у„у2 еШ).
Расстоянием [28] с1(и,х) между двумя вершинами и и у графа Н называется длина кратчайшей простой цепи, соединяющей их.
Эксцентриситетом [28] е(у) вершины у (у е IV) определяется как тахпо всем вершинам и в Я.
Радиусом [28] г{н) называется наименьший из всех эксцентриситетов вершин.
Геодезической [28] вершин и и у называется кратчайшая простая, соединяющая их, цепь.
Диаметр [28] Дн) графа — это длина его самой длинной геодезической.
Диаметральной целью [12] называется цепь, соединяющая такие вершины и и у, что £/(м,у) = й'(я).
Периферийной [12] вершиной называется такая вершина у графа Н, для которой е(у)=(]{н).
Центральной вершиной [28] называется такая вершина у графа Я, для которой
е(у) = г(я).
Центр графа [28] — это множество всех его центральных вершин.