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

• Автор: Павлов, Дмитрий Алексеевич
• Шифр специальности: 05.13.17
• Научная степень: Кандидатская
• Год защиты: 2004
• Место защиты: Черкесск
• Количество страниц: 112 с.

СОДЕРЖАНИЕ
ВВЕДЕНИЕ

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

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

1.2. Многокритериальная постановка задачи о покрытии предфрактального графа простыми непересекающимися цепями покрытие вида К,.

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

графа простыми непересекающимися цепями покрытие вида К2.

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

2.1. Разработка и исследование полиномиальных алгоритмов построения покрытия К,

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

2.1.2. Алгоритмы а2 построения покрытия .ранговыми цепями длины два
2.1.3. Алгоритмы а3 построения покрытия Лранговыми цепями длины три.
2 2. Разработка и исследование полиномиальных алгоритмов построения
покрытия К2
2.2.1. Алгоритм , построения остовного дерева минимального веса
2.2.2. Алгоритм 2 выделения наибольших максимальных цепей
Выводы.
ГЛАВА 3. РАСПОЗНАВАНИЕ ПРЕДФРАКТАЛЬНОГО ДЕРЕВА С ЗАТРАВКОЙ ПРОСТАЯ ЦЕПЬ.
3.1. Алгоритм распознавания прсдфрактального графа с затравкой цепь длины один ребро.
3.2. Алгоритм распознавания предфрактального графа с затравкой простая
цепь длины ребер
Выводы.
ЗАКЛЮЧЕНИЕ.
ЛИТЕРАТУРА


Фрактальные объекты, согласно своему начальному определению, обладают размерностью, строго превышающей топологическую размерность элементов, из которых они построены, причем эта размерность является дробной (под размерностью понимается размерность Хаус-дорфа - Безиковича, введенная в году Ф Хаусдорфом и развитая впоследствии АС. Безиковичем) [,-]. Основой новой геометрии является идея самоподобия [,,]. Она выражает тот факт, что иерархический принцип организации фрактальных структур не претерпевает значительных изменений при рассмотрении их с различным увеличением. В результате эти структуры на малых масштабах выглядят в среднем так же, как и на больших. Здесь следует провести разницу между геометрией Евклида, имеющей дело исключительно с гладкими кривыми, и бесконечно изрезанными самоподобными фрактальными кривыми. Элементы кривых у Евклида всегда са-моподобны, но тривиальным образом: все кривые являются локально прямыми, а прямая всегда самоподобна. Фрактальная же кривая, в идеале, на любых, даже самых маленьких масштабах не сводится к прямой и является в общем случае геометрически нерегулярной, хаотичной [-]. Дальнейшее изучение фракталов осуществлялось в рамках нового междисциплинарного подхода - синергетики [,-], где одной из центральных задач являлось моделирование объектов и явлений, которым присущ хаос, т. С развитием этого направления удалось выявить регулярные законы и закономерности возникновения, казалось бы, на первый взгляд, хаотичных систем, условие протекания непредсказуемых (или, по крайней мерс, очень сложных) процессов и явлений, показать фрактальные структуры, лежащие в их основе. Более того, при дальнейшем изучении оказалось, что моделирование многих фрактальных объектов физики, химии, биологии и других дисциплин сводится к составлению автономных систем обыкновенных дифференциальных уравнений, зависящих от параметров []. При исследовании дискретных объектов [-,-,-], в основе которых лежит пространственно-временной хаос, аппарат дифференциально-интегрального исчисления не подходит [-]. Подобные объекты моделируются средствами теории графов [-,-]. При этом, получаемые модели обладают всеми свойствами фракталов: дробной размерностью, самоподобием, масштабной инвариантностью, что создало предпосылки возникновения фрактальных графов. Впервые понятие «фрактальный граф» было введено в работе [] Мелроузом. Однако используемый Мелроузом и другими авторами иерархический фрактальный граф обладает тем недостатком, что введен с узкой целью, а именно для отражения иерархии связи с учетом варьируемой разветв-ленности []. Дальнейшее развитие теория предфрактальных и фрактальных графов получила в работах Кочкарова А. М. и Перепелицы В. А. [,,-]. В [,,-] приведены некоторые результаты исследования свойств фрактальных графов. Построению остовных деревьев на фрактальных графах посвящена работа []. Результаты исследований задачи о кликах фрактального графа предложены в []. Появление фрактальных (предфракгальных) графов является логически закономерным следствием стремления возможно более адекватно моделировать реальные технические, экономические, социальные явления и объекты с помощью математического аппарата теории графов. При этом получение бесконечного фрактального графа из конечного предфрактального графа означает (в терминологии [,]) превращение феноменологической модели в асимптотическую. В природе не существует реального объекта, адекватного бесконечному фрактальному графу. Однако последний позволяет выявить и получить качественные свойства из количественных характеристик (параметров) конечной предфрактальной модели. Иными словами, фрактальный граф [,-] - это в конечном счете один из способов выявления некоторых качеств моделируемой системы. Поэтому для решения конкретных задач математики, физики, экономики, биологии, строительства, планирования и т. При этом, чем выше ранг графа, тем более точные результаты получаются при решении задач. Учитывая, что решение многих задач экономики, техники, строительства, планирования и т. Применение же теории предфракгальных и фрактальных графов помогает решать задачи, там, где бессильны традиционные подходы.