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

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

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

Термин “сеть” широко распространен в современной научной и бизнес-литературе. На слуху такие выражения как “розничная или торговая сеть (сеть магазинов)”, “сетевой маркетинг”, “филиальная сеть”, “сеть трубопроводов”, “железнодорожная сеть”, “социальная сеть”, “компьютерная сеть”, “информационная сеть”, “телефонная сеть” и т.д. Не редко этот термин используется для обозначения совершенно различных понятий. В настоящем диссертационном исследование термин “сеть” понимается во-первых как совокупность путей доставки товаров или услуг до конечного получателя, а во вторых как совокупность связей между элементами многоэлементной системы. Системы, в основе функционирования которых лежит сеть, принято называть сетевыми системами [1].

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

Развивающаяся экономика и глобализационные процессы вынуждают сетевые системы развивать, адаптировать, оптимизировать свою сетевую структуру под сильно изменчивую конкурентную среду, и под новую геополитическую конъюнктуру. В такой ситуации в регулярных изменениях сетевых структур прослеживаются закономерности. Сетевые структуры не только теряют свою стационарность (фиксированность), но и приобретают признаки динамических систем. Сетевые структуры приобретают признаки и свойства иерархических и масштабно-инвариантных структур. Процессы изменения, развития, поведения сетевых структур можно объединить общим понятием “структурная динамика”. В системах с изменяющейся структурой целесообразно вести контроль над изменениями структуры для формирования спектра необходимых свойств и характеристик. Достижение этой цели лежит в русле решения задач структурного управления или управления структурной динамикой [2, 3].

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

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

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

Предфрактальный граф будем обозначать через , где множество вершин графа, а множество его ребер. Определим его рекуррентно, поэтапно, заменяя каждый раз в построенном на предыдущем этапе графе каждую его вершину связной затравкой . На первом этапе предфрактальному графу соответствует затравка. При этом об описанном процессе говорят, что предфрактальный граф порожден затравкой . Ребра, появившиеся на этапе , , порождения предфрактального графа, будем называть ребрами ранга . Новыми ребрами предфрактального графа назовем - ребра ранга , а все остальные ребра назовем старыми. Процесс построения предфрактального графа, по существу, есть процесс построения последовательности предфрактальных графов, которую и назовем траекторией. Фрактальный граф определяется бесконечной траекторией. Обобщением описанного процесса порождения предфрактального графа является такой случай, когда вместо единственной затравки используется множество затравок , . Суть этого обобщения состоит в том, что при переходе от графа к графу каждая вершина замещается некоторой затравкой , которая выбирается случайно или согласно определенному правилу, отражающему специфику моделируемого процесса или структуры. Если при переходе от графа к графу каждая вершина графа замещается одной конкретной случайно выбранной затравкой , то будем говорить, что предфрактальный граф порожден множеством затравок ,, , с чередованием. Если же при порождении предфрактального графа множеством затравок , , с чередованием задано некоторое правило выбора затравок из , например, неубывание числа вершин или ребер выбираемых затравок, то будем говорить, что предфрактальный граф порожден множеством затравок , , , с упорядоченным чередованием.

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

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

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

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

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

Доказательство. Рассмотрим траекторию предфрактального графа , порожденного множеством затравок , с упорядоченным возрастанием. На первом шаге порождения полная двухвершинная затравка из множества совпадает с первым элементом из траектории предфрактального, . Число вершин . Граф из траектории предфрактального графа порождается из графа замещением двух его вершин затравками , полными трехвершинными графами. Поэтому число вершин графа определяется как . В свою очередь, граф из траектории предфрактального графа порождается из графа замещением всех шести его вершин затравками , - полными четырехвершинными графами. А значит, число вершин графа определяется как

.

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

Теорема 2. Всякий предфрактальный граф , порожденный множеством затравок , , где -вершинный граф и , с чередованием имеет вершин.

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

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

ребер.

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

.

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

