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

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

http://ej.kubagro.ru/2011/04/pdf/30.pdf

1

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

UDC 519.6;519.17 
 
RECOGNIZING OF PREFRACTAL GRAPH 
ARISING FROM OF TWO FULL ZATRAVKAS

L.H. Hapaeva 
 
North-Caucasian  state humane-technological Academy, Cherkessk, Russia 
 
The private task of prefractal graph recognizing, arising from pair of full zatravkas by alternations, was examined. The offered algorithm of  recognizing decide 
this task during the polynominal time.   
 
 
Key words: PREFRACTAL GRAPF. GRAPH RECOGNIZING.  NET SYSTEM. ZATRAVKA. 
 
 
 
Развивающаяся экономика и глобализационные процессы вынуждают се
тевые системы [6] развивать, адаптировать, оптимизировать свою сетевую струк
туру под сильно изменчивую конкурентную среду, и под новую геополитиче
скую конъюнктуру. В такой ситуации в регулярных изменениях сетевых струк
тур прослеживаются закономерности. Сетевые структуры не только теряют свою 

стационарность (фиксированность), но и приобретают признаки динамических 

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

масштабно-инвариантных структур. Процессы изменения, развития, поведения 

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

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

[2]. Своим рождением фрактальные (предфрактальные) графы обязаны синтезу 

идей синергетики [3] и нелинейной динамики [4], фракталов [8], и теории графов 

[1]. 

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

профессора Кульбы В.В. [7], член-корреспондента РАН Новикова Д.А. [8], про
фессора Кочкарова А.М. [4] в таких научно-исследовательских институтах и ве
дущих 
ВУЗах 
России, 
как 
Институт 
проблем 
управления 

им. В.А. Трапезникова РАН, 
Институт 
прикладной 
математики им. 

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

http://ej.kubagro.ru/2011/04/pdf/30.pdf

2

 М.В. Келдыша  РАН, Вычислительный центр им. А.А. Дородницына  РАН,  Ка
рачаево-Черкесская государственная технологическая академия. Работы членов 

школ профессора Кульбы В.В. и член-корреспондента Новикова Д.А. посвящены 

в большей степени вопросам взаимодействия между элементами сложных иерар
хических систем, чем вопросам изменчивости и динамики самих сетевых струк
тур. В работах же школы профессора Кочкарова А.М., наоборот, первичное вни
мание уделено именно вопросам поведения-развития сетевых структур.  

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

задачу распознавания самого процесса развития-изменения структуры се
тевой системы. Задачу, объединяющую две указанные, назовем задачей 

структурного распознавания. Алгоритмы распознавания, строящие реше
ние задачи структурного распознавания, во-первых, устанавливают, что 

процесс развития сетевых структур соответствует тем или иным правилам 

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

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

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

настоящей работе определен особый класс предфрактальных графов - 

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

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

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

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

его рекуррентно, поэтапно, заменяя каждый раз в построенном на преды

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

http://ej.kubagro.ru/2011/04/pdf/30.pdf

3

дущем этапе 
}
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
, с 

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

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

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

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

http://ej.kubagro.ru/2011/04/pdf/30.pdf

4

,...
,
,...,
,...,
,
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
, обозна
чим через Ρ.  

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

возрастанием и при сохранении смежности старых ребер. 

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

http://ej.kubagro.ru/2011/04/pdf/30.pdf

5

                                 F1                                                                F2

                                                 G2

                                                                                              G3

Рис. 1. Траектория предфрактального графа, порожденного парой полных 
затравок 

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

http://ej.kubagro.ru/2011/04/pdf/30.pdf

6

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

