автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Построение алгоритмов структурного распознавания в предфрактальных моделях сетевых систем

На правах рукописи

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

ПОСТРОЕНИЕ АЛГОРИТМОВ СТРУКТУРНОГО РАСПОЗНАВАНИЯ В ПРЕДФРАКТАЛЬНЫХ МОДЕЛЯХ СЕТЕВЫХ СИСТЕМ

05.13.18 - Математическое моделирование, численные методы и комплексы программ

- 3 НОЯ 2011

АВТОРЕФЕРАТ

диссертации на соискание учёной степени кандидата физико-математических наук

Ставрополь - 2011

4858750

Работа выполнена в ФГЪОУ ВПО «Северо-Кавказская государственная гуманитарно-технологическая академия» (Карачаево-Черкесская Республика, г. Черкесск)

Научный руководитель:

Официальные оппоненты:

Ведущая организация:

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

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

доктор технических наук, профессор

Винтизенко Игорь Георгиевич;

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

Наталуха Игорь Анатольевич

Южно-Российский государственный технический университет (г. Новочеркасск)

Защита состоится 18 ноября 2011 года в 14 часов 40 минут на заседании совета по защите докторских и кандидатских диссертаций Д 212.256.08 при ФГБОУ ВПО «Ставропольский государственный университет» по адресу:

355009, Россия, г. Ставрополь, ул. Пушкина, д. № 1, корп. 1а, ауд. 416.

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

Автореферат разослан «-/Лъ / г.

Учёный секретарь совета Д 212.256.08 по защите докторских и кандидатских диссертаций,

кандидат физико-математических наук, доцент

Копыткова Л.Б.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы исследования

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

Математиками «сеть» понимается как разновидность графа. Это множество элементов (вершин) системы (обязательно непустое), совокупность или множество отношений или связей (рёбер, дуг, петель, задаваемых кортежами длины два) между элементами или вершинами системы, трёхместный предикат или инцидентор, указывающий, какое ребро соединяет какую пару вершин, причём каждое ребро и/или каждая вершина могут быть отягощены некоторыми навешиваемыми скалярными характеристиками. Такими могут быть совокупности разных по интенсивности путей доставки товаров или услуг до конечного покупателя, длина пути, время движения по маршруту, пропускная способность газовой трубы, канала связи или электрического проводника, стоимость движения по участку платной автострады и т.д.

Системой в общем виде принято считать совокупность абстрактных и/или материальных объектов (элементов системы) с их известными внутренними свойствами (характеристиками) и заданными межобъектными отношениями (связями), образующими в известном смысле единой целое. Говорят, что это множество элементов, взаимосвязанных структурно и функционально, оно определено общей функцией, целью, назначением, входом и выходом. Системы, в основе функционирования которых лежат сетевые структуры, будем называть «сетевыми системами».

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

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

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

регулярных изменениях сетевых структур начинают прослеживаться закономерности. Сетевые структуры не только теряют свою стационарность (фиксированность), но и приобретают признаки динамических систем. Процессы развития и изменения сетевых структур можно объединить общим понятием «структурная динамика».

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

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

Соответствие темы диссертации требованиям паспорта специальности

Диссертация выполнена в соответствие с пунктами: 1 «Разработка новых математических методов моделирования объектов и явлений»; 3 «Разработка, обоснование и тестирование эффективных вычислительных методов с применением современных компьютерных технологий»; 6 «Разработка новых математических методов и алгоритмов проверки адекватности математических моделей объектов на основе данных натурного эксперимента»; 8 «Разработка систем компьютерного и имитационного моделирования» «Паспорта специальности 05.13. 18 - математическое моделирование, численные методы и комплексы программ (физико-математические науки)» ВАК Министерства образования и науки РФ.

Объектом исследования являются

структуры сложных сетевых динамических систем (социальные сети, компьютерные сети, трубопроводные сети, сети управления и пр.).

Предмет исследования составляют

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

Цель и задачи диссертационного исследования

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

Сформулированная цель диссертационного исследования потребовала решения следующих задач:

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

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

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

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

Методы исследования

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

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

Научная новизна диссертационного исследования состоит в следующем:

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

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

3 Спроектированы взаимно интегрированные алгоритмы распознавания пред-

фрактальных графов, порождённых множеством затравок с чередованием. Алгоритмы объединены в два блока. Первый блок состоит из алгоритмов распознавания предфрактальных деревьев, порождённых различными типами затравок-деревьев с чередованием и с вариациями условий сохранения смежности «старых» рёбер. Второй блок состоит из алгоритмов распознавания предфрактальных графов, порождённых различными типами регулярных затравок с чередованием, но с вариациями условия сохранения смежности «старых» рёбер. Все описанные алгоритмы обоснованы, подсчитана их вычислительная трудоёмкость, оказавшаяся полиномиальной. 4 Разработана архитектура и алгоритмы функционирования программной системы, не имеющей аналогов, изменяющей свою функциональную структуру при вариациях затравок, при вариации предложенных моделей и при вариации методов.

Теоретическая значимость и практическая ценность результатов исследования заключается в следующем:

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

Личный вклад соискателя

Все результаты диссертационного исследования получены автором самостоятельно.

На защиту выносятся следующие основные положения:

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

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

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

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

Апробация результатов исследования

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

• на Х11-ом научно-практическом семинаре «Новые информационные технологии в автоматизированных системах» (Москва, 2009);

• на Международной научной конференции «Проблемы регионального и муниципального управления» (Москва, 2009,2010);

• на 1У-ой Международной конференции «Управление развитием крупномасштабных систем» (Москва, 2010);

• на УП-ой Международной научной молодёжной школе «Высокопроизводительные вычислительные системы» (Таганрог, 2010);

• на Международной научно-технической конференции «Суперкомпьютерные технологии: разработка, программирование, применение (СКТ-2010)» (Таганрог, 2010);

• на Х1У-ом научно-практическом семинаре «Новые информационные технологии в автоматизированных системах» (Москва, 2011);

• на У1-ой Всероссийской научно-практической конференции «Перспективные системы и задачи управления» и Ш-ей Молодёжной школе-семинаре «Управление и обработка информации в технических системах» - «Управление 2011» (Таганрог, 2011);

• на Международной научно-практической конференции «Передовые информационные технологии, средства и системы автоматизации и их внедрение на российских предприятиях А1ТА-2011» (Москва, 2011);

• на научных семинарах профессорско-преподавательского состава Карачаево-Черкесской государственной технологической академии (Черкесск, 2002-2010);

• на научных семинарах Ставропольского государственного университета (Ставрополь, 2010);

• на научных семинарах филиала Южного федерального университета в г. Черкесске (Черкесск, 2008-2010).

Публикации

Основные результаты диссертационного исследования изложены в 14 опубликованных научных работах автора, в том числе 4 - в изданиях из Перечня ведущих рецензируемых научных журналов и изданий ВАК. Общий объём публикаций составляет 6.3 п.л., в том числе автора - 5.5 п.л. Структура и объём диссертации

Диссертация состоит из введения, трёх разделов, заключения, библиографического списка использованных материалов, приложения. Текст диссертации изложен на 121 странице, включает 11 рисунков, в том числе описание программного комплекса в приложении насчитывает 17 страниц. Список использованной литературы содержит 144 источника.

ОСНОВНОЕ СОДЕРЖАНИЕ ДИССЕРТАЦИОННОЙ РАБОТЫ

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

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

В первом разделе «Предфрактальные графы, порождённые с чередованием затравок и их свойства» определены понятия фрактального и предфракгального графов, порождаемых множеством затравок с процессом их чередования. Обосновано использование некоторого класса предфрактальных графов в качестве описательных моделей структурно-сложных систем. Произведён расчёт ряда числовых характеристик нового класса фрактальных и предфрактальных графов. Исследованы некоторые из наиболее интересных свойств этих графов.

Вербально разница между фрактальным и предфрактальным графом можно объяснить по аналогии с бесконечными и конечными графами. Фрактальный граф, как и бесконечный граф, имея некоторую фиксированную структуру, тем не менее, бесконечен, имеет бесконечно много вершин и рёбер. Практическое применение имеют предфрактальные графы, сохраняющие некоторую фиксированную структуру, но они конечны так же, как и конечные графы. Недаром первая российская монография по теории графов А. А. Зыкова подчёркивала конструктивность именно такого рода графов и называлась «Теория конечных графов».

