Фрактализация деревьев

Размещено на http://www.allbest.ru/

Северо-Кавказская государственная гуманитарно-технологическая академия, Черкесск, Россия

ФРАКТАЛИЗАЦИЯ ДЕРЕВЬЕВ

Кочкаров Ахмат Магомедович

д.ф.-м.н, профессор

Кочкарова Асият Нерчуковна

При исследовании сложных систем встречаются процессы: экономические, технические, политические структура связей взаимоотношений, которых меняются во времени. Для построения моделей таких структур наиболее адекватным инструментом являются предфрактальные графы [1]

В этой работе исследуются свойства предфратальных графов порожденных одним ребром и вводиться понятия степень фрактализации для определения явления исследуемого объекта предфрактальной и фрактальной структурой.

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

предфрактальный граф дерево фрактализация

Напомним, что для определения фрактального (предфрактального) [1,3,4,7] графа необходимо ввести следующие понятия:

Затравка - любой связный граф [5,6], обозначаемый .

Операцию замены вершины затравкой (ЗВЗ), суть которой состоит в следующем: в данном графенамеченная вершиназаменяется графом - затравкой , при этом каждое инцидентное вершине ребро соединяется с одной из вершин затравки . Это происходит произвольно (случайным образом) или по определенному правилу. Полученная новая структура называется предфрактальный граф.

Предфрактальный граф будем обозначать , где - множество вершин графа, а - множество его ребер. Предфрактальный граф [1,9] определим рекуррентно, поэтапно, заменяя каждый раз в построенном на предыдущем этапе графе каждую его вершину затравкой . На этапе предфрактальному графу соответствует сама затравка . О данном процессе говорят, что предфрактальный граф порожден затравкой . Процесс порождения предфрактального графа , по существу, есть процесс построения последовательности предфрактальных графов , называемой траекторией [11]. Фрактальный граф , порожденный затравкой , определяется бесконечной траекторией.

Для предфрактального графа ребра, появившимся на - ом,
, этапе порождения, будем называть ребрами ранга .

Рассмотрим модель развития структур происходящих на основе алгоритма замены вершины затравкой (ЗВЗ), когда предфрактальные графы порождены простейший затравкой , представляющей собой простейшее двухвершинное дерево (Более простого связного графа имеющего одно ребро не существует). Очевидно, ().

Обозначим эту заставку . Предфрактальные графы, образованные по правилам ЗВЗ и порождаемые данной затравкой назовем простейшими и будем обозначать . При это, в соответствии с определением предфрактальных графив . Далее, - будет представлять с собой простую четырех вершинную цепь, - может быть представлено уже тремя неизоморфными друг другу графами и т.д.

Рассмотрим случай, когда предфрактальные деревья могут порождаться не одной, а двумя затравками , : где - как и прежде ребро с двумя вершинами, а - тривиальное дерево состоящее из одной вершины, не имеющее ребер. С точки зрения конструктивного подхода мы имеем структурный алфавит , из которого в дальнейшем в соответствие с процедурой ЗВЗ строятся предфрактальные деревья. Обозначим Естественно, напрашивается аналогия с широко распространенным алфавитом . На каждом -ом этапе любая вершина дерева заменяется, либо затравкой - , либо - затравкой . Замена вершины затравкой фактически означает, что данная вершина остается неизменной вместе инцидентными ей ребрами. Поэтому, вполне естественно ввести единственное ограничение в применении этого алфавита состоящее в следующем: затравка не может одновременно применяться при замене всех вершин графа, т.к. в этом случае граф просто не изменяется.

Теорема 1. Любое -вершинное дерево является неканоническим предфрактальным деревом в алфавите , может быть получено за этапов применения процедуры ЗВЗ в этом алфавите.

Доказательство. Доказательство этого утверждения следует из того, что для любого - вершинного дерева всегда может быть указан алгоритм его построения за этапов применения процедуры ЗВЗ в данном алфавите . Суть этого алгоритма состоит в том, что на любом этапе ЗВЗ ко всем вершинам дерева кроме одной применяется замена затравкой (т.е. эти вершины остаются неизменными), а одна вершина заменяется затравкой . Таким образом, на каждом этапе ЗВЗ в соответствии с этим алгоритмом в дереве добавляется одно ребро и одна вершина. Понятно, что подобным способом может быть построена любое дерево. Начиная этот процесс с нулевого этапа (), т.е. имея в наличии - единственную вершину, и применяя целенаправленно описанный алгоритм любое - вершинное дерево может быть получено за этапов (по числу ребер в данном дереве), что и доказывает данную теорему. ?

