Фрактальные и предфрактальные графы, основные определения и обозначения

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

УДК 519.1

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

Фрактальные и предфрактальные графы, основные определения и обозначения

Кочкаров Расул Ахматович, кандидат экономических наук

РИНЦ SPIN-код 5253-4030

1. Финансовый университет при Правительстве Российской Федерации, Москва, Россия, 2. Институт проблем управления РАН, Москва, Россия rasul_kochkarov@mail.ru

Павлов Дмитрий Алексеевич, кандидат физико-математических наук

РИНЦ SPIN-код 8822-5089

Кубанский государственный аграрный университет им. И.Т. Трубилина, Krasnodar, Russia

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

Аннотация

В работе приводится описание фрактального и предфрактального графа. Предложены основные определения и обозначения, приводится процедура построения предфрактального графа, операция замещения вершины затравкой.

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

Abstract

Doi: 10.21515/1990-4665-134-015

UDC 519.1

Physics and mathematics

Fractal and preefactal graphs, basic definitions and symbols

Kochkarov Rasul Ahmatovich, Candidate in Economic Sciences

SPIN-code 5253-4030

1. Financial University under the Government of the Russian Federation, Russian Federation, Moscow

2. Institute for Control Sciences of RAS, Russian Federation, Moscow, rasul_kochkarov@mail.ru

Pavlov Dmitry Alekseevich, Candidate in Physics and mathematics

SPIN-code 8822-5089

Kuban State Agrarian University, Krasnodar, Russia

Hubieva Diana Abrek-Zaurovna, Postgraduate Student, North Caucasus Humanitarian-Technological Academy, Cherkessk, Russia

The fractal and prefractal graph are described in the article. The basic definitions and notation are proposed, the procedure for constructing prefractal graph, the operation of replacement vertex by seed is given

Keywords: FRACTAL GRAPH, PREFRACTAL GRAPH, REPLACEMENT VERTEX BY SEED

Для обозначения графа - конечного или бесконечного в работе используется общепринятое обозначение

[1, 2].

Для определения предфрактальных (prefractal) и фрактальных (fractal) графов приведем дополнительные определения (в скобках приводятся англоязычная терминология) [3, 4].

Затравкой (seed) называется какой-либо связный _вершинный граф

c непомеченными (ненумерованными) вершинами .

Операция замещения вершины затравкой.

Обобщением известной операции расщепления вершины графа является операция замещения вершины затравкой (ЗВЗ, replacement vertex by seed, RVS). Суть этого обобщения состоит в том, что расщепляемая вершина замещается не ребром, а затравкой .

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

Операция ЗВЗ реализуется следующим образом. В данном графе

у намеченной для замещения вершины выделяется ее окружение (environment of a vertex) - множество всех вершин, смежных с вершиной , и множество всех ребер, инцидентных вершине

,

- число вершин во множестве . Далее определяется отображение вершин во множество вершин затравки (см. рис. 1.а и 1.б):

, (1)

то есть каждой вершине ставится в соответствие определяемая с помощью вершина затравки

. После чего у каждого ребра

выделенного окружения конец заменяется на определяемую отображением (1) вершину

затравки (см. рис. 1.в и 1.г). Старое ребро

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

затравки H. Ненумерованным вершинам затравки присваиваются номера с учетом уже имеющихся номеров других вершин данного графа . Аналогично присваиваются обозначения (номера) ребрам затравки, которые заместили намеченную вершину .

Рассмотрим поэтапный процесс выполнения операции ЗВЗ. На этапе в данной затравке

нумеруются вершины и ребра, полученный граф обозначается через

.

На этапе все вершины графа замещаются затравкой . На рис. 2 представлен пример замещения вершин графа затравкой - полный 3-вершинный граф (треугольник), где смежность старых ребер выбирается произвольная: (а) малыми пунктирными окружностями обведены вершины, замещаемые затравкой; (б) средними пунктирными окружностями обведены затравки, замещающие вершины; (в) старые ребра графа выделены жирными линиями.

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

На каждом следующем этапе к вершинам применяется операция ЗВЗ, по завершению этапа получен граф

,

который называется предфрактальным (если , то речь идет о фрактальном графе). На этапе

для каждой вершины осуществляется операция ЗВЗ - замещение вершины затравкой . В процессе выполнения этих операций все ребра сохраняются и далее называются старыми ребрами (old edges) по отношению ко всем текущим графам

,

где . При этом все старые ребра, инцидентные замещаемой вершине , становятся (случайным, либо регулярным образом) инцидентными вершинам затравки, заместившей вершину .

Ребра каждой из таких заместивших затравок называются новыми ребрами (new edges), то есть множество новых ребер можно представить как . При этом ребра этого множества являются старыми в текущих графах

. Т

таким образом, граф

получается в результате применения операции ЗВЗ к каждой из вершин .

Предфрактальный граф обозначается через

,

где множество вершин графа, а множество его рёбер. Определяется он рекуррентно, в построенном на предыдущем этапе графе каждая его вершина заменяется затравкой . На этапе предфрактальному графу соответствует затравка : . Об описанном процессе говорят, что предфрактальный граф порождён затравкой (generated by seed). Процесс порождения предфрактального графа по существу есть процесс построения последовательности предфрактальных графов , называемой траекторией (trajectory). Фрактальный граф

определяется бесконечной траекторией [5].

На рис. 3 представлена траектория предфрактального графа , порожденного затравкой-треугольником, смежность старых ребер выбрана произвольной.

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



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

Обобщением процесса порождения предфрактального графа является такой случай, когда вместо единственной затравки задается множество затравок

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

,

то есть количества их вершин, соответственно равны:

