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

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

ЭЛЬКАНОВА Лиза Муратовна

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

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

АВТОРЕФЕРАТ

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

"НИИ1«

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

Работа выполнена в Карачаево-Черкесской государственной технологической академии

Научный руководитель: доктор физико-математических наук, профессор

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

Официальные оппоненты: доктор физию-матемагических наук, профессор

Наац Игорь Эдуардович доктор физико-математических наук, профессор Ашабоков Борис Азреталиевич

Ведущая организация: Кубанский государственный университет

(г. Краснодар)

Защита состоится «16» февраля 2008 г в 14 часов 30 минут на заседании совета по защитам докторских и кандидатских диссертаций Д 212 256 08 при Ставропольском государственном университете по адресу 355009, Ставропольский край, г Ставрополь, ул Пушкина, 1, ауд 214

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

Автореферат разослан « » января 2008 г

Ученый секретарь диссертационного совета

Л Б Копыткова

Общая характеристика работы

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

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

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

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

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

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

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

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

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

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

Еще до введения понятия фрактального графа возникали и решались задачи с фрактальной структурой Например, в 1989 году в работах профессора И Г Винтизенко была рассмотрена и решена задача о компоновке монтажно-коммуникационного пространства, в решении которой используется фрактальная структура

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

Объектом исследования являются ориентированные предфрак-тальные графы

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

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

Поставленная цель определила необходимость решения ряда частных научных задач.

1 Построение математической модели потока сетевой системы с одним истоковым и множеством стоковых элементов

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

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

4 Разработка алгоритмов распознавания масштабно-инвариантных структур в виде ориентированных предфрактальных графов

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

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

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

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

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

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

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

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

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

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

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

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

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

- распознавание ориентированного предфрактального графа, порожденного затравкой "дуга";

- распознавание ориентированного предфрактального графа, порожденного затравкой "однонаправленный ориентированный путь длины

- распознавание ориентированного предфрактального графа, порожденного затравкой "внешненаправленная звезда",

- распознавание ориентированного предфрактального графа, порожденного затравкой "однонаправленный цикл четной длины",

4) многокритериальная модель задачи о максимальном потоке на ориентированном предфрактальном графе определена шестью критериями, погрешность решения, полученного с помощью известного алгоритма Форда-Фалкерсона

Апробация работы Основные результаты работы докладывались на XIV Международной конференции "Проблемы управления безопасностью сложных систем" (Москва, 2006), на VI международной конференции "Когнитивный анализ и управление развитием ситуаций" (Москва, 2006), на II Всероссийской научно-практической конференции "Перспективные системы и задачи управления" (Домбай, 2007), на V Московской международной конференции по исследованию операций (Москва, 2007), на Международной междисциплинарной научной конференции "Третьи Курдюмовские чтения Идеи синергетики в естественных науках" (Тверь, 2007), на Международной научной конференции "Проблемы регионального и муниципального управления" (Москва, 2007), на X научно-практическом семинаре "Новые информационные технологии" (Москва, 2007), на VI Международной научно-практической конференции «Проблемы экономики, организации и управления предприятиями, отраслями, комплексами в разных сферах народного хозяйства» (Новочеркасск, 2007), на Международной научно-практической конференции «Методы и алгоритмы прикладной математики в технике, медицине и экономике» (Новочеркасск, 2007) Материалы исследования обсуждались на научных семинарах профессорско-преподавательского состава Карачаево-Черкесской государственной технологической академии и филиала Южного Федерального Университета в г. Черкесске (Черкесск, 2004-2007)

Полученные в диссертации результаты нашли практическое при^ менение на следующих предприятиях'

1. Федеральное Государственное Учреждение Управления эксплуатацией Большого Ставропольского Канала;

2 ГИБДД Прикубанского РОВД КЧР;

3 ГОУВПО «Карачаево-Черкесская государственная технологическая академия» в учебном процессе (учебная дисциплина «Синергетика и фракталы»)

Публикации. Основные результаты выполненной работы отражены в 13 публикациях автора, в том числе 1 - в издании из Перечня ведущих рецензируемых научных журналов и изданий