текущего графа 
)
,
(
r
r
r
E
V
G =
 к следующему графу 
1
+
r
G
 всякий раз подчиняется 

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

при сохранении смежности старых ребер. 

Распознавание предфрактального графа 
)
,
(
L
L
L
E
V
G
=
, порожденного па
рой полных затравок 
)
,
(
1
1
1
E
V
F =
 и 
)
,
(
2
2
2
E
V
F =
 с числом вершин 
1
m  и 
2
m  

(
2
1
m
m <
) соответственно, с возрастанием и при сохранении смежности старых ре
бер можно осуществить алгоритмом β . Суть алгоритма β  заключается в иденти
фикации графов 
)
,
(
1
1
1
E
V
F =
, 
)
,
(
2
2
2
E
V
F =
 как затравок предфрактального графа 

)
,
(
L
L
L
E
V
G
=
, а также идентификации траектории самого предфрактального гра
фа. 

На рис. 1 изображена траектория предфрактального графа 
)
,
(
3
3
3
E
V
G =
, по
рожденного парой полных затравок – 3-вершинным графом 
)
,
(
1
1
1
E
V
F =
 и 4
вершинным 
)
,
(
2
2
2
E
V
F =
, с возрастанием и при сохранении смежности старых 

ребер. 

Алгоритм β  состоит из 
L
l
k
,...,
,...,
2,1
=
 этапов. На каждом из этапов алго
ритма β  выполняются три ключевые операции: окрашивание (выделение) верши
ны, окрашивание (выделение) ребра, стягивание ребра, стягивание цепи. На вход 

первого 
1
=
k
 этапа алгоритма предъявляется предназначенный для распознавание 

граф 
)
,
(
E
V
G =
. На вход каждого из этапов 
1
,...,
,...,
2,1
−
=
L
l
k
 алгоритма β  

предъявляется граф 
)
,
(
k
k
k
E
V
G
=
, как результат работы предыдущего этапа. 

Определим число вершин графа 
)
,
(
E
V
G =
 и обозначим их через N . Разде
лим число вершин графа 
)
,
(
E
V
G =
 на произведение 
2
1m
m
 последовательно необ
ходимое количество раз, чтобы получить представление 
r
m
m
N
K
)
(
2
1
=
. Возмож
ны два случая: 
1
=
r
, 
1
m
r =
. Рассмотрим каждый из них подробно. Если остаток r

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

http://ej.kubagro.ru/2011/04/pdf/30.pdf

7

не удовлетворяет ни одному из указанных вариантов, то алгоритм 
3
β  завершает 

свою работу с отрицательным результатом. 

Пусть 
1
=
r
. Тогда 
L
G
G =
, а число этапов алгоритма β  равно 
K
L
2
=
. За
тем у графа 
L
G  производим поиск всех вершины степени 
1
2 −
m
 и объединяем их 

в множество 
L
m
V
2 . Затем полученное множество 
L
m
V
2  разбивается на подмножества 

с учетом взаимной смежности составляющих его вершин следующим образом. Вы
деляем вершину 
L
m
V
v
2
∈
 и смежные ей (
2
2 −
m
) вершины из множества 
L
m
V
2 . Если 

вершина 
L
m
V
v
2
∈
 не имеет в множестве 
L
m
V
2  смежных с ней (
2
2 −
m
) вершин, то 

алгоритм β  заканчивает свою работу с отрицательным результатом. В процессе 

разбиения множества 
L
m
V
2  на подмножества, вершины не выделяются более одного 

раза. После разбиения множества 
L
m
V
2  на подмножества, в каждом подмножестве 

проводиться проверка на взаимную смежность всех ее (
1
2 −
m
) вершин. Далее вы
деляются ребра обеспечивающие смежность вершин в каждом из подмножестве. Их 

число в каждом из подмножестве равно 
2

)
2
)(
1
(
2
2
−
−
m
m
, в противном случае ал
горитм заканчивает свою работу с отрицательным результатом.  

Далее проверяем смежность всех (
1
2 −
m
) вершин каждого выделенного 

подмножества с одной вершиной, степень которой больше чем 
1
2 −
m
. Если тако
вая имеется, выделяя ее и все ребра соединяющие эту вершину с уже выделенными, 

получим выделенный полный подграф с 
2
m  вершинами. Такие полные подграфы 

должны быть выделены на графе 
L
G  в соответствии с числом подмножеств мно
жества 
L
m
V
2 , в противном случае алгоритм заканчивает свою работу с отрицатель
ным результатом. 

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

http://ej.kubagro.ru/2011/04/pdf/30.pdf

8

Далее стягиваем все выделенные ребра. И на вход следующего этапа алго
ритма β  передается граф 
1
−
L
G
. На графе 
1
−
L
G
, как и предыдущем шаге, выделя
ем все вершины степени 
1
1 −
m
 и объединяются в множество 
1

1
−
L
m
V
. С множеством 

1

1
−
L
m
V
 проделываются те же операции относительно вершин со степенью 
1
1 −
m
, 

что и с вершинами множества Далее стягиваем все выделенные ребра. На вход сле
дующего этапа алгоритма β  передается граф 
2
−
L
G
. На всех последующих этапах 

проведем операции по стягиванию выделяемых полных подграфов, чередую число 

их вершин 
1
m  и 
2
m  в продолжении уже начатой последовательности на первых 

двух шагах. На выходе последнем шага получим полный граф 
1
G  с число вершин 

1
m , в противном случае алгоритм β  завершает свою работу с отрицательным ре
зультатом. 

Пусть 
1
m
r =
. Тогда 
L
G
G =
, а число этапов алгоритма β  равно 
1
2
+
= K
L
. 

Затем на графе 
L
G  выделяем все вершины степени 
1
1 −
m
. Далее процесс распо
знавания графа 
L
G
G =
 при 
1
m
r =
 идентичен предыдущему случаю, когда 
1
=
r
. 

Результатом работы алгоритма 
3
β  в случаях когда 
1
=
r
, 
1
m
r =
 является 

траектория 
)
,
(
)
,
(
k
k
k

k
k
k
E
V
G
E
V
G
=
=
=
, 
L
l
k
,...,
,...,
2,1
=
, предфрактального 

графа 
)
,
(
L
L
L
E
V
G
=
, порожденного парой полных затравок 
)
,
(
1
1
1
E
V
F =
, 

)
,
(
2
2
2
E
V
F =
 с числом вершин 
1
m  и 
2
m  (
2
1
m
m <
) соответственно, с возрастани
ем и при сохранении смежности старых ребер. ◄ 

Не налагая дополнительных ограничений на водные данные с алгоритм 
3
β , 

кроме изменения условия 
2
1
m
m <
 на 
2
1
m
m >
 можно переориентировать  алго
ритм 
3
β  на распознавание предфрактального графа 
)
,
(
L
L
L
E
V
G
=
, порожденного 

парой полных затравок 
)
,
(
1
1
1
E
V
F =
, 
)
,
(
2
2
2
E
V
F =
 с числом вершин 
1
m  и 
2
m  

(
2
1
m
m >
) соответственно, с убывание и при сохранении смежности старых ребер. 

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

http://ej.kubagro.ru/2011/04/pdf/30.pdf

9

ТЕОРЕМА 1. Всякий предфрактальный граф 
)
,
(
L
L
L
E
V
G
=
, порожденный 

парой полных затравок 
)
,
(
1
1
1
E
V
F =
 и 
)
,
(
2
2
2
E
V
F =
, 
1
1
m
V =
 и 
2
2
m
V
=
 

(
2
1
m
m >
), с упорядоченным возрастанием и сохранением смежности старых ре
бер 
распознается 
алгоритмом 
β  
с 
полиномиальной 
трудоемкостью 

)
(
L
L
V
L
E
O
+
. 

ДОКАЗАТЕЛЬСТВО разделим на две части. В первой будет доказано соответст
вия выполняемой алгоритмом β  работы заявленным целям, т.е. распознаванию 

предфрактального графа 
)
,
(
L
L
L
E
V
G
=
, порожденного парой полных затравок 

)
,
(
1
1
1
E
V
F =
, 
)
,
(
2
2
2
E
V
F =
 с числом вершин 
1
m  и 
2
m  (
2
1
m
m <
) соответствен
но, с возрастанием и при сохранении смежности старых ребер. Во второй будет под
считана трудоемкость самого алгоритма β . 

I)При порождении предфрактального графа 
)
,
(
L
L
L
E
V
G
=
 парой полных 

затравок 
)
,
(
1
1
1
E
V
F =
 и 
)
,
(
2
2
2
E
V
F =
 с числом вершин 
1
m  и 
2
m  (
2
1
m
m <
) со
ответственно число вершин самого графа будет равно произведению с чередующи
мися множителями 
r
m
m
m
m
N
∗
∗
=
...
2
1
2
1
, где каждый множитель соответствует 

этапу порождения предфрактального графа. Формула 
r
m
m
m
m
N
∗
∗
=
...
2
1
2
1
по
зволяет вычислять число вершин предфрактального графа, порождаемого парой 

полных с упорядоченным возрастанием. А множитель r , если число этапов порож
дения нечетно, равен 
1
m . Если же число этапов порождения четно, то множитель r  

равен 1. Рассмотрим оба случая в отдельности. 

Пусть число этапов порождения предфрактального графа 
)
,
(
L
L
L
E
V
G
=
 не
четно, т.е. 
1
m
r =
. Это значит, что при порождении предфрактального графа 

)
,
(
L
L
L
E
V
G
=
 число его вершин будет равно 
1
2
1
)
(
)
(
m
m
m
G
N
M

L =
, а 

1
2
+
= M
L
. Кроме того это значит, что последней затравкой использованной для 

замещения вершин предфрактального графа 
)
,
(
1
1
1
−
−
− =
L
L
L
E
V
G
 является полный 

1
m -вершинный граф 
)
,
(
1
1
1
E
V
F =
. 

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

http://ej.kubagro.ru/2011/04/pdf/30.pdf

10

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

вершинами предфрактального графа предыдущего этапа. Это следует из общего 

описания процесса порождения предфрактального графа с сохранением смежности 

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

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

только степень этой вершины подграф-затравки будет отличаться от 
1
1 −
m
. 

Выделив на предфрактальном графе 
)
,
(
L
L
L
E
V
G
=
 все вершины степени 

1
1 −
m
 и объединив их в множество 
L
m
V
1 , можно сгруппировать их в подмножества 

исходя из взаимной смежности выделенных вершин. Эти подмножества представ
ляют собой (
1
1 −
m
) смежные вершины каждой новой подграф-затравки предфрак
тального графа 
)
,
(
L
L
L
E
V
G
=
. В каждом из сгруппированных подмножеств мно
жества 
L
m
V
1  не достает по одной вершине, чтобы каждое подмножеств соответство
вало множеству вершин отдельно взятой подграф-затравке. Для добавления этих 

подмножеств последними вершинами достаточно выделить все инцидентные вер
шинам подмножеств ребра, часть из которых (
1
1 −
m
 ребро) окажется инцидентны
ми недостающей вершине. 

После выделения все новые ребра стягиваются. На вход следующему этапу 

порождения подается предфрактальный граф 
)
,
(
1
1
1
−
−
− =
L
L
L
E
V
G
. 

Далее на каждом этапе распознавания чередуя проводиться выделение и стя
гивание новых подграф-затравок, соответствующих затравкам 
)
,
(
2
2
2
E
V
F =
 и 

)
,
(
1
1
1
E
V
F =
, по аналогии с описанным и обоснованным первым этапом распозна
вания алгоритма β . 

Пусть число этапов порождения предфрактального графа 
)
,
(
L
L
L
E
V
G
=
 

четно, т.е. 
1
=
r
. Это значит, что число замещений, учитывая чередующийся харак
тер процесса порождения, вершин затравкой 
)
,
(
1
1
1
E
V
F =
 и затравкой