.

Для упрощения в дальнейшем будут использоваться обозначения: затравка

,

количество вершин затравки

,

количество ребер затравки

.

На рис. 4 представлен пример порождения предфрактального графа , порожденного множеством затравок смежность старых ребер выбрана произвольной: (а)

:

- полный 3-вершинный граф-треугольник; - полный 2_вершинный граф; - 4_вершиннаый граф-звезда; (б) затравки, вновь заместившие вершины, обведены малыми пунктирными окружностями; (в) большие пунктирные окружности обводят подграфы, появившиеся вместо вершин графа после второго этапа замещения вершин затравкой.

Канонический и неканонический предфрактальные графы.

Отличительной особенностью процесса порождения предфрактального графа является то, что на каждом этапе в текущем графе

замещается той или другой затравкой каждая вершина . Предфрактальные графы, получаемые в результате такого процесса, называем каноническими (canonical).

В общем случае неканонический (noncanonical) предфрактальный граф порождается множеством затравок мощности , однако при одном принципиальном отличии: при переходе от графа к графу в траектории

,

замещается затравкой из не каждая вершина

,

а лишь подмножество вершин

,

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

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

На рис. 5 представлен неканонический предфрактальный граф , порожденный единственной затравкой - полный 3-вершинный граф (треугольник), при сохранении смежности старых ребер. Вершина не была замещена затравкой на третьем этапе, а вершина замещена затравкой только на третьем. Суммарно получается, что на втором шаге только две вершины из трех замещены затравкой, на третьем шаге замещены все вершины кроме одной. Малыми пунктирными окружностями обведены затравки, появившиеся на последнем - третьем этапе замещения вершин графа. В подграфе, обведенном большой пунктирной окружностью, замещались все вершины на всех этапах. Фактически этот подграф является каноническим подграфом (canonical subgraph) и, если рассматривать его отдельно, - каноническим предфрактальным графом.

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

На рис. 6 представлен неканонический предфрактальный граф , порожденный множеством затравок , смежность старых ребер выбрана произвольной: (а) вершина не была замещена затравкой на втором этапе; (б) вершины и не замещены затравками на третьем.

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

Нетривиальным случаем операции ЗВЗ в процессе порождения предфрактального графа , траектории

,

является замещение вершины не затравкой, а графом траектории

, ; .

На рис. 7. изображен неканонический предфрактальный граф , в котором на последнем - четвертом этапе порождения две вершины замещены графом из траектории .

Предфрактальный мультиграф

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

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

Предфрактальный граф, порожденный множеством мультиграф-затравок либо единственной мультиграф-затравкой, условимся называть предфрактальным мультиграфом (prefractal multigraph).

На рис. 8 изображен канонический предфрактальный мультиграф , порожденный множеством затравок

,

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

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

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



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

Предфрактальные графы, порожденные затравками - гиперграфами, являются сложными объектами и требуют отдельного исследования. Напомним, что в гиперграфе ребром могут соединяться не строго две вершины, а любые подмножества вершин.

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

Cписок литературы

1. Кочкаров А.М. Асимптотический подход к многокритериальной задаче покрытия графа цепями // Доклады Академии наук Белорусской ССР. - 1983. Т. XXY. - № 10. - С. 911.

2. Кочкаров А.М., Байрамукова З.Х. Спектры предфрактальных графов с затравками-циклами, сохраняющих смежность старых ребер // Политематический сетевой электронный научный журнал Кубанского государственного аграрного университета. - 2012. - № 81. - С. 93-102.

3. Павлов Д.А., Кочкаров Р.А. Алгоритмы с оценками построения покрытий непересекающимися простыми цепями на предфрактальном графе // Препринт САО РАН. - 2004. - № 199. - 22 с.

4. Павлов Д.А., Кочкаров А.А. Об одной многокритериальной задаче покрытия минимального веса предфрактального графа простыми пересекающимися цепями // Препринт САО РАН. - 2004. - № 200. - 12 с.

5. Кочкаров А.А., Кочкаров Р.А., Малинецкий Г.Г. Некоторые аспекты динамической теории графов // Журнал вычислительной математики и математической физики. - 2015. - Т. 55. № 9. - С. 1623-1629.

References

1. Kochkarov A.M. Asimptoticheskij podhod k mnogokriterial'noj zadache pokrytija grafa cepjami // Doklady Akademii nauk Belorusskoj SSR. - 1983. T. XXY. - № 10. - S. 911.

2. Kochkarov A.M., Bajramukova Z.H. Spektry predfraktal'nyh grafov s zatravkami-ciklami, sohranjajushhih smezhnost' staryh reber // Politematicheskij setevoj jelektronnyj nauchnyj zhurnal Kubanskogo gosudarstvennogo agrarnogo universiteta. - 2012. - № 81. - S. 93-102.

3. Pavlov D.A., Kochkarov R.A. Algoritmy s ocenkami postroenija pokrytij neperesekajushhimisja prostymi cepjami na predfraktal'nom grafe // Preprint SAO RAN. - 2004. - № 199. - 22 s.

4. Pavlov D.A., Kochkarov A.A. Ob odnoj mnogokriterial'noj zadache pokrytija minimal'nogo vesa predfraktal'nogo grafa prostymi peresekajushhimisja cepjami // Preprint SAO RAN. - 2004. - № 200. - 12 s.

5. Kochkarov A.A., Kochkarov R.A., Malineckij G.G. Nekotorye aspekty dinamicheskoj teorii grafov // Zhurnal vychislitel'noj matematiki i matematicheskoj fiziki. - 2015. - T. 55. № 9. - S. 1623-1629.

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