.

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

ребер.

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

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

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

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

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

Для мощности множества вершин существует пара и , таких, что

 и ;

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

.

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

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

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

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

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

Термином “R-адическое дерево” называем всякое дерево, у которого каждая невисячая вершина имеет степени , . С учетом практических приложений различают R-адическое дерево и корневое R-адическое дерево [5]. сетевой предфрактальный дерево полиномиальный

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

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

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

Если вершина не является висячей, то она не замещается затравкой;

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

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

Отметим, что в траектории ее начальный элемент представляет собой -вершинную звезду.

Естественным обобщением R-адического дерева является предфрактальное дерево, которое порождается в точном соответствии с описанными правилами 1) 3) с тем лишь отличием, что “незамороженная” висячая вершина замещается альтернативно некоторой звездой из заданного множества звезд . Полученное таким образом дерево принято называть термином “-дерево”. Распознавание -дерева сводится к простой визуализации, подробнее об этом можно узнать в работе [5].

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

Переход в траектории -дерева с чередованием затравок от текущего дерева к текущему дереву всякий раз подчиняется следующим правилам

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

II. Каждая висячая вершина замещается затравкой , выбранной случайным образом из множества затравок-звезд , а каждое висячее ребро становится инцидентным центру звезды ; в каждом переходе от графа к графу используется для замещения вершин только одна затравка и , причем каждая затравка используется (выбирается) в процессе порождения не менее одного раза;

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

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

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

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

На этапе , , сначала выделим все вершины дерева , смежные с висячими вершинами. Если каждая выделенная вершина дерева смежна с одинаковым числом висячих вершин, обозначим это число через , а степень самой вершины равна , то выделим все висячие ребра дерева . Затем в множество добавим ()-вершинную звезду, а все выделенные ребра дерева стянем. Полученное таким образом новое дерево предадим на вход следующего этапа.

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

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

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

Теорема 4. Всякое предфрактальное -дерево с чередованием затравок распознается алгоритмом с полиномиальной трудоемкостью .

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

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

II) На каждом из этапов распознавания алгоритм рассматривает каждое ребро дерева выделяет среди них висячие, т.е. окрашивает их или нет. Поэтому Трудоемкость каждого из этапов алгоритма равна . А поскольку алгоритм распознает предфрактальное -дерево с чередованием затравок за шагов, то вычислительная сложность или трудоемкость ограничивается полиномом .

Заключение

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

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

Литература

1. Малашенко Ю.Е., Новикова Н.М. Суперконкурентное распределение потоков в многопродуктовых сетях// Дискретный анализ и исследование операций. - Серия 2, 1997. Т. 4, № 2. - С. 34-54.

2. Охтилев М.Ю., Соколов Б.В., Юсупов Р.М. Интеллектуальные технологии мониторинга и управления структурной динамикой сложных технических объектов. - М.: Наука, 2006.

3. Кочкаров А.М., Кочкаров А.А., Никищенко С.П. Структурная динамика и исследование структурно-временных характеристик дискретных систем // Известия ТРТУ. Тематический выпуск “Перспективные системы и задачи управления”. - Таганрог: ТРТУ, 2006. - № 3. - С. 235_238.

4. Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. М.: Наука, 1990.

5. Кочкаров А.М. Распознавание фрактальных графов. Алгоритмический подход. Нижний Архыз: РАН САО, 1998.

Аннотация

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

Кочкаров Ахмат Магомедович

Доктор физико-математических наук, профессор

Хапаева Лёля Халисовна

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

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

Ключевые слова: СТРУКТУРНОЕ РАСПОЗНАВАНИЕ, СЕТЕВЫЕ СИСТЕМЫ, ИЕРАРХИЧЕСКИЕ СТРУКТУРЫ, ПРЕДФРАКТАЛЬНЫЕ ДЕРЕВЬЯ, ФРАКТАЛЬНЫЕ ГРАФЫ

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

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