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

УДК 519.1

01.00.0 Физико-математические науки

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

Кочкаров Ахмат Магомедович д.ф.-м.н, профессор РИНЦ SPIN-код 8363-0831

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

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

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

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

Бок 10.21515/1990-4665-134-013

UDC 519.1

Physics and mathematics

FRACTALIZATION OF TREES

Kochkarov Ahmat Magomedovich Doctor of Physics and Mathematics, Professor RSCI SPIN code 8363-0831

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

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

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

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

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

1 Исследование выполнено при финансовой поддержке РФФИ в рамках научного проекта № 16 - 07 - 00231а.

Затравка - любой связный граф [5,6], обозначаемый Н = (Ш, Операцию замены вершины затравкой (ЗВЗ), суть которой состоит в следующем: в данном графе й = (V, Е) намеченная

вершина V 6 ^заменяется графом - затравкой Н = (Ж, при этом каждое инцидентное вершине V ребро соединяется с одной из вершин затравки Н. Это происходит произвольно (случайным образом) или по определенному правилу. Полученная новая структура называется предфрактальный граф.

Предфрактальный граф будем обозначать = Еь), гдеУ^ - множество вершин графа, а Еь- множество его ребер. Предфрактальный граф [1,9] определим рекуррентно, поэтапно, заменяя каждый раз в построенном на предыдущем этапе I = 1,2, ...,£-1графе = (1^,Е{) каждую его вершину затравкой Н = (И^, (}). На этапе I = 1 предфрактальному графу соответствует сама затравка = Н. О данном процессе говорят, что предфрактальный граф ^ = (Уь, Еь) порожден затравкой Н = (Ж, (}). Процесс порождения предфрактального графа по существу, есть процесс построения последовательности предфрактальных графов ••• называемой траекторией [11]. Фрактальный граф в = (7, £"), порожденный затравкой Н = (14/", О), определяется бесконечной траекторией.

Для предфрактального графа ^ ребра, появившимся на I - ом, I £ {1,2,..., ¿}, этапе порождения, будем называть ребрами ранга I.

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

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

Рассмотрим случай, когда предфрактальные деревья могут порождаться не одной, а двумя затравками Я0, Нг: где #i- как и прежде ребро с двумя вершинами, а Я0 - тривиальное дерево состоящее из одной вершины, не имеющее ребер. С точки зрения конструктивного подхода мы имеем структурный алфавит А = {Я0, Я-J, из которого в дальнейшем в соответствие с процедурой ЗВЗ строятся предфрактальные деревья. Обозначим А = {о; о-о}. Естественно, напрашивается аналогия с широко распространенным алфавитом {0; 1}. На каждом -ом этапе любая вершина дерева заменяется, либо затравкой - Я0, либо - затравкой Нь Замена вершины затравкой Я0 фактически означает, что данная вершина остается неизменной вместе инцидентными ей ребрами. Поэтому, вполне естественно ввести единственное ограничение в применении этого алфавита состоящее в следующем: затравка Я0 не может одновременно применяться при замене всех вершин графа, т.к. в этом случае граф просто не изменяется.

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

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

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

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

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

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

алфавите A, может быть построено данное п - вершинное дерево (с максимальным значением L = п-1 мы уже определились).

Для ответа на этот вопрос применим к данному п - вершинному дереву процедуру обратную к процедуре ЗВЗ. А именно: выделим на данном дереве максимальное парасочетание М1 - максимальное множество не смежных ребер принадлежащих данному дереву. Для звезды это множество всегда состоит из одного ребра, а у дерева имеющего совершенное парасочетание М1 состоит из п/2 элементов. Далее строится

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

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

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

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

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

Лемма2. Область значений степени фрактальности ¿'(/¿(Г)) 6 (0; 1].

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

2 L>n,

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

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

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

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

V- =

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

п

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

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

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

Г1г<\1<1

Доказательство. Пусть данное дерево является цепью с n вершинами. Максимальное парасочетание простой цепи будет содержать к ребер если

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

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

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

а)

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

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

\ 8 1 т п

a) ^ = ¥ = Тв' 1 = 1

b) ¡1 = 1 = 1, Ь = з

Введенное понятие позволяет определять насколько «фрактально» данное дерево. Чем ближе значения {! к 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.

References

1. Kochkarov A.M. Raspoznavanie fraktal'nyh grafov. Algoritmicheskij podhod. ? Nizhnij Arhyz: RAN SAO, 1998.

2. Kochkarov A.A., Kochkarov R.A. Predfraktal'nye grafy v proektirovanii i analize slozhnyh struktur. Preprint. - M.: IPM im. M.V. Keldysha RAN, №10, 2003.

3. A.A.Kochkarov. Strukturnaja dinamika: svojstva i kolichestvennye harakteristiki predfraktal'nyh grafov. - M.: Vega-Info, 2012. - 120s.

4. Kochkarov R.A. Mnogovzveshennye predfraktal'nye grafy s nedeterminirovannymi vesami : Prilozhenija v jekonomike, astrofizike i setevyh kommunikacija. - M.: LENARD, 2017. - 432 s.

5. Emelichev R., Mel'nikov O., Sarvanov V., Tyshkevich R. Lekcii po teorii grafov. M.: Nauka, 1990.

6. Berzh K. Teorija grafov i ee primenenija. Per. s fr.-M., Inostrannaja literatura.

1962.

7. Pavlov D. A. Mera shodstva predfraktal'nyh grafov / D. A. Pavlov // Parallel'naja komp'juternaja algebra i ejo prilozhenija v novyh infokommunikacionnyh sistemah : sb. nauch. tr. I Mezhdunar. konf. - Stavropol' : Izd.-inform. centr «Fabula», 2014. - S. 81-86.

8. Melrouz Dzh. Ierarhicheskie fraktal'nye grafy i bluzhdanija na nih . V sb. Fraktaly v fizike M.: Mir, 1988.-S.519-523.23.

9. M.Turbin A.F., Pracevityj N.V. Fraktal'nye mnozhestva. Funkcii, raspredelenija.-Kiev:Nauk. dumka, 1992.

10. Kochkarov A.M., Kochkarova A.N., L.H. Hapaeva. Modelirovanie fraktal'nogo razvitija struktur prostejshimi predfraktal'nymi grafami. Izvestija JuFU. Tehnicheskie nauki. Rostov-na-Donu -2016.

11. Pavlov D.A., Salpagarov S.I. Mnogokriterial'naja zadacha vydelenija marshrutov na predfraktal'nom grafe // Izvestija TRTU. Taganrog: TRTU, 2004

12. Emelichev V.A., Perepelica V.A., Kozyrev V.A. Obzor nekotoryh problem diskretnoj mnogokriterial'noj optimizacii. // Trudy sem. po diskretnoj matematike i ee prilozh. -M.: MGU,1989.-S.13-17.