Политематический сетевой электронный научный журнал Кубанского государственного аграрного университета, 2011, №69

Научный журнал КубГАУ, №69(05), 2011 года 
 

http://ej.kubagro.ru/2011/05/pdf/37.pdf
 

1

 
УДК 519.6; 519.17 
 
СТРУКТУРНОЕ РАСПОЗНАВАНИЕ 
ПРЕДФРАКТАЛЬНЫХ ДЕРЕВЬЕВ С 
МНОЖЕСТВОМ ЗАТРАВОК 
 
Кочкаров Ахмат Магомедович 
Доктор физико-математических наук, профессор 
 
Хапаева Лёля Халисовна 
 
Северо-Кавказская Государственная гуманитарно-технологическая академия,  
Черкесск, Россия 
 
В работе определен класс предфрактальных деревьев, порожденных множеством затравок-звезд с 
чередованием. Построен и обоснован алгоритм 
распознавания этого класса предфрактальных графов. Доказан полиномиальный характер предложенного алгоритма распознавания 
 
Ключевые слова: СТРУКТУРНОЕ РАСПОЗНАВАНИЕ, СЕТЕВЫЕ СИСТЕМЫ, ИЕРАРХИЧЕСКИЕ СТРУКТУРЫ, ПРЕДФРАКТАЛЬНЫЕ ДЕРЕВЬЯ, ФРАКТАЛЬНЫЕ ГРАФЫ 
 

 
UDC 519.6; 519.17 
 
PREFRACTAL TREES GENERATED BY SEEDS 
SET STRUCTURAL RECOGNITION 
 
 
Kochkarov Ahmat Magomedovich 
Dr. Sci. (Phys.-Math.), Prof. 
 
Hapaeva Lelya Halisovna 
 
Northern Caucasia Stat academy for technologies and 
humanities,  
Cherkessk, Russia  
 
In paper the class of prefractal the trees generated by 
set of seeds-stars with alternation is defined. The algorithm of this class prefractal graphs recognition is 
proved. It is proved also polynomial character of the 
offered recognition algorithm 
 
 
Key words: STRUCTURAL RECOGNITION, NETWORK 
SYSTEMS, 
HIERARCHICAL 
STRUCTURES, 
PREFRACTAL 
TREES, 
FRACTAL 
GRAPHS 
 
Введение 
Термин “сеть” широко распространен в современной научной и биз
нес-литературе. На слуху такие выражения как “розничная или торговая 

сеть (сеть магазинов)”, “сетевой маркетинг”, “филиальная сеть”, “сеть тру
бопроводов”, “железнодорожная сеть”, “социальная сеть”, “компьютерная 

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

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

лежит сеть, принято называть сетевыми системами [1]. 

На протяжении довольно длительного времени техническая и эконо
мическая науки считали аксиомой стационарность структуры всякой сете
вой системы. Под структурой системы понимали совокупность исключи
тельно устойчивых связей между элементами системы. На этом понимании 

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

Научный журнал КубГАУ, №69(05), 2011 года 
 

http://ej.kubagro.ru/2011/05/pdf/37.pdf
 

2

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

Развивающаяся экономика и глобализационные процессы вынуждают 

сетевые системы развивать, адаптировать, оптимизировать свою сетевую 

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

сетевых структур прослеживаются закономерности. Сетевые структуры не 

только теряют свою стационарность (фиксированность), но и приобретают 

признаки динамических систем. Сетевые структуры приобретают признаки 

и свойства иерархических и масштабно-инвариантных структур. Процессы 

изменения, развития, поведения сетевых структур можно объединить об
щим понятием “структурная динамика”. В системах с изменяющейся 

структурой целесообразно вести контроль над изменениями структуры для 

формирования спектра необходимых свойств и характеристик. Достиже
ние этой цели лежит в русле решения задач структурного управления или 

управления структурной динамикой [2, 3]. 

В качестве моделей структурной динамики сетевых систем в работах 

профессора Кочкарова А.М. предлагаются различные классы масштабно
инвариантных графов, называемых предфрактальными. 

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