Лемма 1. Объединением двух простейших предфратальных деревьев принадлежавших множеству является простейшее предфрактальное дерево из множество .

Доказательство. Произведем объединение двух равновершинных ППД дополнительным ребром, соединяющим какую - либо вершину первого дерево с некоторой вершиной второго. Полученное дерево будет являться также простейшим предфрактальным деревом следующего ранга. Это видно из того, что если мы объявим дополнительное ребро - ребром первого ранга. А ребрам первого ранга в первоначальных деревьях присвоим ранг два и т.д. Тогда каждой из двух деревьев можно считать полученной процедурой ЗВЗ за L+1 этапов из одной вершины затравки . Лемма доказана. ?

Из утверждения леммы 1 следует, что любое дерево может быть построено за этапов процедуры ЗВЗ, но при этом - вершинная звезда строится только за этапов, а для построения простой цепи можно использовать значительно меньшее их количество, если замену вершин затравкой применять на одном этапе одновременно к нескольким вершинам. В связи с этим возникает естественный вопрос, за какое минимальное число этапов применения процедуры ЗВЗ в алфавите A, может быть построено данное - вершинное дерево (с максимальным значением мы уже определились).

Для ответа на этот вопрос применим к данному - вершинному дереву процедуру обратную к процедуре ЗВЗ. А именно: выделим на данном дереве максимальное парасочетание - максимальное множество не смежных ребер принадлежащих данному дереву. Для звезды это множество всегда состоит из одного ребра, а у дерева имеющего совершенное парасочетание состоит из элементов. Далее строится новое дерево, в котором элементы становятся вершинами (т.е. ребра принадлежащие стягиваются). Следующем шагом выделяется максимальное парасочетание на вновь образовавшемся дереве и т.д. до тех пор, пока на - ом шаге не получиться граф . После этого, повторяя этот процесс в обратном порядке получим алгоритм применение процедуры ЗВЗ в алфавите , приводящий к построению данного дерева за этапов ЗВЗ. Число - будет минимальным числом этапов, за которые может быть построено данное дерево с использованием процедуры ЗВЗ. Назовем это число - числом фрактализации данного дерева. Ниже под символом L будет пониматься именно минимальное число этапов применения операции ЗВЗ необходимых для построения данного дерева.

Степень фрактализации деревьев

Из изложенного выше понятно, что разным деревьям при одном и том же числе вершин могут соответствовать совершенно различные значения числа фрактализации L.

Определение. Степенью фрактализации назовем число

где N - число вершин, L - число фрактализаций данного дерева.

Лемма2. Область значений степени фрактальности .

Доказательство. Утверждение данной леммы следует из неравенства связывающее число вершин дерева n с числом его фрактализации L.

,

т.к. за L этапов ЗВЗ в алфавите A может быть получено «максимальное» -вершинное дерево. Это возникает в случае, если на каждом этапе все вершины заменяются затравкой , что соответствует построению простейших предфрактальных графов. Таким образом, равенство в данном неравенстве достигается, если рассматриваемое дерево является ППД с числом вершин . Лемма доказана.

Следствие. Степень фрактальности простейших предфрактальных деревьев равна единице или

.

Рассмотрим степень фрактальности некоторых типов деревьев.

Лемма3. Степень фрактальности n - вершинной звезды

Доказательство. Так как для звезды максимальное парасочетание всегда состоит из одного ребра для ее построения потребуется этапов процедуры ЗВЗ. Отсюда в соответствии с определением имеем

,

Что и требовалось доказать. ?

Следствие. При степень фрактализации n- вершинной звезды
.

Лемма 3. Степень фрактальности простой цепи удовлетворяет соотношению

Доказательство. Пусть данное дерево является цепью с n вершинами. Максимальное парасочетание простой цепи будет содержать k ребер если n=2k (т.е. число вершин в цепи четно) или n=2k+1 (при нечетном n). После свертки парасочетания получим k - вершинную цепь в первом случае и k+1 - вершинную цепь во втором. Продолжая процесс свертки максимального парасочетания до получения тривиальной цепи получим число фрактализации L-1. Нетрудно получить, что в случае простой цепи L связано с n соотношение

