On some prefractal graphs properties.pdf Фрактальные графы [1, 2] используются для моделирования структур, растущихпо одним и тем же правилам независимо от точки роста. Не исключается множествен-ный одновременный рост во всей структуре системы. Формальным отражением этихправил является операция замены вершины затравкой (ЗВЗ) [1, 2], она же лежитв основе определения фрактальных графов.Термином «затравка»» условимся называть какой-либо связный граф H = (W, Q).Суть операции ЗВЗ заключается в следующем. В данном графе G = (V, E) у намечен-ной для замещения вершины V Е V выделяется множество V = {Vj : j = 1, 2,..., |V|}смежных ей вершин. Далее из графа G удаляется вершина V и все инцидентные ейребра. Затем каждая вершина Vj Е V соединяется ребром с одной из вершин затравкиH = (W, Q). Вершины соединяются произвольно (случайным образом) или по опреде-ленному правилу.Предфрактальный граф будем обозначать через GL = (VL,El ) , где VL - множе-ство вершин графа, а El - множество его ребер. Определим его рекуррентно, поэтап-но, заменяя каждый раз в построенном на предыдущем этапе l = 1, 2,..., L - 1 графеGi = (Vl, E1) каждую его вершину затравкой H = (W, Q). На этапе l = 1 предфрак-тальному графу соответствует затравка Gi = H. Об описанном процессе говорят, чтопредфрактальный граф GL = (VL,EL) порожден затравкой H = (W, Q). Процесс по-рождения предфрактального графа GL, по существу, есть процесс построения последо-вательности предфрактальных графов G1, G2,..., Gi,..., GL, называемой траекторией.Фрактальный граф G = (V, E), порожденный затравкой H = (W, Q), определяетсябесконечной траекторией. Ранг L определяет «возраст» (число этапов порождения) иразмер (число вершин) предфрактального графа.Использование операции ЗВЗ в процессе порождения предфрактального графа Glдля элементов Gi = (Vi, Ei), l Е {1, 2,..., L - 1}, его траектории позволяет ввести отоб-ражение

Скачать электронную версию публикации