развития сетевых структур соответствует тем или иным правилам порож
дения предфрактальных деревьев [4, 5], а во-вторых, определяют какие 

типы затравок при порождении были использованы. 

 

 

Научный журнал КубГАУ, №69(05), 2011 года 
 

http://ej.kubagro.ru/2011/05/pdf/37.pdf
 

3

1. Предфрактальные графы: основные понятия и характеристики 

Предфрактальный граф будем обозначать через 
)
,
(
L
L
L
E
V
G
=
, где 

L
V  − множество вершин графа, а 
L
E  − множество его ребер. Определим 

его рекуррентно, поэтапно, заменяя каждый раз в построенном на преды
дущем этапе 
}
1
,...
2,1
{
−
=
L
l
 графе 
l
G  каждую его вершину связной затрав
кой 
)
,
(
Q
W
H =
. На первом этапе предфрактальному графу соответствует 

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

граф 
)
,
(
L
L
L
E
V
G
=
 порожден затравкой 
)
,
(
Q
W
H =
. Ребра, появившиеся 

на этапе l , 
L
l
,1
=
, порождения предфрактального графа, будем называть 

ребрами ранга l . Новыми ребрами предфрактального графа 
L
G  назовем – 

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

Фрактальный граф определяется бесконечной траекторией. Обобщением 

описанного процесса порождения предфрактального графа 
L
G  является 

такой случай, когда вместо единственной затравки H  используется мно
жество затравок 
{
} {
}
T
t
t
H
H
H
H
H
,...,
,...,
,
2
1
=
=
H
, 
2
≥
T
. Суть этого обоб
щения состоит в том, что при переходе от графа 
1
−
l
G
 к графу 
l
G  каждая 

вершина замещается некоторой затравкой 
H
∈
t
H
, которая выбирается 

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

моделируемого процесса или структуры. Если при переходе от графа 
1
−
l
G
 

к графу 
l
G  каждая вершина графа 
1
−
l
G
 замещается одной конкретной слу
чайно выбранной затравкой 
H
∈
*
t
H
, то будем говорить, что предфрак
тальный граф 
L
G  порожден множеством затравок 
{
}
t
H
=
H
,
T
t
,...,
2,1
=
, 

2
≥
T
, с чередованием. Если же при порождении предфрактального графа 

L
G  множеством затравок 
{
}
t
H
=
H
, 
2
≥
T
, с чередованием задано некото
рое правило выбора затравок из H , например, неубывание числа вершин 

или ребер выбираемых затравок, то будем говорить, что предфрактальный 

граф 
L
G  порожден множеством затравок 
{
}
t
H
=
H
, 
T
t
,...,
2,1
=
, 
2
≥
T
, с 

упорядоченным чередованием. 

Научный журнал КубГАУ, №69(05), 2011 года 
 

http://ej.kubagro.ru/2011/05/pdf/37.pdf
 

4

Очевидно, что порождение фрактального графа 
)
,
(
E
V
G =
 (т.е. когда 

траектория 
является 
бесконечным 
множеством 

,...
,
,...,
,...,
,
1
2
1
+
L
L
l
G
G
G
G
G
) с чередованием затравок, возможно только 

при бесконечном числе замещений затравок 
{
}
t
H
=
H
, 
T
t
,...,
2,1
=
, 
2
≥
T
. 

Если при порождении предфрактального графа с чередованием, для 

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

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

Использованием для порождения предфрактального графа чередованием 

затравок одной и то же затравки на различных этапах порождения исклю
чается. 

В случае порождения предфрактального графа 
L
G  с упорядоченным 

возрастанием (с упорядоченным убываем) затравок 
{
}
t
H
=
H
, 
T
t
,...,
2,1
=
, 

2
≥
T
, если 
T
L >
, то переход на 
1
+
= T
l
 шаге порождения от предфрак
тального графа 
T
G  к 
1
+
T
G
, осуществляется заменой всех вершин графа 

T
G  затравкой с наименьшим (наибольшим) числом вершин из 
{
}
t
H
=
H
, 

T
t
,...,
2,1
=
, 
2
≥
T
. На последующих шагах 
L
T
T
l
,...,
3
,2
+
+
=
 порождения 

предфрактального графа 
L
G  затравки из 
{
}
t
H
=
H
, 
T
t
,...,
2,1
=
, 
2
≥
T
, ис
пользуются последовательно по очередности возрастания (убывания) чис
ла вершин. В случае порождения предфрактального графа 
L
G  число эта
пов порождения больше числа затравок, 
T
L >
, целесообразно говорить о 

периоде замещения вершин затравками. Период замещения вершин за
травкам в процессе порождения предфрактального графа 
L
G  с возрастани
ем или убыванием вершин затравок 
{
}
t
H
=
H
, 
T
t
,...,
2,1
=
, 
2
≥
T
, обозна
чим через Ρ. 

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

являются мощности множеств вершин и ребер. Для предфрактального 

графа порожденного множеством затравок эти характеристики подсчитаны 

в следующих ниже умозаключениях. 

Научный журнал КубГАУ, №69(05), 2011 года 
 

http://ej.kubagro.ru/2011/05/pdf/37.pdf
 

5

ЛЕММА 1. Всякий предфрактальный граф 
L
G , порожденный множе
ством полных затравок 
{
}
t
H
=
H
, 
T
t
,...,
3,2
=
, где 
t
H  − t -вершинный граф 

и 
1
−
= T
L
, с упорядоченным возрастанием имеет 
!
)
(
Т
G
N
L =
 вершин. 

ДОКАЗАТЕЛЬСТВО. Рассмотрим траекторию 
L
l
G
G
G
G
,...,
,...,
,
2
1
 пред
фрактального графа 
L
G , порожденного множеством затравок 
{
}
t
H
=
H
, 

T
t
,...,
3,2
=
 с упорядоченным возрастанием. На первом шаге порождения 

полная двухвершинная затравка из множества H совпадает с первым эле
ментом из траектории предфрактального, 
2
1
H
G =
. Число вершин 

2
)
(
)
(
2
1
=
=
H
N
G
N
. Граф 
2
G  из траектории предфрактального графа 
L
G  

порождается из графа 
1
G  замещением двух его вершин затравками 
3
H , − 

полными трехвершинными графами. Поэтому число вершин графа 
2
G  оп
ределяется как 
6
!3
3
2
3
)
(
)
(
1
2
=
=
∗
=
∗
=
G
N
G
N
. В свою очередь, граф 
3
G  

из траектории предфрактального графа 
L
G  порождается из графа 
2
G  за
мещением всех шести его вершин затравками 
4
H , – полными четырех
вершинными графами. А значит, число вершин графа 
3
G  определяется как 

24
!4
4
3
2
4
3
)
(
4
)
(
)
(
1
2
3
=
=
∗
∗
=
∗
∗
=
∗
=
G
N
G
N
G
N
. 

Аналогичным образом, число вершин графа 
l
G , 
L
l
,...,
3,2
=
, опреде
ляется произведением 
)1
(
)
(
)
(
1
+
∗
=
−
l
G
N
G
N
l
l
. Отметим, что 
1
+
= L
T
, а 

мощность множества затравок 
L
=
H
. Таким образом, Пройдя все этапы 

порождения число вершин предфрактального графа 
L
G , порожденного 

множеством полных затравок, будет равно 
!
)
(
Т
G
N
L =
 ◄1 

ТЕОРЕМА 2. Всякий предфрактальный граф 
L
G , порожденный мно
жеством затравок 
{
}
t
H
=
H
, 
T
t
,...,
3,2
=
, где 
t
H  − t -вершинный граф и 

1
−
= T
L
, с чередованием имеет 
!
)
(
Т
G
N
L =
 вершин. 

ДОКАЗАТЕЛЬСТВО. Согласно общему определению фрактального и 

предфрактального графов число вершин всякого предфрактального графа 

зависит в первую очередь от числа вершин его затравок, и ни коей мере не 

зависит от числа ребер его затравок. Т.е. число вершин предфрактального 

графа не зависит от типа затравки, а зависит от числа ее вершин. Напри                                                
1 Здесь и далее символом “◄” будем обозначать окончание алгоритмов, доказательств лемм и теорем. 

Научный журнал КубГАУ, №69(05), 2011 года 
 

http://ej.kubagro.ru/2011/05/pdf/37.pdf
 

6

мер, предфрактальный граф 
L
J , порожденный полной n -вершинной за
травкой или множеством полных затравок, предфрактальный граф 
L
C , по
рожденный n -вершинным циклом или множеством циклов, и предфрак
тальный граф 
L
D , порожденный n -вершинной цепью или множеством це
пей, будут иметь одинаковое количество вершин. Поэтому, используя ре
зультат предыдущей леммы, можно утверждать, что всякий предфракталь
ный граф 
L
G , порожденный множеством затравок 
{
}
t
H
=
H
, 
T
t
,...,
3,2
=
 с 

чередованием имеет 
!
)
(
Т
G
N
L =
 вершин. ◄ 

ТЕОРЕМА 3. Всякий предфрактальный граф 
L
G , порожденный мно
жеством полных затравок 
{
}
t
H
=
H
, 
T
t
,...,
3,2
=
, где 
t
H  − t -вершинный 

граф 
и 
1
−
= T
L
, 
с 
упорядоченным 
возрастанием 
имеет 

∑
−

=

+
+
+
=
2

1
2
)1
(
)!
2
(
1
)
(
T

l
L
l
l
G
Q
 ребер. 

ДОКАЗАТЕЛЬСТВО. В траектории 
L
l
G
G
G
G
,...,
,...,
,
2
1
 предфрактально
го графа 
L
G , порождаемого множеством затравок 
{
}
t
H
=
H
 с упорядочен
ным возрастанием граф 
2
1
H
G =
 имеет одно ребро и две вершины, 

1
)
( 1 =
G
Q
, 
2
)
( 1 =
G
N
. Напомним, что каждая затравка из множества 

{
}
t
H
=
H
 используется для порождения предфрактального графа только 

один раз, то траектория предфрактального графа 
L
G , порождаемого мно
жеством затравок 
{
}
t
H
=
H
 с чередованием, будет состоять из (
1
−
T
) гра
фов. Предфрактальный граф 
2
G  из траектории, порожденный замещением 

двух вершин графа 
2
1
H
G =
 трехвершинной трехреберной затравкой 
3
H , 

будет имеет 
6
3
*
2
)
(
*
)
(
)
(
3
2
2
=
=
=
H
N
G
N
G
N
 вершин. А число ребер 

графа 
2
G  вычисляется сложением числа ребер графа 
1
G  (
1
)
( 1 =
G
Q
) с чис
лом всех новых ребер полученных при замещении двух вершин графа 
1
G  

трехреберной затравкой 
3
H  − 
7
3
*
2
1
)
(
*
2
)
(
)
(
3
1
2
=
+
=
+
=
H
Q
G
Q
G
Q
. 

Аналогично, число ребер предфрактального графа 
3
G  можно получить 

сложением числа ребер графа 
2
G  с числом новых ребер полученных при 

замещении всех шести вершин графа 
2
G  четырехвершинными шестире

Научный журнал КубГАУ, №69(05), 2011 года 
 

http://ej.kubagro.ru/2011/05/pdf/37.pdf
 

7

берными затравками 
4
H  − 
43
6
*
6
7
)
(
*
6
)
(
)
(
4
2
3
=
+
=
+
=
H
Q
G
Q
G
Q
. Та
ким образом, число ребер каждого последующего предфрактального графа 

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

числа вершин текущего предфрактального графа на число ребер очередной 

затравки: 
)
(
*
)
(
)
(
)
(
2
1
+
+
+
=
l
l
l
l
H
Q
G
N
G
Q
G
Q
, 
1
,...,
3,2
−
=
T
l
, 
1
−
= T
L
. 

Второе слагаемое из правовой части выражения 
)
(
*
)
(
2
+
l
l
H
Q
G
N
 опреде
ляет число новых ребер, которое появляется на каждом этапа порождения, 

или, иначе, соответствует числу новых ребер предфрактального графа 
1
+
l
G
 

из траектории исследуемого предфрактального графа 
L
G . Поэтому число 

всех его ребер 
)
(
L
G
Q
 можно получить путем последовательного сложения 

новых 
ребер 
появляющихся 
на 
всех 
этапах 
порождения: 

∑
−

=
+
+
+
=
1

1
2)
(
)!*
1
(
1
)
(
L

l
l
L
H
Q
l
G
Q
. Учитывая, что для порождения предфрак
тального графа 
)
(
L
G
Q
 используется только полные затравки, а число их 

ребер 
вычисляется 
согласно 
соотношению 
2

)1
(
)
(
−
=
l
l
H
Q
l
, 
то 

∑
∑
−

=

−

=

+
+
+
=
+
+
+
+
=
1

1

1

1
2
)1
(
)!
2
(
1
2
)1
)(
2
(
)!
1
(
1
)
(
L

l

L

l
L
l
l
l
l
l
G
Q
 
или 

∑
−

=

+
+
+
=
2

1
2
)1
(
)!
2
(
1
)
(
T

l
L
l
l
G
Q
. ◄ 

СЛЕДСТВИЕ 3.1. Всякий предфрактальный граф 
L
G , порожденный 

множеством затравок-звезд 
{
}
t
H
=
H
, 
T
t
,...,
4,3
=
, где 
t
H  − t -вершинный 

граф 
и 
2
−
= T
L
, 
с 
упорядоченным 
возрастанием 
имеет 

∑
−

=
+
+
+
=
2

2
)1
(
2
)!
1
(
2
)
(
T

l
L
l
l
G
Q
 ребер. ◄ 

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

Научный журнал КубГАУ, №69(05), 2011 года 
 

http://ej.kubagro.ru/2011/05/pdf/37.pdf
 

8

Под распознаванием предфрактального графа будем понимать опре
деление траектории предфрактального графа при условии, что будут зада
ны затравки. Будем различать два вида распознавания: явное и неявное. 

Под неявным распознаванием подразумеваем утверждение о том, что 

данный граф является фрактальным и базируется на некоторой n 
вершинной затравке или множестве затравок 
{
}
t
H
=
H
, 
T
t
,...,
3,2
=
. 

Явное распознавание подразумевает представление в явном виде 

множества ребер для каждого ранга или представление в явном виде тра
ектории данного графа 
)
,
(
E
V
G =
, что подразумевает и определение (рас
познавание) затравки или множества затравок, порождающих предфрак
тальный граф. 

Итак, рассмотрим следующую проблему. Пусть представлен в явном 

виде некоторый граф 
)
,
(
E
V
G =
, обладающий двумя необходимыми (но не 

являющимися достаточными) признаками предфрактального графа, поро
жденного с чередованием затравок:  

1) Для мощности множества вершин V  существует пара T  и L , та
ких, что 
1
−
= T
L
 и 
!
T
V =
; 

2) Для мощности множества ребер 
E  справедливо равенство 