Предфрактальный граф будем обозначать через С^ = (К^ где - множество вершин графа, а Е^— множество его рёбер. Определим его рекуррентно, поэтапно, заменяя каждый раз в построенном на предыдущем этапе / = {1,2,..Х — 1}графе б/ каждую его вершину связной затравкой Н = (}У,О). На первом этапе всему предфрактальному графу соответствует одна затравка. При этом об описанном процессе говорят, что предфрактальный граф =(Уь,Е1) порождён затравкой II = (IV, (3). Рёбра, появившиеся на этапе I, / = 1,2, порождения предфрактального графа, будем называть рёбрами ранга I. «Новыми» рёбрами предфракгального графа С/, назовем рёбра ранга Ь, а все остальные рёбра назовем «старыми». Процесс построения предфрактального графа, по существу, есть процесс построения последовательности предфрактальных графов, который и назовём траекторией. Фрактальный граф определяется бесконечной траекторией. Обобщением описанного процесса порождения предфрактального графа является такой случай, когда вместо единственной затравки Я используется множество затравок

Н = {#,} = {#1,#2,...,#,.....Нт), Т>2. Суть этого обобщения состоит в том, что

при переходе от графа С?;_1 к графу в; каждая вершина замещается некоторой затравкой Н, е Н, которая выбирается случайно или согласно определённому правилу, отражающему специфику моделируемого процесса или структуры.

Я, Н2 Нз

Рисунок 1 - Траектория предфрактального графа

Если при переходе от графа к графу б, каждая вершина графа б,., замещается конкретной случайно выбранной затравкой Н,* е Н, то говорят, что предфрактальный граф порождён множеством затравок Н = {#,},( = 1,2,...,Г, Т >2 с чередованием. Если при порождении предфрактального графа множеством затравок Н = {Н,}, Т > 2 с чередованием задано некое правило выбора затравок из Н, например, правило не убывания числа вершин или рёбер выбираемых затравок, то будем говорить, что предфрактальный граф Оь порождён множеством затравок Н = {Н,}, / = 1,2,...,7\ Т>2,с упорядоченным чередованием (рис. 1).

Очевидно, что порождение фрактального графа О = (У,Е) (порождающая траектория которого является бесконечным множеством с чередованием затравок возможно только при бесконечном числе замещений затравок Н = {#,}, I = 1,2,...,Т, Т> 2.

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

В случае порождения предфрактального графа с упорядоченным возрастанием (с упорядоченным убыванием) затравок Н = {#г}, / = 1,2,...,7", Т> 2, если 1>Т, то переход на 1 = Т +1 шаге порождения от предфрактального графа О-р к графу С7+1 осуществляется заменой всех вершин графа Ор затравкой с наименьшим (наибольшим) числом вершин из Н = {Н,}, ? = 1,2,...,Г, Т > 2. На последующих шагах / = Г+2,Г+3,...,1 порождения предфрактального графа затравки из Н = {#,}, ( = 1,2,...,Т, Т> 2 используются последовательно в соответствие с очерёдностью возрастания (убывания) числа вершин.

В случае порождения предфрактального графа , когда число этапов порождения больше числа затравок, Ь > Т, целесообразно говорить о периоде замещения вершин затравками. Период замещения вершин затравками в процессе порождения предфрактального графа 01 с возрастанием или убыванием вершин затравок Н = {#,}, / = 1,2,...,7\ Т > 2 обозначим через Р.

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

Одними из первичных характеристик предфрактальных графов являются числа их вершин и рёбер. Теоремы 1.3 и 1.4 и их следствия определяют число вершин предфрактальных графов, порождаемых процессами с чередованием затравок различных классов и типов.

Теорема 1.3 Всякий предфрактальный граф порождённый множеством затравок Н = {Я,}, / = 2,3,...,Г с чередованием, где Я, - /-вершинный граф и I - Т -1, имеет N{01) = Т! вершин.

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

Следствие 1.3.1 Всякий предфрактальный граф порождённый множеством затравок-циклов Н = {Я,}, (= 3,...,Г с чередованием, где Н, - /-вершинный граф и Ь = Т- 2, имеет iV(G¿) = ТУ 2 вершин.

Следствие 1.3.2 Всякий предфрактальный граф Сь, порождённый множеством затравок-цепей Н = {//,}, / = 2,3,...,Г с чередованием, где Н1 - /-вершинный граф и Ь = Т-1, имеет = вершин.

Следствие 1.3.3 Всякий предфрактальный граф порождённый множеством затравок-звёзд Н = {#(}, ¿ = 3,...,Г с чередованием, где Я, - ¡-вершинный граф и Ь = Т-2,имеет Лг(0£) = Л/2 вершин.

Следствие 1.3.4 Всякий предфрактальный граф Сь, порожденный множеством затравок-деревьев Н = {Н,}, / = 2,3,...,Г с чередованием, где Я, вершинный граф и Ь = Т-\, имеет ) = Т\ вершин.

Теорема 1.4 Всякий предфрактальный граф , порождённый множеством затравок Н = {Н,}, / = 2,3,...,7", где Я, - вершинный граф с упорядоченным возрастанием или убыванием числа вершин затравок и полным периодом замещения вершин затравками Ь = Р(Т -1), имеет Л'^) = (Т\)р вершин.

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

Следствие 1.4.1 Всякий предфрактальный граф порождённый множеством полных затравок Н = {Я,}, / = 2,3,...,Г, где Н1 - ¡-вершинный граф с упорядоченным возрастанием или убыванием числа вершин затравок и полным периодом

р

замещения вершин затравками Ь = Р('Г -1), имеет N{0^) = (Л) вершин.

Следствие 1.4.2 Всякий предфрактальный граф порождённый множеством затравок-циклов Н = {Н1), / = 3,...,Т, где Н, - /-вершинный граф с упорядоченным возрастанием или убыванием числа вершин затравок и полным периодом за-

р

мещения вершин затравками Ь = Р(Т - 2), имеет N(<31) = (Л/2) вершин.

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

Теорема 1.5 Всякий предфрактальный граф й/ , порождённый множеством полных затравок Н = {Я<}> / = 2,3,...,7\ где Я, - I-вершинный граф и Ь = Т-1

с упорядоченным возрастанием, имеет 0^1)-1+ £-^-рёбер.

1=1 2 ■

Следствие 1.5.1 Всякий предфрактальный граф порождённый множеством затравок-циклов Н = {Н,}, / = 3,4,...,Т, где Я, - ¡-вершинный граф и 1 = Г-2

с упорядоченным возрастанием, имеет <2(0£) = 3 + + 0 + 2) Рё^еР-

1 = 2 2

Следствие 1.5.2 Всякий предфрактальный граф порождённый множеством затравок-деревьев Н = {Н,}, / = 2,3,4,...,Т, где Н1 - /-вершинный граф и

Т-2

1-7 -1 с упорядоченным возрастанием, имеет <2{й1) = 1 + £ (/ +1)!(/ +1) рёбер.

1=1

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

Теорема 1.9 Всякий предфрактальный граф порождённый множеством полных затравок Н = {#,}, / = 2,3,...,7\ где Н, - ¡-вершинный граф с чередованием при сохранении смежности «старых» рёбер, имеет диаметр ) = 2Ь-\.

Следствие 1.9.1 Всякий предфрактальный граф порождённый множеством полных затравок Н = {II1}, / = 2,3,...,Т, где Н( - /-вершинный граф с чередованием при сохранении смежности «старых» рёбер, имеет радиус ) = I.

Теорема 1.10 Всякий предфрактальный граф порождённый множеством затравок-звёзд Н = {#,}, / = 3,...,Г, где Н, - /-вершинная звезда с чередованием при сохранении смежности «старых» рёбер, имеет диаметр ¿(О^ = 2Ь. А

Следствие 1.10.1 Всякий предфрактальный граф Оь, порождённый множеством затравок-звёзд Н = {Н,}, / = 3,...,Г, где Я, - ¡-вершинная звезда с чередованием при сохранении смежности «старых» рёбер, имеет радиус г(С^) = I. А

Ключевые оценки диаметра предфрактального графа, порождённого множеством затравок, даны в двух следующих теоремах:

Теорема 1.11 Для всякого предфрактального графа Оь, порождённого множеством полных затравок Н = {//,}, / = 2,3,...,Г, где Я, - /-вершинный граф с чередованием, верно неравенство ¿/(0^) > 2£ -1. А

Теорема 1.12 Для всякого предфрактального графа порождённого множеством затравок Н = {//,}, / =2,3,...,Г с чередованием верно неравенство 21-1. <

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

Лемма 1.13 Для всякого предфрактального графа порождённого множеством полных затравок Н = {н,}. / = 2,3,...,Г, где Н, - ¡-вершинный граф с чередованием при сохранении смежности «старых» рёбер, верно неравенство тахс!<Ь{Т-\), где тахс\egGi - наибольшая степень среди всех степеней

вершин предфрактального графа 0£.

Следствие 1.13.1 Для всякого предфрактального графа порождённого множеством полных затравок Н = {#,}, / = 2,3,...,Т, где Я, - /-вершинный граф с чередованием, верно неравенство тахс^С/, <Ь(Т-1), где maxdegG¿ - наибольшая степень среди всех степеней вершин предфрактального графа (?£. Ч

Следствие 1.13.2 Для всякого предфрактального графа порождённого множеством затравок Н = {#,}, / = 2,3,...,Г, где Н1 - ^вершинный граф с чередованием, верно неравенство шах <ЦТ-1), где шaxdegG¿ - наибольшая степень среди всех степеней вершин предфрактального графа <

Следствие 1.13.3 Для всякого предфрактального графа порождённого множеством затравок Н = {#,}, / = 2,3.....Г, где Н( - /-вершинный граф с чередованием при сохранении смежности «старых» рёбер, верно неравенство тах(^(/£ <Ь(Т-1), где тах - наибольшая степень среди всех степеней вершин предфрактального графа .

Комплекс взаимосвязанных программ (в приложении к диссертации) по этим теоремам и следствиям через серию алгоритмов а определяет число вершин предфрактального графа, число рёбер, диаметр и радиус предфрактального графа, степени вершин и наибольшую степень вершины предфрактального графа в соответствии с теоремой 1.3, следствиями 1.3.1-1.3.4; теоремой 1.4, следствиями 1.4.1-1.4.4; теоремой 1.5, следствиями 1.5.1-1.5.4; теоремой 1.9, следствием 1.9.1; теоремой 1.10, следствием 1.10.1; теоремами 1.11 и 1.12; леммой 1.13 со следствиями 1.13.1-1.13.3.

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

12 3 4

Первая серия алгоритмов а\ состоит из четырех алгоритмов а\, а\ , а^, а\ , которые позволяют распознавать предфрактальные деревья, порождённые множеством затравок-звёзд с чередованием при различных вариациях операции замены вершин затравками.

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

Алгоритмом «I2 выполняется распознавание Н-дерева с упорядоченным чередованием затравок-звёзд.

Алгоритм позволяет распознавать предфрактальные деревья, порождённые множеством затравок-звёзд с чередованием в соответствии со «стандартным правилом» порождения предфрактального графа. Алгоритм а^ настроен на распознавание предфрактальных деревьев, порождённых множеством затравок-звёзд с произвольным чередованием при сохранении смежности «старых» рёбер.

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

3 12

так и алгоритм а1 принципиально отличаются от алгоритмов а.\ и а{, которые позволяют распознавать только Н -деревья.

Теорема2.1 Всякое предфракталъное Н-дерево с чередованием

затравок распознаётся алгоритмом с полиномиальной трудоёмкостью О^Е^Ь).

Следствие 2.1.1 Всякое предфракталъное Л-дерево с упорядо-

ченным чередованием (возрастанием или убыванием числа вершин) затравок распознаётся алгоритмом а\ с полиномиальной трудоёмкостью 0(\Е^Ь).

Теорема 2.2 Всякое предфракталъное дерево с чередованием

затравок и сохранением смежности «старых» рёбер распознаётся алгоритмом а^ с полиномиальной трудоёмкостью О^Е^Ь).

Следствие2.2.1 Всякое предфракталъное дерево В^ = с чередовани-

ем затравок и сохранением смежности «старых» рёбер распознаётся алгоритмом а\ с полиномиальной трудоёмкостью О^Е^Ь).

Вторая серия алгоритмов этого раздела диссертации состоит только из одного алгоритма а^. Алгоритм «2 предложен для распознавания особого класса пред-

с

фрактальных Н -деревьев, порождаемый множеством затравок-звёзд с возрастанием, с исключением смежности «старых» рёбер, в том числе и различных рангов.

с

Теорема2.3 Всякое предфракталъное Н -дерево порождён-

ное с упорядоченным возрастанием числа вершин затравок без сохранения смежности «старых» рёбер, распознаётся алгоритмом а2 с полиномиальной трудоёмкостью О^Е^Ц.

1 9

Третья серия алгоритмов а3 (аз и <23 ) предназначена для распознавание предфрактальных деревьев, порождаемых парой затравок-цепей при сохранении смежности «старых» рёбер. Алгоритм «3 занимается распознаванием предфрактальных деревьев с упорядоченным возрастанием, алгоритм «3 предназначен для распознавания предфрактальных деревьев с упорядоченным убыванием.

Теорема 2.4 Всякое предфракталъное дерево £>£ = (У^, ££), порождённое парой цепей-затравок с упорядоченным возрастанием при сохранении смежности «старых» рёбер, распознаётся алгоритмом а\ с полиномиальной трудоёмкостью 0(\Е^Ь).

Следствие 2.4.1 Всякое предфракталъное дерево = ,£/,), порождённое парой цепей-затравок с упорядоченным убыванием при сохранении смежности «старьсс» рёбер, распознаётся алгоритмом сс$ с полиномиальной трудоёмкостью О^Е^Е).

В соответствие с теоремой 2.1 и следствием 2.1.1; теоремой 2.2 и следствием 2.2.1; теоремой 2.3 и теоремой 2.4 со следствием 2.4.1 комплекс компьютерных про-

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

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

Сначала определим предфрактальный С-граф, порождаемый множеством простых циклов-затравок С = {С} с чередованием.

Переход в порождающей траектории б},62,...,С,.,...,в/, С-графа с чередованием затравок от текущего графа Ог = {УГ,ЕГ) к текущему дереву йг+\ всякий раз подчиняется следующим правилам:

• если вершина V е Уг имеет степень, отличную от двух, то она не замещается затравкой;

• каждая вершина V е К,, степень которой равна двум, замещается затравкой С* еС, выбранной случайным образом из множества затравок-циклов С = {С), замещение производится «склеиванием» затравки С* е С с вершинам уе У/,

• в каждом переходе от графа йг к графу Ог+\ используется для замещения вершин только одна затравка из множества С = {С} и Ь>Т, где Т - число затравок в множестве С = {С}. Каждая затравка используется (выбирается) в процессе порождения не менее одного раза.

В процессе порождения по описанным правилам предфрактальный С-граф, очевидно, сохраняет смежность «старых» рёбер.

Распознавание предфрактального С-графа, порождённого множеством простых циклов-затравок С = {С} с чередованием и сохранением смежности «старых» рёбер, производит алгоритм Р), как это показано на рис. 2.

Теорема 3.1 Всякий предфрактальный С-граф С^ порождённый

упорядоченным чередованием затравок-циклов с сохранением смежности «старых» рёбер, распознаётся алгоритмом Д с полиномиальной трудоёмкостью О^Е^Ь).

Алгоритм Д распознавания предфрактального С-графа создаёт предпосылки для конструирования алгоритма распознавания предфрактального N-графа =(У1,Е1), порождаемого множеством регулярных затравок N = {Щ степени п с упорядоченным чередованием (возрастанием или убыванием числа вершин) затравок и сохранением смежности «старых» рёбер. Ключевое отличие процесса порождения N-графа алгоритмом от процесса порождения С-графа алгоритмом 01 состоит в замещении затравками вершин степени п.

Теорема 3,2 Всякий предфрактальный N -граф = (У^, Е1) с упорядоченным чередованием регулярных затравок и сохранением смежности «старых» рёбер распознаётся алгоритмом /?2 с полиномиальной трудоёмкостью О^Е^Ь).

Рисунок 2 - Траектория предфрактального С-графа, порождённого множеством простых циклов-затравок С = {С} с упорядоченным возрастанием числа вершин-затравок и сохранением смежности «старых» рёбер

Распознавание предфрактального графа в/, порождённого парой

полных затравок =(У\,Е\) и Р^ =(Уг^2) с числом вершин щ и т2 (/щ <) соответственно, с возрастанием и при сохранении смежности «старых» рёбер, можно осуществить алгоритмом /?з. Суть алгоритма /З3 заключается в идентификации графов ^=(^,£1), как затравок предфрактального графа

G¿ = (VI,Еь) и его траектории порождения.

Теорема 3.3 Всякий предфрактальный граф йь = (К^,^), порождённый парой полных затравок Гу =(У\,Е\) и =(^2>-^2)> = и =от2 (да1 >от2)> с упорядоченным возрастанием и сохранением смежности «старых» рёбер, распознается алгоритмом /?з с полиномиальной трудоёмкостью

Как и ранее, работа программного комплекса начинается с вычислительной реализации алгоритмов, основанных на доказанных теоремах 3.1-3.3 о распознавании разных типов предфрактальных графов с полиномиальной трудоёмкостью. Одной из задач созданного комплекса программ стала визуализация результатов диссертационных построений.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ, ПОЛУЧЕННЫЕ В ДИССЕРТАЦИОННОМ ИССЛЕДОВАНИИ

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

2 Подсчитаны основные числовые характеристики предфрактальных графов, порождённых с чередованием затравок, в частности, число вершин и число рёбер.

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

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

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

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

ПО ТЕМЕ ДИССЕРТАЦИИ ОПУБЛИКОВАНЫ СЛЕДУЮЩИЕ РАБОТЫ

Публикации в ведущих рецензируемых журналах и изданиях, определённых ВАК

1 Хапаева Л.Х. Распознавание предфрактального графа, порождаемого двумя полными затравками // Политематический сетевой электронный научный журнал Кубанского государственного аграрного университета [Электронный ресурс]. -Краснодар: КубГАУ, - 2011. - № 5 (69). Режим доступа: http://ei.kubagro.ru/201 l/69/pdf/05/pdf 0.8 пл.

2 Кочкаров A.M., Хапаева Л.Х. Структурное распознавание предфрактальных деревьев с множеством затравок // Политематический сетевой электронный научный журнал Кубанского государственного аграрного университета [Электронный ресурс]. - Краснодар: КубГАУ, - 2011. - № 6 (70). Режим доступа: http://ej.kubagro.ru/2010/12/pdf/08/pdf 0.8 пл., в т.ч. автора 0.7 пл.

3 Кочкаров A.A., Хапаева Л.Х. Алгоритм распознавания предфрактального графа с чередованием затравок// Научно-технические ведомости Санкт-Петербургского государственного политехнического университета. Информатика. Телекоммуникации. Управление. - 2010. - № 3(101). - С. 134-140. 0.45 пл., в т.ч. автора 0.4 пл.

4 Кочкаров A.A., Салпагарова А.Р., Хапаева Л.Х. Стойкость технических систем: моделирование распространения внешних воздействий по структуре сложной системы // Известия Южного федерального университета. Технические науки. - 2009. -№ 5(94). - С. 228-234.0.45 пл., в т.ч. автора 0.4 п.л.

Публикации в других изданиях

5 Кочкаров А.Л., Хапаева Л.Х., Сенникова Л.И. Особенности структурного распознавания сложных сетевых систем // Труды Международной научно-практической конференции «Передовые информационные технологии, средства и системы автоматизации и их внедрение на российских предприятиях AITA-2011». - М.: Издательство Института проблем управления имени В.А. Трапезникова РАН, 2011. - С. 670680.0.7 пл., в т.ч. автора 0.65 п.л.

6 Аров М. О., Хапаева Л.Х. Распознавание предфрактального графа, порождённого множеством полных затравок с чередованием и сохранением смежности «старых» рёбер // Сборник материалов VI-ой Всероссийской научно-практической конференции «Перспективные системы и задачи управления» и Ш-ей Молодёжной школы-семинара «Управление и обработка информации в технических системах» -«Управление 2011». - Таганрог: Издательство Таганрогского технологического института Южного федерального университета, 2011. - С. 264-266. 0.2 пл., в т.ч. автора 0.15 пл.

7 Хапаева Л.Х., Сенникова Л.И., Кочкаров A.A. Структурное распознавание сложных сетевых систем // Сборник материалов VI-ой Всероссийской научно-практической конференции «Перспективные системы и задачи управления» и Ш-ей молодёжной школы-семинара «Управление и обработка информации в технических системах» - «Управление 2011». - Таганрог: Издательство Таганрогского техноло-

гического института Южного федерального университета, 2011. - С. 321-330. 0.7 пл., в т.ч. автора 0.6 п.л.

8 Сенныкова ЛИ., Хапаева J1.X., Кочкаров A.A. Структурное распознавание необратимо развивающихся сетевых систем И Материалы XIV-го Научно-практического семинара «Новые информационные технологии в автоматизированных системах». - М.: Издательство Московского государственного института электроники и математики, 2011.-С. 154-166.0.8 п.л., в т.ч. автора 0.7 пл.

9 Кочкаров A.A., ХапаеваЛ.Х„ Салпагарова А.Р. Параллельные алгоритмы поиска решений оптимизационных задач на масштабно-инвариантных графах большой размерности II Материалы Международной научно-технической конференции «Суперкомпьютерные технологии: разработка, программирование, применение (СКТ-2010)». Том 1. - Таганрог: Издательство Таганрогского технологического института Южного федерального университета, 2010. - С. 261-265. 0.3 пл., в т.ч. автора 0.25 п.л.

10 Кочкаров A.A., Хапаева Л.Х., Салпагарова А.Р. Параллельные алгоритмы поиска решений оптимизационных задач на масштабно-инвариантных графах большой размерности // Материалы VII-ой Международной научной молодёжной школы «Высокопроизводительные вычислительные системы». - Таганрог: Издательство Таганрогского технологического института Южного федерального университета, 2010. - С. 221-225.0.3 пл., в т.ч. автора 0.25 пл.

11 Кочкаров A.A., Сомов Д.С., ХапаеваЛ.Х. Исследование просачиваемости сложных сетевых систем методами теории графов// Материалы Международной научной конференции «Проблемы регионального и муниципального управления». -М.: РГГУ, 2010. - С. 29-32.0.25 пл., в т.ч. автора 0.2 пл.

12 Хапает Л.Х., Кочкаров A.A., Салпагарова А.Р. Применение масштабно-инвариантных графов в моделировании сложных многоэлементных систем // Материалы IV-ой Международной конференции «Управление развитием крупномасштабных систем». Том I. - М.: Издательство Института проблем управления имени В.А. Трапезникова РАН, 2010. - С. 331-333. 0.2 пл., в т.ч. автора 0.15 пл.

13 Кочкаров A.A., ХапаеваЛ.Х, Салпагарова А.Р., Болуров H.H. Структурная организация сетевых систем // Материалы ХИ-го Научно-практического семинара «Новые информационные технологии в автоматизированных системах». - М.: Издательство Московского государственного института электроники и математики, 2009. -С. 74-75.0.15 пл., в т.ч. автора 0.1 пл.

14 Кочкаров A.A., ХапаеваЛ.Х. Структурная организация сетевых систем: моделирование и методы исследования // Материалы Международной научной конференции «Проблемы регионального и муниципального управления». - М.: РГГУ, 2009. - С. 237-239.0.2 пл., в т.ч. автора 0.15 пл.

Подписано в печать 30.09.2011. Формат 60x84/16. Бумага офсетная. Печать офсетная. Усл. печ. л. 1,0. Заказ 0664. Тираж 100 экз.

Издательство ФГБОУ ВПО «СКГТТА» 369000, КЧР, г. Черкесск, ул. Ставропольская, д. 36

ВВЕДЕНИЕ.'.

1 ПРЕДФРАКТАЛЬНЫЕ ГРАФЫ, ПОРОЖДЁННЫЕ С ЧЕРЕДОВАНИЕМ ЗАТРАВОК, И ИХ СВОЙСТВА.

1.1 Фрактальные графы, порождённые множеством затравок с чередованием.

1.2 Свойства предфрактального графа; порождённого множеством затравок с чередованием.

1.2.1 Число вершин предфрактального.графа, порождённого множеством затравок с чередованием. )..

1.2.2 Число рёбер предфрактального графа, порождённого с чередованием'затравок.;.

1.3- ' Выводы;.-• •—г-:-; ■ ------- - - .40;

2 РАСПОЗНАВАНИЕ ПРЕДФРАКТАЛЬНЫХ ДЕРЕВЬЕВ, ПОРОЖДЁННЫХ С ЧЕРЕДОВАНИЕМ ЗАТРАВОК.:.

2.1 Признаки предфрактальных графов, порождённых с чередованием затравок.'.

2.2 Распознавание предфрактального графа, порождённого множеством затравок-звёзд с чередованием при сохранении смежности «старых» рёбер.

2.3 Распознавание предфрактального графа, порождённого множеством затравок-звёзд с чередованием при непересекающихся «старых» рёбрах.'.5.

2.4 Распознавание предфрактальных деревьев, порождённых парой затравок-цепей с чередованием.

2.5 Выводы.'.'.

3 РАСПОЗНАВАНИЕ ПРЕДФРАКТАЛЬНЫХ ГРАФОВ, ПОРОЖДЁННЫХ РЕГУЛЯРНЫМИ ЗАТРАВКАМИ

С ЧЕРЕДОВАНИЕМ. У.

3.1 Распознавание предфрактального графа, порояедённого множеством затравок-циклов с чередованием при сохранении смежности «старых» рёбер:.

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

3.3 Распознавание предфрактального графа, порождённого парой полных затравок с чередованием при сохранении смежности «старых» рёбер •.

3.4 Выводы:;.1 і і .'•. і-.-.-. л іуЛ'.-.Ч

Определим прежде всего модели структурно-сложньис систем и отображающую их структурную динамику. Представление структуры системы (технической, социально-экономической, управления и т.д.) в виде графа — общепризнанный подход-при визуальном и модельном представлении связей между элементами системы [91]. Структура системы в зависимости от моделируемого процесса или явления может оставаться стационарной или претерпевать определенные регулярные изменения. В первом случае речь идет о динамических системах [104], [101], [93], [92]. Для учёных, использующих в моделировании динамических систем1 методы теории графов, ключевыми являются работы [93], [92]; [94],' [120]; [45].:Суть подхода, излагаемого в этих работах, заключается в следующем; Структура системы, взаимодействие элементов при функционировании системы представляется в виде ориентированного графа [92]; [120] .Каждой вершине и каждому ребру или каждой дуге графа присваиваются некоторые параметры и функционалы, адекватно описывающие процессы функционирования; исследуемой (моделируемой) системы. Начальное возмущение, приложенное к одной или группе вершин, распространяется по всему графу, изменяя параметры вершин. Меняется и величина самого импульса в соответствии с функционалами, присвоенными рёбрам или дугам графам Такой подход в моделировании динамических систем нашёл применение во многих областях.

Этот подход актуален и полезен в исследовании; социально-экономических систем (рис. 1.0а) [93], [92], [94], [120]] Моделирование социально-экономических систем посредством; операторных (функциональных) графов активно используется в научной школе профессора В-В; Кульбы.

Вызывает определённый интерес то, что идея описанного подхода нашла приложение в моделировании и исследовании! медико-биологических систем. В отличии от работ, выполняемых в научной школе профессора В.В. Кульбы, в работах представителей научной школы профессора А.П. Фаворского на графе структуры медико-биологической системы (большой и малый круги кровообращения человека, система сосудов головного мозга человека) решаются системы уравнений гемодинамики (рис. 1.0б) [19], [20]. Фактически, граф системы стал одновременно источником как начальных, так и краевых условий системы дифференциальных уравнений. а б

Рисунок 1.0 - Визуальное представление некоторых графовых моделей

Описанные модели объединены одной важной ограничительной особенностью. Структура моделируемых систем, представленных в виде графов на рис. 1.0а и 1.06, жёстко фиксирована.

Структурный синтез и организационные иерархии сложных систем и отображающих их графов. В проектировании сложных систем и синтезе структур теория графов становится незаменимым инструментом. Применение методов и подходов теории графов показало свою результативность в различных областях - от медицины и биологии до экономики и менеджмента [41], [137], [23], [95], [124], [97], [91], [131], [127], [25], [43], [30], [113], [129], [31], [40], [106], [125], [126], [116], [21], [90], [117], [138], [108], [121], [118].

Особое внимание стоит обратить на использование методов и подходов теории графов и дискретной математики в моделировании сложных многоэлементных систем. Задачи, которые возникли при исследовании таких многоэлементных систем, как электроэнергетические, социальные и информационные сети, сети управления дали существенный толчок для нового развития и применения идей теории графов и фрактальных графов [16], [17], [4], [5], [1], [13], [14], [11], [3], [8], [9], [10], [12], [18], [2], [6], [15].

Интересные результаты были получены при моделировании сложных иерархических систем самоподобными или фрактальными графами [85], [81], [122], [65], [66], [67], [68], [69], [70], [71], [72], [73], [83], [84], [86], [7], [82], [87], [27], [22], [28], [44], [114], [115], [123], [89], [26], [48], [49], [50], [51], [52], [60], [53], [54], [55], [56], [57], [58], [59], [61], [62], [63], [64], [35], [36], [33], [34], [74], [75], [76], [77], [78], [79], [80], [133]. Своим рождением фрактальные (предфрактальные) графы обязаны синтезу идей синергетики [134], [42], [135], [29], [103], [46], [96], [39], и нелинейной динамики [119], [47], [102], [24], [105], фракталов [130], [32], [128], [139], [132], [107], [99] и теории графов [9], [11], [18], [20], [21], [23], [25], [30], [31], [40], [41], [43], [91], [92], [95], [97], [106], [108], [113], [116], [117], [118], [124], [125], [126], [127], [129], [131], [137], [138]. , I ■

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

Актуальность темы исследования. Теперь пришло время обратиться к структурному распознаванию сетевых систем. Термин «сеть» широко распространён в современной научной и экономической литературе. На слуху такие выражения, как «розничная сеть», «железнодорожная сеть», «торговая сеть», «компьютерная сеть», «сеть магазинов», «сетевой маркетинг», «потоки в сетях», «филиальная сеть», «сеть трубопроводов», «социальная сеть», «информационная сеть», «телефонная сеть», «сеть Интернет» и т.д. Нередко этот термин остаётся инвариантным при обозначении совершенно различных понятий. Математиками «сеть» понимается как разновидность графа, это множество элементов (вершин) системы, совокупность или множество отношений или связей (рёбер, дуг, задаваемых кортежами длины два) между элементами или вершинами системы, причём каждое ребро и/или каждая вершина могут быть отягощены некоторыми навешиваемыми, скалярными характеристиками. Это могут быть, например,' совокупности разных по интенсивности путей доставки товаров- или услуг до конечного покупателя, длина ребра, время движения по ребру," пропускная; способность вершины, стоимость движения по ребру и [80], [97], [98],

99], [100], [112], [124]/- - ■■>

Системой в общем виде принято считать совокупность абстрактных и/или материальных объектов (элементов системы) с их известными внутренними свойствами (характеристиками) и заданными межобъектными отношениями (связями),- образующими в известном смысле единой целое. Говорят, что это множество элементов, взаимосвязанных структурно и функционально, оно определено общей функцией, целью, назначением, входом и выходом. Системы, в--основе ¡'функционирования которых лежат сетевые структуры, будемназывать! «се^вь^ [111], [112].

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

Однако глобализация и либерализация общественной жизни и мировой экономики, усложнение межгосударственных экономических отношений и связей, развитие инфотелекоммуникационных технологий, ускорение мировых процессов, обогащение их новыми составляющими — всё это приводит к экзогенному и эндогенному возмущению структуры изучаемого сигнала, делая его вариативным,- стохастичным, циклическим, нестационарным, сети разрастаются пространственно,' а сетевые взаимодействия усложняются. Развивающаяся экономика итлобализационные процессы в ней вынуждают сетевые системы развивать', адаптировать, оптимизировать свою структуру под сильно изменяющуюся1 конкурентную среду, под новую геополитическую конъюнктуру. В такой ситуации в регулярных изменениях сетевых структур начинают прослеживаться новые закономерности.

Это заставляет необходимо изучать мировые сетевые конъюнктуры новыми подходами, научными, сложными, интеллектуально-ёмкими, математическими и инструментальными. В основании же сложности и противоречивости всех мировых 'процессов лежит существенная недетерминированность, присущая самой*природе,'сетевая структура с её перманентной изменчивостью. В такой ситуации в регулярных изменениях сетевых структур начинают прослеживаться закономерности. Сетевые структуры не только теряют свою стационарность (фиксированность), но и приобретают признаки динамических систем,'признаки и-свойства иерархических и масштабно-инвариантных структур. Процессы развития, изменения, особенностей поведение сетевых структур можно объединить общим понятием «структурная динамика». ' 1

Исследования в области структурной динамики ведутся в научных школах профессора B.B. Кульбы [92], [93], [94], член-корреспондента РАН ДА. Новикова [111], [112], [37], [38], профессора A.M. Кочкарова [85], [81], [122], [65], [66], [67], [68], [69], [70], [71], [72], [73], [83], [84], [86], [7], [82], [87], [27], [22], [28], [44], [114], [115], [123], [89], [26], [48], [49], [50], [51], [52], [60], [53], [54], [55], [56], [57], [58], [59], [61], [62], [63], [64], [35], [36], [33], [34], [74], [75], [76], [77], [78], . [79], [80], [133] в таких научно-исследовательских институтах и ведущих вузах России, как Институт проблем управления имени В.А: Трапезникова РАН, Институт прикладной математики имени М.В. Келдыша РАН, Вычислительный центр имени A.A. Дородницына РАН, Северо-Кавказская государственная' гуманитарно-технологическая академия. ¡Работы/членов школ профессора В;В: Кульбы и член-корреспондента РАН Д.А. Новикова посвящены в большей степени задачам взаимодействия между элементами сложных иерархических систем, нежели задачам изменчивости и динамики 'самих сетевых структур- В работах же школы профессора A.M. Кочкарова первичное внимание уделено именно задачам изменчивости ? и динамики, поведения; и развития? самих сетевых структур. В качестве моделей' структурной динамики сетевых систем: в работах профессора A.M. Кочкарова предлагаются различные классы новых масштабно-инвариантных графов, называемых предфрактальными.

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

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

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

• адаптации предфрактальньк графов к.задачам моделирования: сетевых структур с корректирЬвкой основного правила порождения предфрактальных графов, приводящего к лучшей идемпотентности'графа и модели;

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

• проектирования взаимно интегрированных алгоритмов распознавания, адаптированных к моделированию сетевых структур прёдфрактальных графов; "'. ' ' ''-'"" '■'.' ' ' '. .'. "■ '"■■ '

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

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

Научная новизна' диссертационного исследования состоит в следующем: ■

1. Проведена адаптация (с изменением правил) процесса порождения • Гі і:'і.'і л 11 ¿'і ч . і; ■.'. предфрактальных графов к моделированию развивающихся сетевых структур, отличающаяся динамикой построений. Результатом адаптации стал новый класс предфрактальных графов, порождаемый множеством затравок с чередованием.:

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

3. Спроектированы взаимно' инте1рированнь1е алгоритмы распознавания предфрактальных графов, порождённых множеством! затравок с чередованием. Алгоритмы объединёны в два блока. Первый блок состоит из алгоритмов распознавания предфрактальных деревьев^ порождённых различными типами затравок-деревьев с "чередованием и с вариациями условий! сохранения - смежности «старых»- рёбер; Второй блок состоит из алгоритмов распознавания предфрактальных графов,' также порождённых: различными типами регулярных затравок с чередованием и с различными вариациями условия сохранения смежности «старых» рёбер. Все описанные алгоритмы обоснованы и имеют полиномиальную сложность.' ; " ; ;

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

Практическая ценность и теоретическая значимость результатов исследования заключается в том, что предложенный подход в динамическом моделировании развивающихся сетевых систем в виде предфрактальных графов, порождаемых множеством разных затравок, с чередованием, позволяет отслеживать и прогнозировать. возможные структурные изменения в таких сетевых системах, как электроэнергетической, системах водо- и теплоснабжения, в системах трубопроводного транспорта, информационной, социальной, в системах управления торговыми сетями и т.п. системах. Методика позволяет проектировать изменения структур сетевых систем в случае объективных изменений внешней для систем среды. Результаты диссертационного исследования, связанные с подсчётом в динамике числовых характеристик и выявлением новых свойств предфрактальных графов с чередованием, имеют теоретическую значимость. Они мо1уг вызвать интерес у специалистов по теории графов и структурной динамике для дальнейшего использования в научных обобщениях.' • 1 > • 1

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

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

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

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

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

I ' , , 1 I р ! ! I ! > < Л со

ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ ДИССЕРТАЦИОННОГО ИССЛЕДОВАНИЯ

1 Рассмотрены структурные особенности сетевых систем, получающие всё больший диапазон применений в науке, технике, управлении. К этим особенностям в первую очередь следует отнести способность сетей развиваться и «размножаться» своими разномасштабными самоподобными или фракталоподобными фрагментами (затравками).

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

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

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

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

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

7 Процесс порождения предфрактальных графов адаптирован для моделирования развивающихся динамических сетевых структур, что привело к появлению нового класса предфрактальных графов, порождаемых множеством затравок с чередованием. Определено понятие этой новой математичеСКОЙ КОНСТРУКЦИИ. »* ■ 1 ' ' : ' ''' у;

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

9 Найдена вычислительная трудоёмкость или «труднорешаемость» этих алгоритмов, во всех случаях она оказалась полиномиальной.

10 Разработана архитектура комплекса программ, состоящего из 23 блоков А-\¥, меняющего свой состав и функциональную структуру при вариациях в использовании алгоритмов функционирования программной системы в соответствии с предложенными в разных разделах диссертации моделями и методами. ■ 1 .

1. Albert R., BarabasiA. Statistical mechanics of complex networks // Reviews of Modern Physics. 2002. - № 74. - P. 47-97: .

2. Barlow M. T. Diffusions on fractals / Lectures on probability theory and statistics.-Berlin: Springer Verlág, 1998/-121 p^ ;.

3. BolltE.M., ben-Avraham D. What is Special about Diffusion on Scale-Free Nets? // New Journal of Physics. 2005. - V. 7. - № 26. P. 1-21.4 . Dorogovtsev S.N:, Mendes J.F.F. Evolution of networks // Adv. Physics. —2002.-№51.-P. 1079-1187.

4. DorogovtsevS.N.,: Mendes J.F.F. Evolution of networks: From Biological Nets to the Internet and WWW. Oxford: Oxford University Press, 2003.

5. Kigami J. Analysis on fractals / Volume l43 of Cambridge Tracts in Mathematics. — Cambridge:Cambridge University Press, 2001.

6. Kochkarov A., Perepelitsa V. Fractal Graphs and Their Properties // Berlin:1 1GM 1998 - International Congress of"Mathematicians: Abstracts of Short Communications■ and'Posters• -P. 347. . V, ' ' :

7. KronB. Greenfunctions- on^seltsimilár gr^hsf^idiboimds for the spectrum of the Laplacian // Ánnales Institution Fourier (Grenoble). — 2002. 52(6). — P. 1875-1900. ' ■li w'" ■ • "

8. Kron B. Growth of self-similar graphs // Journal of GraphTheory. 2004. -45(3) - P. 224-239: r v''

9. Kron Bl, Teüfl Éi 'Asymptoúcs} óf the" transition; probabilities of the simple random walk on self-similar graphs // Trató^tío^of^Ainerican- Máthematical Society. 2004;i- 356(1) — P; 393:-4l^^ ;; ; v ^

10. Lib., AldersonD;, TañakaR., Doyle J.C., Willihger W. Towards a Theory of Scale-Free Graphs: Definition, Properties and Implications (Extended Version)//Technical ELepórtCIT-CDS-04-006¿ Cal Tech; 2005.

11. Malozemov L., Teplyaev A. Pure point spectrum of the Laplacians on fractalgraphs//Journal of Functional Analysis. 1995. - 129(2). - P. 390-405.

12. RiehlJ., Hespanha J.P. Fractal graph optimization algorithms// Proceedings of the 44-th Conference on Decision and Control, 2005. P. 2188-2193.

13. Schulman L.S., Gaveau B. Complex systems under stochastic dynamics // Att. Fond. G. Ronchi, 2003. Volume LVIII. - № 805.

14. SongC., HavlinS., MakseH.A. Self-similarity of Complex Networks// Nature. 2005. - P. 433, 392-395.

15. StrogatzS. Exploring complex networks// Nature. — 2001. №410. — P. 268-276.

16. Watts D.J. Small Worlds. — Princeton: Princeton University Press, 1999.

17. Woess W. Random-wallcs-on-'infinite5graphs1 and groups/ Volume 138 of Cambridge Tracts in Mathematics. — Cambridge: Cambridge University Press, 2000. '

18. Абакумов M.B., Гаврипюк K.B., Есикова Н.Б., Кошелев В.Б., Лукшин А.В., Мухин С.И., Соснин Н.В., Тишкин В.Ф., Фаворский А.П. Математическая" модель гемодинамики сердечно-сосудистой^ системы // Дифференциальные уравнения J 1997. - 33(7): - С. 892-898.

19. Абакумов М.В., Есикова Н.Б., Мухин С.И., Соснин Н.В., Тишкин В.Ф Фаворский А.П. Разностная схема решения задач гемодинамики на графе. Препринт. М.: Издательство Диалог-МГУ; 1998.

20. Авондо-Бодино Дж. Применение в экономике теории графов. М.: Прогресс, 1966.

21. Асанов М.О., Баранский В.А., Расин В.В. Дискретная математика: графы, матроиды, алгоритмы. — Ижевск: Научно-исследовательский центр «Регулярная и хаотическая динамика», 2001.

22. Ахромеева Т.С., Курдюмов С.П., Малинецкий Г.Г., Самарский A.A. Нестационарные структуры и диффузионный хаос. — М.: Наука, 1992.

23. Басакер Р., Саати Т. Конечные графы и сети. — М.: Наука, 1974.

24. Батчаев ИЗ. Об одной многокритериальной задаче покрытия предфрак-тальных графов звёздами одного рангового типа // Известия Кабардино-Балкарского научного центра РАН. — 2002. Т. 8. - № 1. - С. 1—5.

25. Безручко Б.П., Короновский A.A., Трубецков Д.И., Храмов А.Е. Путь в синергетику. Экскурс в десяти лекциях. М.: Издательство КомКнига, 2005. !1 1 1 '

26. БержК. Теория графов и её применения. — М.: Издательство иностранной литературы, 1962.—320 с.

27. Березина Л.Ю. Графы и их применение. М.: Просвещение, 1979.

28. Божокин С.В., Паршин Д. А. Фракталы и мультифракталы. — Ижевск: Научно-исследовательский центр «Регулярная и хаотическая динамика», 2001.

29. Борлаков Х.Ш., Кочкарова П.А, Казалиева Л.Х Теория упорядочения твёрдых растворов с учётом перколяционных факторов. М.: ВИНИТИ, 2003. Депонировано в ВИНИТИ 12.03.2003г. - 11с.

30. Борлаков Х.Ш., Урусова П.А., Казалиева Л.Х. О предельной форме спектра масс в кинетической теории коагуляций: М.: ВИНИТИ, 2003. Депонировано в ВИНИТИ 12:03.2003г. - 6 с.

31. Бурков В Н., Кузнецов H.A., Новиков Д. А: Механизмы управления в сетевых структурах // Автоматика и телемеханика. 2002. - № 12. - С. 96—115. '' уг.^лл

32. Воронин A.A., Мишин С.П. Оптимальные иерархические структуры. М.: Институт проблем управления РАН, 2003. — 210 с.

33. Гленсдорф П., ПригоЫсин И. Термодинамическая теория: структуры устойчивости и флуктуаций. М.: Едиториал УРСС, 2003.

34. Дистелъ Р. Теория графов. Новосибирск: Издательство Института математики СО РАН, 2002.

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

36. Занг В.-Б. Синергетическая экономика. Время и перемены в нелинейной экономической теории. М.: Мир, 1999. \

37. Зыков A.A. Теория конечных графов. Том. 1. — Новосибирск: Наука, 1969.-.544с. '' ■ . ""', .

38. Касты Дж. Большие системы. Связность, сложность и катастрофы. М.: Мир, 1982. ■ ■ ■ :.• ' :•"■•/•

39. Князева E.H., Курдюмов С.П. Основания синергетики. Синергетическое мировидение. М.: Издательство КомКнига, 2005.

40. Компьютеры и нелинейные явления. Ш: Наука^ 19881

41. Коркмазова 3.О., Кочкаров Al А- ■ Эйлеровы предфрактальные графы // —. Таганрог: Известия ;Таганрогского государственного радиотехнического унжерситета\Спеіщ^шШв™ '•

42. Коркмазова 3.0. Многокритериальная задача разбиения на эйлеровые подграфы предфрактального графа. — Черкесск: Карачаево-Черкесская государственная технологическая академия, 2004. Депонировано в ВИНИТИ № 1729-В2004.-25 с. *

43. Коркмазова 3.0. Параллельный алгоритм вычисления задачи Эйлера на предфрактальных графах. — Черкесск: Карачаево-Черкесская государственная технологическая академия, 2004. Депонировано в ВИНИТИ №1730-В2004. 20 с.

44. Коркмазова 3.0. Выделение максимальных эйлеровых подграфов на предфрактальном' графе. — Черкесск: Карачаево-Черкесская государственная технологическая академия, 2004. Депонировано в ВИНИТИ №1731-В2004. -25 с.

45. Коркмазова З.О., Кочкаров P.A. Многокритериальная задача покрытия предфрактального графа эйлеровыми подграфами. Препринт Специальной астрофизической обсерватории (CAO) РАН №208. Нижний Ар-хыз: Издательство CAO РАН; 2005. - 15 с.

46. Коркмазова З.О., Кочкаров P.A. Многокритериальная задача покрытия предфрактального графа эйлеровыми подграфами. Препринт Специальной астрофизической обсерватории (CAO) РАН № 209. Нижний Ар-хыз: Издательство CAO ФАН, 2005. - 27 с.

47. Кочкаров A.A. Число'точек сочленения предфрактального графа // Материалы П-ой Международной конференции! «Нелокальные краевые задачи и родственные проблемы математической биологии, информатики и физики». Нальчик: Издательство НИИ ПМиА КБНЦ РАН, 2001.

48. Кочкаров А А. Плоские и иланарные предфракталыiые графы // Материалы V-ro Всероссийского симпозиума «Математическое моделирование и компьютерные технологии». Кисловодск: Кисловодский институт экономики и права, 2002. G. 35. : . •.;.'.': .'.-'.■

49. Кочкаров A.A., Кочкаров Р!А. Предфрактальные графы в проектировании и анализе сложных структур. Препринт № 10: — М.: Издательство Института прикладной'математики имени МЛЗ. Келдыша РАН, 2003 .

50. Кочкаров A.A., Кочкаров P.Ai О планарности и других топологических свойствах фрактальных графов. Препрйнт М 83; — М.: Издательство Института прикладной матёматики 'имени MiB; КелдышаРАН, 2003.

51. Кочкаров A.A., XanaeeaJJ.X. Структурная организация сетевых систем: моделирование и методы исследования // Материалы Международной научной конференции «Проблемы регионального и муниципального управления». М.: РГТУ, 2009. - С. 237-239.

52. Кочкаров A.A., Салпагарова А.Р., Хапаева JT.X. Стойкость технических систем: моделирование распространения внешних воздействий по структуре сложной системы // Известия Южного федерального университета. Технические науки. 2009. - № 5(94). - С. 228-234.

53. Кочкаров A.A., Сомов Д. С., Хапаева JI.X. Исследование просачиваемо-сти сложных сетевых систем методами теории графов // Материалы Международной научной конференции «Проблемы регионального и муниципального управления». М.: РГТУ, 2010. - С. 29-32.

54. Кочкарое A.M., Перепелица В.А., Сергеева JI.H. Фрактальные графы и их размерность. Черкесск: Карачаево-Черкесский государственный технологический институт, 1996. Депонировано в ВИНИТИ № 3284-В96. —34 с.

55. Кочкарое A.M. Хроматическое число й хроматическийиндекс фрактальных графов // Материалы Республиганской конференции преподавателей и аспирантов КЧТИ; Черкесск: Издательство Карачаево-Черкесского технологического института,1997. — С.56^

56. Кочкарое A.M. Топологические характеристики теоретико-графовой модели крупномасштабной кластеризации . материи во Вселенной. Препринт Специальнойастрофизическойобсерватории(САО) РАН. Ниж- . ний Архыз: Издательство CAO РАН, 1998.- С. 1-6.

57. Кочкарое A.M. Распознаваний фрактальных графов. Алгоритмический подход. Нижний Архыз; Издательство Специальной астрофизической обсерватории (CAO) РАН, 1998. - 170 с. ! . ; :

58. Кочкарое A.M., Перепелица BÍA. Число внутренней устойчивости предфрак-тапьного и фрактального графа.1 Сборник статей. — Нижний Архыз: Издательство Специальной астрофизической обсерватории (CAO) РАН,' 1999.

59. Кочкарое P.A., Салпагаров С.И. Полиномиальные быстрые алгоритмы нахождения остовного дерева минимального веса. — Черкесск: Карачаево-Черкесская государственная технологическая академия, 2002. Депонировано в ВИНИТИ, № 437-В2002. 75 с.

60. Кочкарое P.A., Кочкарое A.A. Формализация целевых программ // Модели экономических' 'систем И' информационные технологии: Сборник научных трудов / Под редакцией О.В. Голосова. Выпуск ХП-ый. -М.: Финансовая академия, 2004.

61. Кристофидес Н. Теория графов. Алгоритмический подход. — М.: Мир, 1978.-432 с.

62. КулъбаВ.В., Назаретов В.М., ЧухровИ.П. Модифицированные функциональные графы как аппарат моделирования сложных динамических систем. Препринт ИПУ РАН. М.: Издательство Института проблем управления РАН, 1'995. '

63. КулъбаВ.В., КононовД.А., Косяченко C.Ä., Шубин А.Н. Методы формирования сценариев развития социально-экономических систем. М.: СИНТЕГ, 2004. '

64. КулъбаВ.В., Ковалевский С.С., Уткин В.А. и др. Управление и контроль реализации социально-экономических целевых программ. М.: Книжiный дом «Либриком», 2009.

65. Ловас Л., Пламмер М. Прикладные задачи теории графов. Теория паро-сочетаний в математике, физике, химии. М.: Мир, 1998.1 \ V 1 5 »t ' ■

66. Лоскутов A JO., Михайлов A.C. Введение в синергетику. — М.: Наука, 1990: '

67. Майника Э. Алгоритмы оптимизации на графах и сетях. — М.: Мир, 1981.100 • Малашенко Ю.Е., Новикова II. М. Многокритериальный и максиминныйанализ многопродуктовых сетей. — М!: ВЦ АН СССР, 1988.

68. МалинецкийГ.Г., Потапов А.Б. Современные проблемы нелинейной динамики. М.: Эдиториал УРСС, 2000.

69. Малинецкий Г.Г., Курдюмов С.П. Нелинейная ? динамика щ проблемы прогнозаУ/Вестник РАН; 2001. - Том 7К - № 3. - С. 210-224.

70. Малинецкий Г.ГМатематические основы синёргетикш Хаос, структуры; вычислительный эксперимент. — М.: Издательство КомКнига, 2005:106? МстинецкийШ.Г., Потапов AlÉi Нелинейная' динамиками хаос: Основные понятия; — М.: Шдательство КомКнига; 2006^

71. Манделъброт Б.Фрактальная гёометрия природы.—М;: ИКИ; 2002.

72. Мелихов А.И:, Бернштейн Л.С., Курейчйк В.М. Применение графов для проектирования дйс^етных;устройств. М.: Наука, 1974. — 304 с.

73. Мелроуз Дж. Иерархичёские фрактальные графы и блуждания на них // Фракталы в- физике/ Под редакцией Л Пъетронеро, Э: Тозатти. — М.:

74. Млр,1988. -с! 519^523:; :'"'"'■''■. :v^V/ ^ /' \

75. Миркин Б.Г., Родин G.H: Графы и гены: — Mí: Наука; 1977.

76. Новикова Н:М:, Поспелова ШШ Многокритериальные задачи; принятия решений в условиях неопределённости.;. — М.: Вычислительный центр РАН, 2000;

77. Новиков Д. А. Механизмы функционирования многоуровневых организационных систем. М.: Фонд «Проблемы управления», 1999. - 150 с.

78. Новиков Д. А., Цветков A.B. Механизмы стимулирования в многоэлементных организационных системах. М.: Апостроф, 2000 — 184 с.

79. Новиков ДА. Сетевые структуры и организационные системы. М.: Институт проблем управленияРАН, 2003. — 102 с.

80. Оре О. Теория графов. М.: Наука, 1968.

81. Павлов ДА. Нахождение диаметральной простой цепи на фрактальном и предфрактальном графах // Материалы XVT-ой Международной научной конференции «Математические методы в технике и технологиях — ММТТ-16». Сборник трудов. СПб: Издательство СПбГТИ, 2004.

82. Применение теории графов связи в технике / Под редакцией Д. Кернопа, Р. Розенберга. — М.: Мир, 1974.

83. Применение теории графов в химии / Под редакцией Н.С. Зефирова, С.И. Кучанова. — Новосибирск: Наука, 1988.

84. Райнике К, Ушаков H.A. Оценка надёжности систем с использованием графов. -М.: Радио и. связь, 1988.

85. Режимы с обострением. Эволюция'идеи: законы коэволюции сложных структур. М.: Наука, 1998. '

86. Роберте Ф.С. Дискретные математические модели с приложениями к социальным, биологическим и экологическим задачам. — М.: Наука, 1986.

87. Розенблит A.B., Голендер А.Е. Логико-комбинаторные методы в конструировании лекарств. Рига: Зинатне, 1983.1

88. Сешу С., Рид М.Б. Линейные графы и электрические цепи; М.: Высшая школа:, 1971. . ! :129?

89. Татт У Теория$графов1 — М!:^Мир;;1988; ; " '

90. Турбин А. Ф., Працевйтый ШВ1. Фрактальные^ множества. Функции, „ распределения. Киев: Наукова да " ' ;132' Уилсон Р: Введение в теорию графов. М.: Мир, 1977. - 208 с.

91. Федер Е. Фракталы.'- М: Мир, 1991. •

92. Фляйншнер У.Эйлеровыграфы и смежные вопросы, М.: Мир, 2002.

93. Фракталы, в физике / Под редщлдеш Л Пъетро}1еро, Э. Тозатти. — М.: Мир, 1988.

94. Хакен Г.Синергетика.—М: Мир; 1980? '

95. Хакен Г. Информация и самоорганизация. М.: Мир, 1991.

96. Хакен Г. Тайны приводы. Синергетика;.учение ©¡взаимодействии. Москва-Ижевск: Издательство Института компьютерных исследований,2003. . '

97. Таганрог: ИздательствомТаганрогского^ технологического института Южного федерального университета, 2011. С. 321-330.

98. Харари Ф. Теория графов. М.: Мир, 1973. - 302 с.143'. Химические приложения: топологии и теории ірафов / Под редакцией Р.

99. Кинга.-М.: Мир, 1987.: • ' <■■;.'■•'

100. АА ШредерМ. Фрактальц ха6с, ;степенныё законь1. Миниатюры из бесконечного рая. Ижевск: Научно-исследовательский центр «Регулярная и /хасїтинеская-данамш^