из чего и следует утверждение данной леммы. ?

Для наглядности обратимся к пузырьковой модели приведенной на рисунке 1.

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

а) б)

Рисунок 1 Пузырьковая модель

На рисунке 1 приведены примеры двух заданных графов (а) 8-ми вершинной звезды и (б) 8-ми вершинной цепи.

Рассчитаем степень фрактализации для заданных графов на рисунке 1 (а) и (б).

a)

b)

Введенное понятие позволяет определять насколько «фрактально» данное дерево. Чем ближе значения к 1, тем фрактальное организовано данное дерево. И наоборот, чем ближе к 0, тем ближе структура дерева к фрактальному хаосу.

Литература

1. Кочкаров А.М. Распознавание фрактальных графов. Алгоритмический подход. Нижний Архыз: РАН САО, 1998.

2. Кочкаров А.А., Кочкаров Р.А. Предфрактальные графы в проектировании и анализе сложных структур. Препринт. М.: ИПМ им. М.В. Келдыша РАН, №10, 2003.

3. А.А.Кочкаров. Структурная динамика: свойства и количественные характеристики предфрактальных графов. М.: Вега-Инфо, 2012. 120с.

4. Кочкаров Р.А. Многовзвешенные предфрактальные графы с недетерминированными весами: Приложения в экономике, астрофизике и сетевых коммуникация. М.: ЛЕНАРД, 2017. 432 с.

5. Емеличев Р., Мельников О., Сарванов В., Тышкевич Р. Лекции по теории графов. М.: Наука, 1990.

6. Берж К. Теория графов и ее применения. Пер. с фр. М., Иностранная литература. 1962.

7. Павлов Д. А. Мера сходства предфрактальных графов / Д. А. Павлов // Параллельная компьютерная алгебра и её приложения в новых инфокоммуникационных системах: сб. науч. тр. I Междунар. конф. Ставрополь: Изд.-информ. центр «Фабула», 2014. С. 81-86.

8. Мелроуз Дж. Иерархические фрактальные графы и блуждания на них. В сб. Фракталы в физике М.: Мир, 1988. С. 519-523.23.

9. М.Турбин А.Ф., Працевитый Н.В. Фрактальные множества. Функции, распределения. Киев: Наук. думка, 1992.

10. Кочкаров А.М., Кочкарова А.Н., Л.Х. Хапаева. Моделирование фрактального развития структур простейшими предфрактальными графами. Известия ЮФУ. Технические науки. Ростов-на-Дону. 2016.

11. Павлов Д.А., Салпагаров С.И. Многокритериальная задача выделения маршрутов на предфрактальном графе // Известия ТРТУ. Таганрог: ТРТУ, 2004.

12. Емеличев В.А., Перепелица В.А., Козырев В.А. Обзор некоторых проблем дискретной многокритериальной оптимизации. // Труды сем. по дискретной математике и ее прилож. М.: МГУ, 1989. С. 13-17.

Аннотация

В работе исследуются свойства предфрактальных графов, порожденных затравкой, представляющей собой дерево. Для определения явления исследуемого объекта с фрактальной структурой вводится понятие - степень фрактализации.

Степень фрактализации позволит оценить структуру относительно принадлежности последней к предфрактальным графам

Ключевые слова: ФРАКТАЛЬНЫЙ И ПРЕДФРАКТАЛЬНЫЙ ГРАФ, СТЕПЕНЬ ФРАКТАЛИЗАЦИИ

Annotation

FRACTALIZATION OF TREES

Kochkarov Ahmat Magomedovich Doctor of Physics and Mathematics, Professor

Kochkarova Asiyat Nerchukovna North Caucasus State Humanitarian-Technological Academy, Cherkessk, Russia

In this article, the properties of prefractal graphs generated by a seed representing a tree are investigated. To determine the phenomenon of the object under investigation with a fractal structure, we present a concept which is the degree of fractalization. The degree of fractalization will allow us to evaluate the structure relative to its belonging to the prefractal graphs

Keywords: FRACTAL AND PREDEFACTAL GRAPH, DEGREE OF FRACTALIZATION

Размещено на Allbest.ru