∑
−

=

+
+
+
=
2

1
2
)1
(
)!
2
(
1
T

l

l
l
E
. 

Сформулируем два вопроса из области теории распознавания:  

а) является ли данный граф G предфрактальным, порожденным мно
жеством полных затравок; 

б) можно ли построить достаточно эффективный алгоритм, который 

гарантированно дает положительный или отрицательный ответ на вопрос 

а). 

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

т.е. предфрактальный граф так же должен быть деревом [4]. 

Научный журнал КубГАУ, №69(05), 2011 года 
 

http://ej.kubagro.ru/2011/05/pdf/37.pdf
 

9

Результатом работы многих процессов являются структуры, отра
жающиеся диадическими деревьями [5]. Естественным обобщением этого 

понятия является R-адическое дерево [5]. 

Термином “R-адическое дерево” называем всякое дерево, у которого 

каждая невисячая вершина имеет степени r + 1, 
2
≥
r
. С учетом практиче
ских приложений различают R-адическое дерево и корневое R-адическое 

дерево [5].  

Простейший случай, когда диадическое дерево порождается единст
венной затравкой, которая представляет собой 3-вершинную звезду. Ана
логично R-адическое дерево порождается затравкой, которая представляет 

собой (
)
r + 1 -вершинную звезду. 