Структура диссертацщ .Диссертация состоит из введения и четырех глав, вый.6д6в и предложени(1,'"библиографического списка. Работа содержит 109 страниц, 17 рисунков и библиографический список из 203 наименований

Содержание работы

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

В первой главе «Моделирование многостоковых сетевых систем Показатель уровня просачиваемости» построена и исследована теоретико-графовая многостоковая потоковая модель сложной сетевой системы

Как отмечалось ранее, структуру любой сетевой системы разумно представлять в виде графа в ~ (У,Е) В диссертационной работе представлен такой граф для нефтепроводной системы Российской Федерации Вершины этого графа соответствуют местам добычи нефти, заводам по переработке нефти, узловым станциям трубопроводной системы Ребра графа соответствуют участкам трубопровода, соединяющим узловые элементы трубопроводной системы Ребра графа С = (У,Е) являются неориентированными Но в действительности поток нефтепродукта на каждом участке трубопровода имеет направление, а значит, любое ребро графа <7 = (V, Е) можно сориентировать, т е задать каждому ребру начало и конец в соответствии с направлением потока на участке трубопровода Граф сетевой трубопроводной системы с заданными направлениями ребер (ориентированные ребра графа, напомним, принято называть дугами) будем обозначать через д = (У,Е)

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

Потоковым путем Р(у) ориентированного графа О = (У,Е) назовем кратчайший путь от центральной до периферийной вершины V е V Периферийной вершине V е V не всегда может соответствовать только один потоковый путь Множество всех потоковых путей обозначим через Ур

Потоковой цепью 5(у) графа (7 = (У, Е) назовем кратчайшую неори-ентиро ванную цепь от центральной до периферийной вершины V е V Периферийной вершине V е V не всегда может соответствовать только одна потоковая цепь Множество всех потоковых цепей обозначим через У3

ы

Показателем уровня просачиваемости назовем отношение ф =

При ф > 0 в системе есть потоковая просачиваемость, т е на графе <5 = (У, Е) можно выделить хотя бы один потоковый путь, или нефтепродукт трубопроводной сетевой системой будет доставлен хотя бы до одного из получателей Очевидно, что при ф = 1 потоки продвигаются до всех стоков

Лемма 1.1. Показатель уровня просачиваемости центральнона-правленной звезды равен О

Лемма 1.2. Показатель уровня просачиваемости внешненаправ-ленной звезды равен 1

Лемма 1.3. Показатель уровня просачиваемости однонаправленного пути равен 1/2

Во второй главе «Исследование метрических характеристик ориентированных фрактальных графов с различными затравками» введено понятие ориентированного предфрактального графа и исследован ряд его свойств и характеристик

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

Термином затравка условимся называть какой-либо связный ориентированный граф Й-(IV,О) Суть операции замены вершины затравкой (ЗВЗ) заключается в следующем В данном графе б = (V, Е) у намеченной для замещения вершины V е У выделяется множество

^ = 7 = 1,2, ,\У\ смежных ей вершин Далее, из графа <5

удаляется вершина V и все инцидентные ей дуги Затем каждая вершина уу е V, 1,2, ,|к| соединяется дугой с одной из вершин затравки Н = (Ж, 0 Вершины соединяются произвольно (случайным образом) или ло определенному правилу при необходимости

Ориентированный предфрактальный граф - конечный аналог ориентированного фрактального графа - будем обозначать через дь = (К^Я/), где

Уь - множество вершин графа, а Еь - множество его дуг Определим его рекуррентно, поэтапно заменяя каждый раз в построенном на предыдущем этапе 1 = 1,2, ,Ь-\ графе <Э( = (У1,Е1) каждую его вершину затравкой Н = (IV, 0 На этапе 2 = 1 ориентированному предфрактальному графу соответствует затравка = Н Об описанном процессе говорят, что ориентированный предфрактальный граф д1=(У[1,Е1) порожден затравкой Н - (IV, О) Процесс порождения ориентированного предфрактального фафа д; по существу есть процесс построения последовательности ориентированных предфрактальных графов (7,, <72, , , называемой траекторией Ориентированный фрактальный граф <7 = (У, Е), порожденный затравкой Н = ((¥, 0, определяемся бесконечной траекторией Ориентированный предфрактальный граф =(УЬ,ЁС) условимся назьшать (п,д,Ь) -ориентированым графом, если он порожден «-вершинной д-дуговой связной ориентированной затравкой Я = (РУ, 0

Для ориентированного предфрактального графа Одуги, появившиеся на / -ом, I е {1,2, , Ь} этапе ■ порождения, будем называть дугами ранга / Новыми дугами предфрактального графа назовем

дуги ранга Ь, а все остальные дуги назовем старыми

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

Пусть О, =(У/ ,Е/ ) - предфрактальный ориентированный граф, порожденный ориентированной затравкой Я-контуром (рис. 1).

Рисунок 1. Предфрактальный ориентированный граф порожденный контуром

Теорема 2.1. Для всякого графа , порожденного кон-

туром Я , диаметр .

Теорема 2.2. Для всякого предфрактального ориентированного (и, ц, I) -орграфа О, = (1/! ,Ё1) множество остовных деревьев X = Х(С) содержит собственное подмножество, состоящее только из ПОД, то есть выполняется строгое неравенство для их мощностей:

1г|<|лг|.

Теорема 2.3. Для всякого предфрактального ориентированного (п,д,Ь)-графа С/ — (К, , Е/), порожденного затравкой Я справедливы оценки минимальной степени 50(Я) < 50((5) < ¿50(Я), причем верхняя и нижняя оценки достижимы.

Теорема 2.4. Всякий ориентированный предфрактальный ациклический граф G, - (Vl,El) , порожденный затравкой Н = {fV,Q), имеет

диаметр равный d(GL) = La, где а = d(H) - диаметр загравки

H=(WtQ)

Пусть GL - ориентированный предфрактальный граф, порожденный затравкой-звездой Н = (IV, Q) , начала дуг которого смежны Замещение проводится по принципу вершины предфрактального ориентированного графа Gl_x являются центрами затравок предфрактального орграфа Gh

Теорема 2.5. Всякий ориентированный предфрактальный граф GL, порожденный затравкой-звездой по принципу, описанному выше, имеет диаметр d(GL) = 1L

Третья глава «Алгоритмы распознавания ориентированных предфрактальных графов с различными затравками» посвящена распознаванию ориентированных предфрактальных графов Предложены и обоснованы пять алгоритмов распознавания ориентированных предфрактальных графов, порожденных различными затравками алгоритм

У у ~ распознавание ориентированного предфрактального графа, порожденного затравкой "дуга"; алгоритм уг - распознавание ориентированного предфрактального графа, порожденного затравкой "однонаправленный ориентированный путь длины g", алгоритм уг ~ распознавание ориентированного предфрактального графа, порожденного затравкой "внешненаправленная звезда", у4 - распознавание ориентированного предфрактального графа, порожденного затравкой "однонаправленный контур четной длины"

Все предложенные алгоритмы являются полиномиальными

Теорема 3.1. Вычислительная сложность алгоритма распознавания ориентированного предфрактального графа GL = (VL,EL), порожденного затравкой "дуга", оценивается неравенством 'т(у1)<0(\VL\ L) = 0(\V1\log\Vl\) Теорема 3.3. Вычислительная сложность алгоритма у2 распознавания

ориентированного предфрактального графа GL=(VL,EL), порожденного затравкой "однонаправленный ориентированный путь длины g", оценивается неравенством т(у2) S OQ VL | L) = 0(\ VL | log | VL |)

Теорема 3.6. Вычислительная сложность алгоритма уъ распознавания ориентированного предфрактального графа бь ~(У£,Ё1), порожденного затравкой "внешненаправленная звезда", оценивается неравенством т(у4) < 0(т £), где т = |

Теорема 3.9. Всякий предфрактальный (п,Ь)-гр&§ С = {У,Е) с циклической затравкой четной длины распознается алгоритмом у4 с полиномиальной трудоемкостью, т е т(у4) < 0(|£|/,)

Четвертая глава «Гарантированные оценки потока в многостоковых задачах на ориентированых предфрактальных графах с заданными затравками» посвящена многокритериальной постановке потоковой задачи на ориентированных предфрактальных графах

Рассмотрим предфрактальный ориентированный граф дс = (У, ,Е1), порожденный затравкой Н-^^О), у которой мощность множества вершин = п , а мощность множества дуг = ц

Пусть х - некоторый поток из Б вТ X = {х}-множество всех потоков предфрактального графа = (У1,Е1)

Оценка потока на предфрактальном ориентированном графе Оь задается векторно-целевой функцией (ВЦФ)

JO 7»

0,у, ^ -» тах хеХ (2)

где 7 - сумма потоков дуг, соединяющих вершину у, с такими

, которые последуют у,,

- сумма потоков дуг, соединяющих вершину у, с теми ,

/>1

которые предшествуют у,

Р2 (л) = шах Сг тт , (3)

хеХ

где |С\| - длина пути Сх потока л:

F3 (x) = max d+ (v() —> mm ,

(4)

где Ух -множество вершин потока х

с1+(у1 ) - полустепень исхода вершины V,

Р\(х) = тахйП(у,) —> тт,

(5)

где d (v,) - полустепень захода вершины v(

(6)

где Ух -множество вершин потока х

= ^¿Iv^nim,

(7)

где Ух -множество вершин потока х

Все критерии векторно-целевой функции имеют конкретную содержательную интерпретацию

Первый критерий определяет максимальный поток предфракталь-

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

- в транспортном потоке - число развязок,

- в денежном потоке указывает на затраты на обработку,

- в водном потоке уменьшение притоков снижает вероятность паводка

Пусть каждой дуге ориентированного предфрактального графа <3 ~ (У, Е) приписаны пропускные способности по принципу каждой

дуге <г,'у, г,у = 1,п затравки Н = (IV, О) поставлены в соответствие пропускные способности }, р\к1 е [а,Ь\

Затравка Н = (¡V,0) = , в (72 = (У2,Е2) приписываются пропускные способности дугам по принципу дуге efJ соответствует

р]} = кр\ /, где к - коэффициент масштабирования, 0 < к < 1 И так

далее на следующих шагах /, 1 = 1,1 , ¿-число рангов 6 дуги е('7

ставим в соответствие пропускные способности р\ = к1~*р\

Рассмотрим предфрактальный орграф 6 = (V, Ё) с затравкой Я , состоящей из дуги, в траектории у которого смежность старых дуг не нарушается

Рассмотрим задачу нахождения максимального потока из источника Б в сток Т, где Э-начало дуги 1 -го ранга, Т-все висячие вершины <5/. = , тогда

ТЕОРЕМА 4.1. Максимальный поток В, предфрактального ориентиро-

Ь(\-к!)

ванного графа д = (У,Е) из Б в Т равен Вь = 1 - к

г1-хк'ь$<к<у2

где 1 = 1,Ь,

Ь - максимальный поток загравки 1-го ранга

Рассмотрим предфрактальный орграф С'1—(У1,Ё1) с затравкой-

п-вершинной внешненаправленной звездой Н = Найдем мак-

симальный поток из Б в Т, где 5 - центр звезды первого ранга, Т -множество стоков, совпадающих с висячими вершинами предфрактального графа ={У1,ЕЬ)

ТЕОРЕМА 4.2 Максимальный поток В[ В орграфе <3, = (У1,Ё1) из источника Б в сток Т оценивается следующими неравенствами

1

В, <

г'-1к'(п-\)ь , о <к<~,

в\

(п-ц'^И, ^-<к< 1 1 -к я,

2'-хк1(п-\)а , 0 <к<-^~

где 1 = \,Ь, В1- максимальный поток затравки,

Ь - максимальная пропускная способность дуги затравки Н ~(1У,0) Рассмотрим многокритериальную задачу на предфрактальном ориентированном графе <31-(У1,Ё1) с затравкой Н = {]¥,0)- п-вершинной внешненаправленной звездой, построенному по принципу

каждая вершина предфрактального ориентированного графе = является центром затравки предфрактального ори-

ентированного графа О, = (У,,Е1)

Пусть 5 - исток предфрактального ориентированного графа 01=(У1>Е1), который совпадает с центром звезды первого ранга Стоками являются все висячие вершины

Теорема 4.3 Если х - поток в предфрактальном ориентированном графе 01=(УС>Е1), то справедливы гарантированные оценки

4 1 -к Вх

21'хк1{п~\)Ь , 0 <к<~

в\

.ад*

1 + к1

1 -к Рг(х)<Е(п-1), ВД = 1,

где к - коэффициент масштабирования,

В,-максимальный поток затравки Н - {Ш,0), Ь - максимальная пропускная способность дуги затравки

а,

Основные результаты, полученные в диссертационной работе;

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

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

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

ми ух - распознавание ориентированного предфрактального графа, порожденного затравкой "дуга", у2 - распознавание ориентированного предфрактального графа, порожденного затравкой "однонаправленный ориентированный путь длины ¿\ уъ - распознавание ориентированного предфрактального графа, порожденного затравкой "внешненаправленная звезда"; у4 ~ распознавание ориентированного предфрактального графа,

порожденного затравкой "однонаправленный контур четной длины"

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

По теме диссертации опубликованы следующие работы:

1 Эльканова, Л М Дискретная модель структурного разрушения сложных систем / А А Кочкаров, М Б Салпагаров, Эльканова Л М // Проблемы управления -2007 -№5 -С 21-26

2 Эльканова, Л М Метрические характеристики предфрактального графа с полными различными затравками /Л М Эльканова, А М Кочкаров // Материалы Третьей Международной конференции «Нелокальные краевые задачи и родственные проблемы математической биологии, информатики и физики» - Нальчик НИИ ПМА КБНЦ РАН, 2006 -С 334-335

3 Эльканова, Л М Особенности структурного разрушения сложных систем / Л М Эльканова, М Б Салпагаров, А А Кочкаров, Кочкаров РА// Материалы Международной научно-практической конференции «Методы и алгоритмы прикладной математики в технике, медицине и экономике» - Новочеркасск ЮРГТУ (НПИ), 2007 - С 70-74

4 Эльканова, Л М Моделирование сложных социально-экономических систем в условиях- внешних негативных воздействий / Л М Эльканова, М Б Салпагаров // Материалы Шестой Международной научно-практической конференции «Проблемы экономики, организации и управления предприятиями, отраслями, комплексами в разных сферах народного хозяйства» -Новочеркасск ЮРГТУ (НПИ), 2007 - С 33-35 .

5 Эльканова, Л М Программно-целевые методы в России / Л М Эльканова, Р А Кочкаров //Третьи Курдюмовские чтения «Синергетика в естественных науках» - Тверь ТГУ, 2007 - С 345-347,

6 Эльканова, Л M., Распознавание предфрактального графа с двумя затравками / ЛM Эльканова, И X Утакаева // Материалы Второй Всероссийской научно-практической конференции «Перспективные системы и задачи управления» -Таганрог ТИЮФУ, 2007 - С 180-183

7 Эльканова, JI M Двухпараметрическая шестикритериальная задача о р-центрах / JI M Эльканова, А А Узденов // Материалы Второй Всероссийской научно-практической конференции «Перспективные системы и задачи управления» -Таганрог ТИЮФУ, 2007 - С 188-190

8 Эльканова, Л.М Оценка оптимального потока на предфрактальных орграфах / Л M Эльканова, И X Найманова // Материалы Второй Всероссийской научно-практической конференции «Перспективные системы и задачи управления» -Таганрог ТИЮФУ, 2007 - С 190-191

9 Эльканова, JIM Планирование и программно-целевые методы в России / Л M Эльканова, Р А Кочкаров // Материалы Второй Всероссийской научно-практической конференции «Перспективные системы и задачи управления» - Таганрог ТИЮФУ, 2007 - С 239-241

10 Эльканова, Л M Условия существования максимального потока на ориентированных предфрактальных и фрактальных графах / Л M Эльканова//Черкесск КЧГТА,2007 Деп в ВИНИТИ № 747-В2007 - С 1-12

11 Эльканова, Л.М. Метрические характеристики ориентированных предфрактальных и фрактальных графов с затравкой-звезда и затравкой-контур / Л M Эльканова // Черкесск КЧГТА , 2007 Деп в ВИНИТИ №848 - В2007 - С 1-14

12. Эльканова, Л M Многокритериальная задача о потоке на ориентированных предфрактальных и фрактальных структурах Препринт № 155 Нижний Архыз РАН CAO 2007 - С 1-15

13 Эльканова, Л M Поведение параметров ориентированных предфрактальных и фрактальных структур Препринт № 154 Нижний Архыз РАНСА0.2007 - С 1-13

Подписано в печа!ь 10 012008 Формат 60x84 1/16 Уел печ л 1,05 Уч -изл л 0,88

Бумага офсетная Тираж 100 экз Заказ 4

Отпечатано в Издагельско-полиграфическом комплексе Ставропольского государственного университета 355009, Ставрополь, ул Пушкина, 1

Введение

Глава 1. Моделирование многостоковых сетевых систем. Показатель уровня просачиваемости.

1.1. Теоретико-графовая многостоковая потоковая модель сложной сетевой системы

1.1.1. Некоторые понятия и определения теории графов

1.1.2. Многостоковая потоковая модель трубопроводной системы

1.1.3. Математические модели теории просачиваемости.

1.3. Выводы.

Глава 2. Исследование метрических характеристик ориентированных фрактальных графов с различными затравками.

2.1. Ориентированный предфрактальный граф. Определение.

2.2. Диаметр и радиус ориентированного предфрактального графа.

2.3. Выводы.

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

3.1. Распознавание ориентированного предфрактального графа с затравкой "дуга".

3.2. Распознавание ориентированного предфрактального графа с затравкой "однонаправленный ориентированный путь длины

3.3. Распознавание ориентированного предфрактального графа с затравкой "внешненаправленная звезда".

3.4. Распознавание ориентированного предфрактального графа с затравкой "однонаправленный контур четной длины".

3.5. Выводы.

Глава 4. Гарантированные оценк потока в многостоковых задачах на ориентированых предфрактальных графах с заданными затравками.

4.1. Классификация потоков в сетевых системах.

4.2. Многокритериальная оптимизация. Термины, понятия, алгоритмы с оценками.

4.3. Многокритериальная потоковая задача на ориентированных пред фрактальных графах.

4.4. Выводы.

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

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

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

Активные исследования в рамках обеих парадигм проводились в течение 30 лет научной школой член-корр. РАН Курдюмова С.П.

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

Можно ли выделить общие черты в поведении сложных систем разной природы и, если «да», то чем обусловлена эта общность? Каковы перспективы развития единых подходов к сложному, применимых не только в технических, но и в общественных науках, а также в науках о живом? Обусловлена ли сложность процессами самоорганизации или является организованной искусственно?

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

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

Можно сказать, что создаваемая парадигма сама, в некотором смысле, лежит на кромке хаоса, т.е. на стыке двух предшествующих парадигм. Сами они слишком просты, чтобы описывать сложное, ведь поведение изучаемых в их рамках систем достаточно однородно - диссипативные структуры "одинаково регулярны", хаос — "одинаково нерегулярен".

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

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

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

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

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

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

В русском языке термин "сложность" имеет двоякий смысл. С одной стороны, его можно понимать как сложность устройства (complication, compound), т.е. как наличие в некоторой системе большого числа элементов и (или) нетривиальных связей между ними. А с другой стороны, речь может идти о сложности внешних проявлений системы (complexity) безотносительно ее внутреннего устройства, т.е. о нетривиальном поведении. Эти две "сложности" во многом взаимосвязаны, но не эквивалентны,, и понятие "сложность" далее будет использоваться только во втором из упомянутых значений. Хотя строгого определения сложности не существует, опыт развития синергетики и изучения конкретных систем, интуитивно определяемых нами как сложные, позволяет высказать некоторые общие соображения о свойствах любой сложной системы на разных уровнях описания.

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

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

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

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

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

Правилам изменения структур сетевых систем и законам структурной динамики посвящено множество работ [58-60,176,180,183-196,199,200]. В значительной степени это работы иностранных исследователей. Отечественными исследователями для описания изменений в сложных сетевых структурах было введено понятие "фрактального графа" [76,158-166,196]. Фрактальный граф (и его конечный аналог - предфрактальный граф)- объект, совмещающий в себе основные идеи структурной динамики, свойство масштабной инвариантности (самоподобия) фракталов [13,103,156,181], и абстрактность теории графов.

Еще до введения понятия фрактального графа возникали и решались задачи с фрактальной структурой. Например, в 1989 году И. Г. Винтизенко в диссертационной работе на соискание ученой степени доктора технических наук « » была рассмотрена и решена задача о компоновке , алгоритм решения которого имеет фрактальную структуру.

Изучение фрактальных графов и областей их приложения ведутся по трем направлениям: распознавание фрактальных графов [76], свойства и характеристики фрактальных графов [58-61,77-82,184], задачи многокритериальной оптимизации [181] в системах с масштабно-инвариантной структурой [7-9,36-47]. В работах, связанных с оптимизационными задачами, предложен и обоснован ряд параллельных алгоритмов поиска решений [40,47,62,63].

Эту методологию можно использовать для описания и моделирования селевых потоков, водотоков рек, потоков лавинообразных процессов, а также потоков транспорта в системе автомобильных дорог, перевозок товаров по железным дорогам, перекачки нефти и газа по сети трубопроводов от источника до пункта назначения, используя потоки в сетях и на графах [2022,27,29,87,149,159].

С одной стороны, естественным образом, возникает класс многокритериальных задач оптимизации [2,11,12,24,31,92-96,124-126] потоков в сетевой системе с ограничениями по пропускным способностям передающих составляющих. Поиск решения многокритериальных потоковых задач необходим при динамически изменяющихся, или случайно выбранных значениях пропускных способностей передающих составляющих сетевых систем.

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

Все перечисленные задачи лежат в области понятий математического моделирования, исследования операций и системного анализа [11,1417,85,127,128,150].

В нескольких институтах Российской Академии Наук (в Институте прикладной математики им. М.В. Келдыша, Институте проблем управления им. Трапезникова, Вычислительном центре им. A.A. Дородницына), в различных научных школах ведутся работы по исследованию живучести и поведения сетевых систем, находящихся в условиях внезапных внешних воздействий неопределенного характера [66-73,88-91,98-104, 135-139].

Способность системы функционировать во внештатных режимах называют живучестью [32,102]. Более узко способность системы функционировать в условиях внешних негативных воздействий ряд исследователей называют стойкостью [56,66-73,135-139]. Исследование живучести, стойкости и уязвимости [100,112-114] сетевых систем являются важными практически востребованными задачами.

Краткое содержание и структура диссертационной работы

Диссертационная работа посвящена моделированию сложных сетевых систем и моделированию задач на этих системах.

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

1. Построение математической модели потока сетевой системы с одним истоком и множеством стоков.

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

3. Определение метрических и числовых характеристик ориентированных фрактальных графов.

4. Разработка алгоритмов распознавания масштабно-инвариантных структур в виде ориентированных предфрактальных графов.

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

Объектом исследования являются ориентированные предфрактальные графы.

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

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

В диссертационной работе построена математическая модель потока сетевой системы с одним истоком и множеством стоков элементов.

Сетевая система со сложной масштабно-инвариантной (фрактальной) структурой представлена на многостоковой потоковой моделью.

Введено понятие ориентированного предфрактального графа, исследован ряд его свойств и характеристик.

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

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

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

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

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

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

Во второй главе введено понятие ориентированного предфрактального графа и исследован ряд его свойств и характеристик.

Третья глава посвящена распознаванию ориентированных предфрак-тальных графов. Предложен и обоснован комплекс алгоритмов распознавания ориентированных предфрактальных графов, порожденных различными затравками: алгоритм — распознавание ориентированного предфракталь-ного графа, порожденного затравкой "дуга"; алгоритм у2 ~ распознавание ориентированного предфрактального графа, порожденного затравкой "однонаправленный ориентированный путь длины алгоритм у3 — распознавание ориентированного предфрактального графа, порожденного затравкой "внешненаправленная звезда"; алгоритм 74 - распознавание ориентированного предфрактального графа, порожденного затравкой "однонаправленный контур четной длины".

Все предложенные алгоритмы являются полиномиальными.

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

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

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

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

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

- распознавание ориентированного предфрактального графа, порожденного затравкой "однонаправленный ориентированный путь длины §";

- распознавание ориентированного предфрактального графа, порожденного затравкой "внешненаправленная звезда";

- распознавание ориентированного предфрактального графа, порожденного затравкой "однонаправленный цикл четной длины";

4) многокритериальная модель задачи о максимальном потоке на ориентированном предфрактальном графе определена шестью критериями; с помощью известного алгоритма Форда-Фалкерсона выделяется приближенное решение поставленной задачи и вычисляется погрешность.

0. 4.4. Выводы

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

Заключение.

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

При этом получены следующие новые научные результаты:

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

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

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

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

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

2. Айзерма М.А., Алескерое Ф.Т. Выбор вариантов. Основы теории. — М.:

3. Арнольд В.И. Теория катастроф. М.: Знание, 1981.

4. Асанов М. О., Баранский В.А., Расин В.В. Дискретная математика: графы, матроиды, алгоритмы. Ижевск: НИЦ "РХД", 2001.

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

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

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

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

9. Березовский Б.А., Барышкин Ю.М., Борзенко В.И., Кемпнер Л.М. Многокритериальная оптимизация: математические аспекты. М.: Наука, 1989.

10. Берж К. Теория графов и ее применения. М.: Изд-во иностр. лит., 1962.

11. Божокин C.B., Паршин Д. А. Фракталы и мультифракталы. Ижевск: НИЦ«РХД», 2001.

12. Венцелъ Е.С. Введение в исследование операций. -М.: Сов. радио, 1964.

13. ГафтМ.Г. Принятие решений при многих критериях. M.: Знание, 1979.

14. Гермейер Ю.Б. Введение в теорию исследования операций. М.: Наука, 1971.

15. ГиллФ., МюрейУ., Райт М. Практическая оптимизация. М.: Мир, 1985.

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

17. Дубов Ю. А., Травкин СИ., ЯкимецВ.Н. Многокритериальные модели формирования и выбора вариантов систем. М.: Наука, 1986.

18. Евстигнеев В.А., Касьянов В.Н. Графы в программировании: обработка, визуализация и применение. СПб.: БХВ-Петербург, 2003.

19. Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки бесконтурных графов. Новосибирск: Наука, 1998.

20. Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки деревьев. Новосибирск: Наука, 1994.

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

22. Емельянов C.B., Ларичев О.И. Многокритериальные методы принятия решений. -М.: Знание, 1985.

23. Ермольев Ю.М., Ляшко ИИ, Мшайлевич B.C., Тюптя В.И. Математические методы исследования операций. Киев: Вища школа, 1979.

24. Жуковин В.Е. Многокритериальные модели принятия решений с неопределенностью. -Тбилиси: Мецниереба, 1983.

25. Замбицкий Д.К., ЛозовануД.Д. Алгоритмы решения оптимизационных задач на сетях. Кишинев, Штиинца: 1983.

26. Зыков A.A. Теория конечных графов. Новосибирск: Наука, 1969.

27. Иенсен П., БарнесД. Потоковое программирование. — М.: Радио и связь, 1984.

28. Кестен X. Теория просачиваемости для математиков. — М.: Мир, 1986.

29. Kuhu P.JI., РайфаХ. Принятие решений при многих критериях: предпочтения и замещения. М.: Радио и связь, 1981.

30. Козлов М.В., Малашенко Ю.Е., Рогожин B.C., Ушаков И.А., Ушакова Т.В. Моделирование живучести систем энергетики: методология, модель, реализация. М.: ВЦ АН СССР, 1986.

31. Компьютеры и нелинейные явления. М.: Наука, 1988.

32. Компьютеры, модели, вычислительный эксперимент. М.: Наука, 1988.

33. Кононов Д.А., Кулъба В.В. и др. Синтез формализованных сценариев и структурная устойчивость сложных систем (синергетика и аттрактивное поведение). Препринт. М.: Институт проблем управления, 1998.

34. Коркмазова З.О. Выделение максимальных эйлеровых подграфов на предфрактальном графе. Черкесск: Карачаево-Черкесская гос. технолог, ак., 2004. Деп. в ВИНИТИ № 1731-В2004. - С. 1-25.

35. Коркмазова З.О. Многокритериальная задача разбиения на эйлеровые подграфы предфрактального графа. Черкесск, Карачаево-Черкесская Гос. Технолог. Ак., 2004. Деп. в ВИНИТИ № 1729-В2004. С. 1-25.

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

37. Коркмазова 3.0., Кочкарое P.A. Многокритериальная задача покрытия предфрактапьного графа эйлеровыми подграфами: Препринт Спец. астрофиз. обсерватории РАН № 208. Нижний Архыз, 2005. 15 с.

38. Коркмазова 3.0., Кочкарое P.A. Многокритериальная задача покрытия предфрактального графа эйлеровыми подграфами Препринт Спец. астрофиз. обсерватории РАН № 209. Нижний Архыз, 2005. 27 с.

39. Косорукое O.A., Мищенко A.B. Исследование операций. — М.: Экзамен, 2003.

40. Кочкаров A.A., Кочкаров P.A. О планарности и других топологических свойствах фрактальных графов. Препринт №83. М.: ИПМ им. М.В. Келдыша РАН, 2003.

41. Кочкаров P.A., Элъканова JI.M. Планирование программно-целевые методы в России. // Вторая Всероссийская научно-практическая конференция. «Перспективные системы и задачи управления». Таганрог 2007. С.239-241.

42. Кочкаров P.A., Элъканова JI.M. Программно-целевые методы в России. // Третьи Курдюмовские чтения: «Синергетика в естественных- науках». Тверь 2007.С.345-347.

43. Кочкаров A.A. Структурное управление и обеспечение стойкости сложных систем // III Международная конференция по проблемам управления. Тез. докл. Том I. М.: Ин-т проблем управления им. В.А. Трапезникова РАН, 2006. С. 121-121.

44. Кочкаров A.A. Когнитивное моделирование. Концепция стойкости и структурное управление// Материалы международной междисциплинарной научной конференции "Вторые Курдюмовские чтения. Идеи синергетики в естественных науках". Тверь: ТвГУ, 2006. С. 74-75.

45. Кочкаров A.A. Плоские и планарные предфрактальные графы. // V Всероссийский симпозиум "Математическое моделирование и компьютерные технологии". Тез. докл. Кисловодск: КИЭП, 2002. С. 35 - 35.

46. Кочкаров A.A. Стойкость и моделирование систем, находящихся в условиях внешних воздействий // Труды XLVII научной конференции МФТИ

47. Современные проблемы фундаментальных и прикладных наук". Часть VII. М.: МФТИ, 2004. С. 190-190.

48. Кочкаров A.A. Стойкость, графы, синергетика// Новое в синергетике. Новая реальность, новые проблемы, новое поколение: Сб. статей. Часть 2 / Под ред. Г.Г. Малинецкого. — М.: Радиотехника, 2006.

49. Кочкаров A.A. Стойкость, графы, синергетика// Новое в синергетике. Новая реальность, новые проблемы, новое поколение: Сб. статей / Под ред. Г.Г. Малинецкого. М.: Наука, 2007. - С. 187-202.

50. Кочкаров A.A. Число всевозможных предфрактальных графов. //IV Всероссийский симпозиум "Математическое моделирование и компьютерные технологии". Тез. докл., том 2. Кисловодск: КИЭП, 2000. С. 73 -74.

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

52. Кочкаров A.A., Кочкаров P.A. Исследование связности предфрактальных графов. // IV Всероссийский симпозиум "Математическое моделирование и компьютерные технологии". Тез. докл., том 2. Кисловодск: КИЭП, 2000.-С. 74-75.

53. Кочкаров A.A., Кочкаров P.A. О критериях планарности фрактальных графов. // Труды XLVI научной конференции МФТИ "Современные проблемы фундаментальных и прикладных наук". Часть VII. М.: МФТИ, 2003.-С. 186- 186.

54. Кочкаров A.A., Кочкаров P.A. Параллельные алгоритмы на предфрактальных графах: Препринт ИПМ им. М.В. Келдыша РАН. М., 2003. 20 с.

55. Кочкаров A.A., Кочкаров P.A. Параллельный алгоритм поиска кратчайшего пути на предфрактальном графе // Журнал вычисл. матем. и матем. физики. 2004. - Т. 44, № 6. - С. 1157-1162.

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

57. Кочкаров A.A., Малинецкий Г.Г. Концепция стойкости для социально-экономических и технических систем // Труды Международной конференции "Математическое моделирование социальной и экономической динамики". М.: РГСУ, 2004. С. 151-154.

58. Кочкаров A.A., Малинецкий Г.Г. Моделирование распространения внешних воздействий по структуре сложной системы // Математическое моделирование. 2006. - Т. 18, № 2. - С. 51-60.

59. Кочкаров A.A., Малинецкий Г.Г. Моделирование стойкости сложных технических систем // Труды XII Международной конференции "Проблемы управления безопасностью сложных систем". М.: РГГУ, 2004. -С. 348-352.

60. Кочкаров A.A., Малинецкий Г.Г. Обеспечение стойкости сложных систем. Структурные аспекты: . М.: ИПМ им. М.В. Келдыша РАН, № 53, 2003.

61. Кочкаров A.A., Малинецкий Г.Г. Стойкость, управление риском и обеспечение безопасности сложных технических систем // Проблемы безопасности и чрезвычайных ситуаций. -2005. № 4. - С. 12-25.

62. Кочкаров A.A., Малинецкий Г.Г. Управление безопасностью и стойкостью сложных систем в условиях внешних воздействий// Проблемы управления. 2005. - № 5. - С. 70-76.

63. Кочкаров A.A., Салпагаров М.Б., Элъканова JI.M. Дискретная модель структурного разрушения сложных систем // Проблемы управления. -2007.-№5. С. 70-76.

64. Кочкаров A.A., Салпагаров С.И. Число мостов предфрактального графа.

65. V Всероссийский симпозиум "Математическое моделирование и компьютерные технологии". Тез. докл. Кисловодск: КИЭП, 2002. С. 36 — 37.

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

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

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

69. Кочкаров A.M., Перепелица В.А. О гамильтоновости фрактальных графов. //Международная конференция "Нелокальные краевые задачи и родственные проблемы математической биологии, информатики и физики". Тез. докл. Нальчик: НИИ ПМиА КБНЦ РАН, 1996. С.52-53.

70. Кочкаров A.M., Перепелица В.А. Число внутренней устойчивости пред-фрактального и фрактального графа. Сб. статей. РАН CAO. 1999.

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

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

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

74. Краснощекое П. С., Петров A.A. Принципы построения моделей. М.: Издательство МГУ, 1983.

75. Краснощекое П. С., Петров A.A., Федоров В.В. Информатика и проектирование. — М.: Знание, 1986.

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

77. Кулъба В.В., Кононов Д.А., Ковалевский С. С. и др. Сценарный анализ динамики поведения социально-экономических систем. Препринт. М.: Институт проблем управления, 2002.

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

79. Кулъба В.В., Кононов Д.А., Чернов И.В., Янич С.С. Сценарии управления государством (на примере Союза Сербии и Черногории) // Проблемы управления. 2005. № 5. С. 33-42.

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

81. Ларичев О.И. Объективные модели и субъективные решения. — М.: Наука, 1987.

82. Ларичев О.И. Теория и методы принятия решений. — М.: Логос, 2000.

83. ЛовасЛ., Плалшер М. Прикладные задачи теории графов. Теория паро-сочетаний в математике, физике, химии. М.: Мир, 1998.

84. Лотов A.B. Введение в экономико-математическое моделирование. М.: Наука, 1984.

85. Лотов A.B., Бушенков В.А., Каменев Г.К., Черных О.Л. Компьютер и поиск компромисса: Метод достижимых целей. М.: Наука, 1997.

86. Майника Э. Алгоритмы оптимизации на графах и сетях. М.: Мир, 1981.

87. Малашенко Ю.Е., Новикова КМ. Многокритериальный и максиминный анализ многопродуктовых сетей. -М.: ВЦ АН СССР, 1988.

88. Малашенко Ю.Е., Новикова КМ. Модели неопределенности в многопользовательских сетях. М.: Эдиториал УРСС, 1999.

89. Малашенко Ю.Е., Новикова Н.М. Потоковые задачи анализа уязвимости многопродуктовых сетей. М.: ВЦ АН СССР, 1989.

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

91. Малашенко Ю.Е., Рогожин B.C., Ферапнтов Е.В. Живучесть сетевых систем. М.: ВЦ АН СССР, 1989.103 .Манделъброт Б. Фрактальная геометрия природы. -М.: ИКИ, 2002.

92. Меламед Я.И., Сигал И.Х. Теория и алгоритмы решения многокритериальных задач комбинаторной оптимизации. -М.: ВЦ РАН, 1996.

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

94. Мелроуз Дж. Иерархические фрактальные графы и блуждания на них // Фракталы в физике / Под ред. Л. Пъетронеро, Э. Тозатти. М.: Мир, 1988.-С. 519-523.

95. Миркин Б.Е., Родин С.Н. Графы и гены. М.: Наука, 1977.

96. Многокритериальные задачи принятия решений. М.: Машиностроение, 1978.

97. Моисеев H.H. Алгоритм развития. М.: Наука, 1987.

98. Моисеев H.H. Математика ставит эксперимент. М.: Наука, 1979.

99. Моисеев H.H. Математические задачи системного анализа. М.: Наука, 1981.

100. Назарова И.А. Лексикографическая задача анализа уязвимости многопродуктовых сетей // Изв. РАН ТиСУ. 2003. № 5. С. 123-134.

101. Назарова И.А. Модели и методы анализа многопродуктовых сетей М.: ВЦ РАН, 2004.

102. Назарова H.A. Модели и методы решения задачи анализа уязвимости сетей // Изв. РАН ТиСУ. 2006. № 4. С. 61-72. Наука, 1990.

103. Нечепуренко М.И., Попков В.К., Майнагашев С.М. Алгоритмы и программы решения задач на графах и сетях. Новосибирск: Наука, 1990.

104. Новикова Н.М., Поспелова И.И. Многокритериальные задачи принятия решений в условиях неопределенности. М.: ВЦ РАН, 2000.

105. Ногин В Д. Принятие решений в многокритериальной среде: количественный подход. -М.: Физматлит, 2004.

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

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

108. ПавловД.А. Полиномиальный алгоритм нахождения максимального па-росочетания на предфрактальных графах// XVII Международная научная конференция "Математические методы в технике и технологиях -ММТТ-17". Сб. труд. Кострома: КГТУ, 2004.

109. Петров A.A. Исследование операций и математическое моделирование // материалы учредительной конференции Российского научного общества исследования операций. М.: ВЦ РАН, 1996

110. Петров A.A. Экономика. Модели. Вычислительный эксперимент. — М.: Наука, 1996.

111. Плесневич Г.С., Сатаров М. С. Алгоритмы в теории графов. Ашхабад: Ылым, 1981.

112. Подиновский В.В. Методы многокритериальной оптимизации / Математические методы в социальных науках. Вильнюс, 1972.

113. Подиновский В.В., Ногин В.Д. Парето-оптимамльные решения многокритериальных задач. М.: Наука, 1982.

114. ПолищукЛ.И. Анализ многокритериальных экономико-математических моделей. -М.: Наука, 1989.

115. Понтрягин Л.С., Болтянский В.Г., Гамкрелидзе Р.В., Мищенко Е.Ф. Математическая теория оптимальных процессов. М.: Наука, 1976.

116. Поспелов Г.С., Ириков В.А. Программно-целевое планирование и управление. М.: Сов. радио, 1976.

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

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

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

120. Салпагаров М.Б. Моделирование разрушения систем с масштабно-инвариантной структурой. — Черкесск: Карачаево-Черкес. Гос. Тех. Акад., 2007. Деп. в ВИНИТИ № 745-В2007. 36 с.

121. Салпагаров М.Б., Кочкаров A.A., Кочкаров P.A. Потоковое моделирование структурного разрушения сложных систем // Труды XIV Международной конференции "Проблемы управления безопасностью сложных систем". М.: РГГУ, 2006. С. 454-456.

122. Салпагаров С.И. Задача о назначениях на фрактальных и пред фрактальных графах. Многокритериальная постановка. Черкесск, КЧГТА, 2003, Деп. в ВИНИТИ, №2323-В2003. С. 1-34.

123. Самарский A.A., Михайлов А.П. вычислительный эксперимент. М.: Педагогика, 1987.

124. Самарский A.A., Михайлов А.П. Математическое моделирование: идеи, методы, примеры. М.: Физматлит, 2001.

125. Свами М., Тхуласираман К. Графы, сети и алгоритмы. М.: Мир, 1984.

126. Сешу С., Рид М.Б. Линейные графы и электрические цели. М.: Высш. шк., 1971.

127. Соболь И.М., Статников Р.Б. Выбор оптимальных параметров в задачах со многими критериями. — М.: Наука, 1981.

128. Соколов И.М. Размерности и другие геометрические критические показатели в теории протекания // УФН, 150(2), 221-255 (1985).

129. Сушков Ю.А. Графы зубчатых механизмов. Л.: Машиностроение, 1983.

130. Тарасевич Ю.Ю. Просачиваемость: теория, приложения, алгоритмы. — М.: Едиториал УРСС, 2002.

131. Tamm У. Теория графов. М.: Мир, 1988.

132. ТахаХ. Введение в исследование операций. -М.: Диалект, 2005.

133. Тихонов А.Н., Костомаров Д.П. Вводные лекции по прикладной математике. М.: Наука, 1984.

134. Турбин А.Ф., Працевитьгй Н.В. Фрактальные множества. Функции, распределения. Киев: Наук, думка, 1992.

135. Узденов A.A., Элъканова JI.M. Двухпараметрическая шестикритериальная задача о ¿»-центрах. // Вторая Всероссийская научно-практическая конференция. «Перспективные системы и задачи управления». Таганрог 2007. С. 188-190.

136. Уилсон Р. Введение в теорию графов. М.: Мир, 1977.

137. Утакаева И.Х., Элъканова JI.M. Распознавание предфрактального графа с двумя затравками. // Вторая Всероссийская научно-практическая конференция. «Перспективные системы и задачи управления». Таганрог 2007. С.180-183.

138. Федер Е. Фракталы. М.: Мир, 1991.

139. Филлпс Д., Гарсиа-Диас А. Методы анализа сетей. М.: Мир, 1984.

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

141. Форд Л., ФалкерсонД. Потоки в сетях. М.: Мир, 1966.

142. Фракталы в физике / Под ред. Л. Пъетронеро, Э. Тозатти. — М.: Мир, 1988.

143. Харари Ф. Теория графов. М.: Мир, 1973.

144. Химические приложения топологии и теории графов. Под ред. Кинга Р. ~ М.: Мир, 1987.

145. Хоменюк В.В. Элементы теории многокритериальной оптимизации. М.: Наука, 1983.

146. Шкловский Б.И., Эфрос А.Л. Теория протекания и проводимость сильно неоднородных сред // УФН, 117(3), 401-436 (1975).

147. Шкловский Б.И., Эфрос А.Л. Электронные свойства легированных полупроводников. -М.: Наука, 1979.

148. Шредер М. Фракталы, хаос, степенные законы. Миниатюры из бесконечного рая. Ижевск: НИЦ "Регулярная и хаотическая динамика", 2001.

149. Штойер Р. Многокритериальная оптимизация: теория, вычисления и приложения. М.: Радио и связь, 1992.

150. Элъканова Л.М. Метрические характеристики ориентированных пред-фрактальных и фрактальных графов с затравкой-звезда и затравкой-контур. //Черкесск , 2007. Деп. в ВИНИТИ №848-В2007. С. 1-14.

151. Элъканова Л.М. Многокритериальная задача о потоке на на ориентированных предфрактальных и фрактальных структурах. Препринт №155 РАН CAO. Нижний Архыз. 2007. С. 1-15

152. Элъканова Л.М. Поведение параметров ориентированных предфрактальных и фрактальных структур. Препринт №154РАН CAO. Нижний Архыз. 2007. С. 1-13.

153. Элъканова Л.М. Условия существования максимального потока на ориентированных предфрактальных и фрактальных графах. //Черкесск , 2007. Деп. в ВИНИТИ № 747-В2007. С. 1-12.

154. Эльканова Л.М.,Найманова И.Х. Оценка оптимального потока на пред-фрактальных орграфах. // Вторая Всероссийская научно-практическая конференция. «Перспективные системы и задачи управления». Таганрог2007. С.190-191.

155. Эфрос А.Л. Физика и геометрия беспорядка. -М.: Наука, 1982.

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

157. Barlow M.T. Diffusions on fractals / Lectures on probability theory and statistics. Springer Verlag, Berlin, 1998. P. 1-121.

158. BolltE.M., ben-Avraham D. What is Special about Diffusion on Scale-Free Nets? // New J. Phys., 2005. V. 7, № 26. - P. 1-21.l%.BroadbentS.K., Hammers ley J. M. Percolation processes I. Crystals and mazes // Proc. Camb. Phil. Soc. 53, 629-641 (1957).

159. Dorogovtsev S.N., Mendes J.F.F. Evolution of networks// Adv. Phys. 2002 -№51.-P. 1079-1187.

160. Grimmet G. Percolation. Berlin: Springer-Verlag, 1999.

161. Kigami J. Analysis on fractals / Volume 143 of Cambridge Tracts in Mathematics. Cambridge University Press, Cambridge, 2001.

162. Kochkarov A., Perepelitsa V. Fractal Graphs and Their Properties. // ICM 1998 Berlin, International Congress of Mathematicians, Abstracts of Short Communications and Posters, p. 347.

163. Leath P.L. Cluster size and boundary distribution near percolation threshold I I Phys. Rev. B, 14(11), 5046-5055 (1976).

164. Li L., Alderson D., TanakaR., Doyle J. C., Willinger W. Towards a Theory of Scale-Free Graphs: Definition, Properties, and Implications (Extended Version) // Technical Report CIT-CDS-04-006, Cal Tech, 2005.

165. Lyons R., Peres Y. Probability on trees and networks. Cambridge University Press, 2001.

166. Malozemov L., Teplyaev A. Pure point spectrum of the Laplacians on fractal graphs//J. Funct. Anal., 129(2):390-405, 1995.

167. Meester R, Roy R. Continuum percolation. Cambridge Univ. Press, 1996.

168. Pareto V. Manuel d'economie politique. Paris: Giard, 1909.

169. Riehl J., Hespanha J.P. Fractal graph optimization algorithms// Proc. of the 44th Conf. on Decision and Contr., 2005. P. 2188-2193.

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

171. Song C., HavlinS., Makse H.A. Self-similarity of Complex Networks// Nature 433, 392-395 (2005).

172. Stanley H.E. Introduction to Phase Transitions and Critical Phenomena. Oxford University Press, 1971.

173. StaufferD., Aharony A. Introduction to Percolation Theory. London: Taylor and Francis, 1992.

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

175. Watts D.J. Small Worlds. Princeton: Princeton University Press, 1999.201 .WoessW. Random walks on infinite graphs and groups / Volume 138 of Cambridge Tracts in Mathematics. Cambridge University Press, Cambridge, 2000.

176. ZiffR.M., Sapoval B. The efficient determination of percolation threshold by a frontier generating walk in a gradient // J. Phys. A: Math. Gen. 19, 1169-1172 (1986).

177. ZiffRM., Stell G. Univ. Mich. Report. 11-18 (1988).