Сохраняя для обозначения дерева символ G, можем представлять 

траекторию порождения предфрактального дерева в тех же обозначениях, 

что и последовательность 
L
r
G
G
G
G
,...,
,...,
,
2
1
. Алгоритм получения этой 

траектории в случае порождения предфрактального R-адического дерева 

описывается следующим образом. 

Переход от текущего дерева 
)
,
(
r
r
r
E
V
G =
 к текущему дереву Gr +1 

всякий раз подчиняется трем общим правилам.  

1) Если вершина 
r
V
v ∈
 не является висячей, то она не замещается 

затравкой; 

2) замещаемая затравкой вершина 
r
V
v ∈
 выбирается только из под
множества висячих вершин, а само висячее ребро становится ин
цидентным центру звезды; 

3) если какая-либо висячая вершина 
r
V
v ∈
 оказалась незамещенной 

затравкой, то она называется “замороженной” и по отношению к 

ней операция ЗВЗ не применяется ни на каком из следующих эта
пов 
L
r
r
,...,
2
,1
+
+
. 

Отметим, что в траектории 
L
r
G
G
G
G
,...,
,...,
,
2
1
 ее начальный элемент 

1
G  представляет собой (
)
r + 1 -вершинную звезду. 

Естественным обобщением R-адического дерева является предфрак
тальное дерево, которое порождается в точном соответствии с описанными 

правилами 1) − 3) с тем лишь отличием, что “незамороженная” висячая 

Научный журнал КубГАУ, №69(05), 2011 года 
 

http://ej.kubagro.ru/2011/05/pdf/37.pdf
 

10

вершина замещается альтернативно некоторой звездой из заданного мно
жества звезд 
{ }
H
=
H
. Полученное таким образом дерево принято назы
вать термином “ H -дерево”. Распознавание H -дерева сводится к простой 

визуализации, подробнее об этом можно узнать в работе [5]. 

Несколько более сложным случаем является задача распознавания 

предфрактального H -дерева с чередованием затравок. 

Переход в траектории 
L
r
G
G
G
G
,...,
,...,
,
2
1
 H -дерева с чередованием 

затравок от текущего дерева 
)
,
(
r
r
r
E
V
G =
 к текущему дереву Gr +1 всякий 

раз подчиняется следующим правилам 

I. Если вершина 
r
V
v ∈
 не является висячей, то она не замещается за
травкой; 

II. Каждая висячая вершина 
r
V
v ∈
 замещается затравкой 
H
∈
∗
H
, 

выбранной случайным образом из множества затравок-звезд 

{
}
t
H
=
H
, а каждое висячее ребро становится инцидентным центру 

звезды 
H
∈
∗
H
; в каждом переходе от графа 
r
G  к графу 
1
+
r
G
 ис
пользуется для замещения вершин только одна затравка 
{ }
H
=
H
 и 

T
L ≥
, причем каждая затравка используется (выбирается) в про
цессе порождения не менее одного раза; 

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

множеством затравок-звезд, вытекает из следствия 3.1. 

 

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

Приведем описание алгоритма 
1
α  распознавания предфрактального 

H -дерева с чередованием затравок.  

АЛГОРИТМ 
1
α Состоит из 
L
l
k
,...,
,...,
2,1
=
 этапов. На каждом из этапов алго
ритма выполняются три ключевые операции: окрашивание (выделение) 

вершины, окрашивание (выделение) ребра, стягивание ребра. На вход пер
вого 
1
=
k
 этапа алгоритма предъявляется предназначенное для распозна
вание дерево 
)
,
(
E
V
G =
 и пустое множество H . На вход каждого из этапов