Потоки в ресурсных сетях с нестандартной достижимостью тема диссертации и автореферата по ВАК РФ 05.13.17, кандидат наук Абдулрахман Хайдар

• Абдулрахман Хайдар
• кандидат наук
• 2020

Оглавление диссертации кандидат наук Абдулрахман Хайдар

Введение

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

1.1. Основные определения и понятия теории графов и сетей

1.2. Ресурсные сети и их классификация

1.2.1. Ресурсные сети определение

1.2.2. Однородные и неоднородные ресурсные сети

1.2.3. Эргодические, полуэргодические и неэргодические ресурсные сети

1.3. Графы с нестандартной достижимостью

1.3.1. Нестандартные достижимости нестрогого типа

1.3.2. Нестандартные достижимости строгого типа

1.4. Заключение к главе

Глава 2. Ресурсные сети с нестандартной достижимостью и их аналоги

2.1. Ресурсные сети с магнитной достижимостью

2.1.1. Ресурсные сети с накоплением неубывающей магнитности

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

2.1.3. Ресурсные сети с накоплением-исчезанием магнитности

2.2. Ресурсные сети с вентильной достижимостью

2.2.1. Ресурсные сети с вентильной накопительной достижимостью

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

2.3. Динамические ресурсные сети

2.3.1. Сети с временными пропускными способностями

2.3.2. Периодические динамические ресурсные сети

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

2.4. Заключение к главе

Глава 3. Двухресурсные сети

3.1. Однородные двусторонние полные сети с двумя ресурсами

3.2. Несимметричные двусторонние полные (НДП) сети

3.2.1. НДП сети с одним ресурсом

3.2.2. НДП сети с двумя ресурсами

3.2.3. НДП сети с двумя ресурсами и двумя пропускными способностями

3.3. Двухресурсные сети с магнитной достижимостью

3.3.1. Распределение двух ресурсов в сети с магнитной достижимостью

3.3.2. Двухресурсные сети с магнитной достижимостью и двумя пропускными способностями

3.4. Заключение к главе

Заключение

Литература

Введение диссертации (часть автореферата) на тему «Потоки в ресурсных сетях с нестандартной достижимостью»

Введение

Актуальность работы. Начало теории графов было положено Эйлером в 1736 г., когда им была написана статья о Кенигсбергских мостах. Однако она была единственной в течение почти ста лет. Интерес к этой науке возродился около середины XIX в связи с развитием естественных наук (исследования электрических сетей, моделей кристаллов и структур молекул), формальной логики. Кроме того, оказалось, что многие математические головоломки могут быть сформулированы в терминах теории графов.

Графы встречаются в разных областях: физике (диаграммы Феймана), электротехнике, химии (структурные формулы), генной инженерии и биоинформатике, социологии (социограммы), информатике (блок-схемы алгоритмов, управляющие графы программ). Экономике (сетевое пи календарное планирование). Область применения теории графов значительно расширилась в связи с развитием инфокоммуникационных сетей, появлением всемироной паутины - Интернета, сетей мобильной связи. Функционирование последних невозможно без использования основных алгоритмов теории графов, в частности алгоритма нахождения кратчайшего пути между двумя вершинами графа. Появление вредоносных программ -компьютерных вирусов, а также распространителей спама требует разработки алгоритмов анализа процессов случайного блуждания по графу и случайного распределения ресурса на графе. Задачи распространения спама оказались родственными задачам распространения инфекций (медицина) или распространению слухов (социология). Объединяют эти задачи общая математическая модель - ориентированный граф, лежащая в их основе, и алгоритмы, которые используются для решения этих задач. (см. [52], [59]-[63], [66]). Известные работы в этой области принадлежат Н. Кристофидесу, Р.Д. Басакеру, Ф. Харари, К. Бержу, Р. Флойду, Д.К. Замбицкому, О. Оре, Т.

Свами, Д.Р. Фалкерсону, Л.Р Форду, А.А. Зыкову, У Татту и др. (см. [37], [14]-[15], [51], [54]-[56], [34]-[35], [11], [42]-[44]).

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

Ресурсные сети - динамические графовые модели распространения ресурса были введены и изучены в работах О.П. Кузнецова и Л.Ю. Жиляковой. В них рассматривались однородные, несимметричные, симметричные, эйлеровые, полные, эргодические циклические ресурсные сети и исследованы для них предельные состояния ресурсной сети (см. [26]-[33], [38], [64], [65], [67], [69]). Ресурсная сеть - это сеть, где кроме заданных пропускных способностей дуг, для каждой вершины сети указано количество находящегося в ней ресурса («вещества»). Функционирование (работа) сети происходит в дискретном времени и состоит в обмене ресурсами, имеющимися в вершинах. Обмен ресурсами происходит по дугам сети. Количество ресурса проходящего по дуге в каждый дискретный такт работы ресурсной сети не может превосходить её пропускную способность. Таким образом, ресурс, находящийся в вершине может быть передан в следующий момент времени только в вершины, в которые ведут дуги из неё исходящие и количество передаваемого ресурса ограничено пропускными способностями дуг. В вершину может поступить ресурс только из вершин, в которых начинаются дуги, приходящие в вершину. Количество ресурса, которое может поступить в вершину ограничено пропускными способностями дуг,

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

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

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

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

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

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

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

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

Степень научной разработанности проблем. Ресурсные сети введены в работах О.П. Кузнецова и Л.Ю. Жиляковой (см. [38]-[40]). Были изучены модели распределения ресурса в полных двусторонних сетях, исследованы условия сходимости процесса перераспределения ресурса, а также предложен метод нахождения порогового значения и предельного состояния при разных величинах суммарного ресурса, доказаны теоремы о существовании предельного состояния и порогового значения суммарного ресурса.

Кроме этого, в работах Л.Ю. Жиляковой (см. [26]-[33]) рассмотрены эйлеровы ресурсные сети и исследованы свойства симметричных, квазисимметричных и неполных однородных симметричных сетей, которые обладают тем свойством, что при больших ресурсах их предельное состояние полностью зависит от начального состояния в сети. Исследованы свойства несимметричных ресурсных сетей и вопросы о сходимости процесса перераспределения ресурса и о нахождении предельных состояний при малых суммарных ресурсах. Исследован процесс функционирования таких сетей в случае ресурса большего, чем пороговое значение. Показано, что в этом случае некоторые вершины ресурсной сети (аттракторы) собирают в себе излишки ресурса, а ресурс в остальных вершинах ресурсной сети в предельном состоянии одинаков при любом количестве ресурса, находящегося в сети. Доказано, что в этом случае имеет место стабилизация процесса перераспределения при любой величине суммарного ресурса (большей порогового значения) и его начальном распределении по вершинам ресурсной сети.

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

состояниях в сети возникают периодические колебания, названные предельным циклом. А при большом суммарном ресурсе, большем порогового значения, свойство цикличности перестает оказывать влияние на процессы перераспределения ресурса, происходящие в сети. Доказано, что такие сети имеют единственное пороговое значение ресурса (см. [26]-[33]). Также в работе В.А. Скороходова [47] исследованы и разработаны методы решения задачи для нахождения порогового значения в эргодической ресурсной сети. Показано что, данная задача сводится к решению системы линейных алгебраических уравнений, описывающей закономерности перераспределения ресурса в сети.

В работах Я.М. Ерусалимского, Е.О. Басанговой, С.Ю. Логвинова, В.А. Скороходова, А.Г. Петросяна (см. [12], [13], [20]-[25], [41], [45]) исследованы графы и сети с нестандартной достижимостью, описаны различные виды ограничений на достижимость. Отличительной особенностью графов с нестандартной достижимостью является тот факт, что допустимыми являются не все возможные пути в сети, а только те пути, которые удовлетворяют некоторым дополнительным условиям. Показано, что в общем случае невозможно применение классических алгоритмов для решения задач на графах с нестандартной достижимостью.

Общим подходом к решению задач на орграфах с ограничениями на достижимости является построение вспомогательного графа (развертки) исходного графа, имеющего большее количество вершин и обладающего следующим свойством: допустимому пути на исходном графе с ограничениями соответствует некоторый путь на вспомогательном графе, а недопустимому пути не соответствует ни одного пути (см., например, [25]). Конструкция развертки определяется типом ограничения на достижимость. Для графов с нестандартными достижимостями описанных видов рассмотрены классические задачи о кратчайшем пути, о максимальном потоке и о случайных блужданиях. Наибольшую сложность вызывают две последние задачи, так как при построении вспомогательного графа

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

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

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

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

1. Описание потоков в ресурсных сетях с нестандартной достижимостью при больших и малых ресурсах. Исследование функционирования периодических динамических ресурсных сетей при малых ресурсах.

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

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

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

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

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

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

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

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

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

3. Исследованы потоки в эргодических ресурсных сетях с нестандартной достижимостью. Доказано, что при суммарном ресурсе, равном пороговому значению, предельный поток в ресурсной сети с магнитной достижимостью существует и единственен. Получены условия существования предельного состояния в ресурсной сети с вентильной достижимостью (теоремы 2.3 и 2.4).

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

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

Основные положения, выносимые на защиту:

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

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

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

4. Методы нахождения основных характеристик двухресурсной сети: порогового значения Т и предельного состояния при любых величинах первого и второго ресурса.

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

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

Область исследования. Область исследования и содержание диссертационной работы соответствует паспорту специальности 05.13.17 -Теоретические основы информатики. Область исследования соответствует п.10 «Разработка основ математической теории языков и грамматик, теории

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

Апробация работы. Основные результаты докладывались и обсуждались на различных конференциях и семинарах:

• VI Международная научная конференция «Современные методы и проблемы теории операторов и гармонического анализа — VI». Ростов-на-Дону, 2016.

• Международная конференция «Воронежская весенняя школа «Понтрягинские чтения — XXVII» ». Воронеж, 2016.

• IX Международная научная конференция «Современные методы прикладной математики, теории управления и компьютерных технологий (ПМТУКТ-2016)». Воронеж, 2016.

• VII Международная научная конференция «Современные методы и проблемы теории операторов и гармонического анализа — VII». Ростов-на-Дону, 2017.

• Международная конференция «Воронежская весенняя математическая школа «Понтрягинские чтения — XXVIII», Воронеж, 2017.

• VIII Международная научная конференция «Современные методы и проблемы теории операторов и гармонического анализа — VIII», Ростов-на-Дону, 2018.

• Семинар кафедры алгебры и дискретной математики Южного федерального университета (Ростов-на-Дону, 2015-2019, рук. проф. Ерусалимский Я.М.).

• Семинар лаборатории № 11 Института проблем управления им. В.А. Трапезникова РАН (Москва, 2019, рук. проф. Кузнецов О.П.)

Публикации. Результаты диссертации опубликованы в 10 научных работах, 4 из которых опубликованы в рекомендованных ВАК РФ рецензируемых научных изданиях. В совместных публикациях в диссертацию включены результаты, принадлежащие лично автору.

Объём и структура диссертации. Работа состоит из введения, трех глав, заключения и библиографического списка из 69 наименований. Общий объём диссертации составляет 121 страницы. Диссертационная работа содержит 33 рисунка.

Основное содержание работы

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

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

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

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

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

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

Теорема 2.2. На полуэргодической вспомогательной сети G' исходной сети О с накоплением неубывающей магнитности существует пороговое значение суммарного ресурса Т имеет вид:

р

Т = 1 б;

7=1 '

где - величина максимального предельного ресурса в вершине х^

эргодической подсети О" вспомогательной сети G', при котором все вершины находятся в зоне I~, р - количество вершин подсети О".

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

Теорема 2.3. Если Ж0 > Т0, то существует предельное состояние для вспомогательной сети О'.

Теорема 2.4. Для величины Ж = Ж0 + в(Н0) имеют место следующие утверждения:

1. если Ж > Т, то на вспомогательной сети существует предельное состояние.

2. если Ж < Т, то существование предельного состояния на вспомогательной сети зависит от начального состояния.

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

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

Теорема 2.5. Имеют место следующие утверждения:

1. Пороговое значение Т динамической сети О0(Х,и,/,Б) равно Т + Т + + Т

Т = —-2 "'—-, где Я = НОД(Б, К) и Тв - пороговое значение суммарного

ресурса компоненты Нв (в = 1,2,..., Я);

2. Если величина суммарного ресурса Ж равна значению Т, тогда предельное состояние О* существует, единственно и составляется из предельных состояний компонент Нв (в = 1,2,..., Я).

В главе 3 «Двухресурсные сети» рассмотрены модель распределения двух ресурсов в однородных и несимметричных двусторонних полных сетях и разработана метода нахождения порогового значения и предельного состояния для произвольных двух величин суммарных ресурсов в сети.

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

Теорема 3.1. Для однородной двусторонней полной сети с двумя

йв]-.

ресурсами и для любого суммарного ресурса Ж = Ж + Ж имеет место:

1) если Ж < гп2, то при любом начальном состоянии 0(0), его

Ж Ж Ж

предельным состоянием является вектор 0* = (—;—;...;—),

п п п

0* / 'Ж2 Ж 2 'Ж2 \ 2 =(—;—;...;—). п п п

2) если Ж > гп2, то при любом начальном состоянии 0(0) сети, в котором хотя бы в двух вершинах ресурсы не равны, выравнивание не происходит, т.е. в предельном состоянии 0* также не во всех вершинах ресурсы будут равны, здесь имеем два случая:

I) если Ж < гп2, то выравнивается первый ресурс, и не выравнивается второй ресурс.

II) если Ж > гп2, то оба ресурса не выравниваются. Сформулирована и доказана теорема о существования предельного

состояния в несимметричных двусторонних полных ресурсных сетях. Теорема 3.2. Для ресурсной сети с пороговым значением Т

Ж

1) если Ж<Т, то для всех вершин #*= — 0, т.е. вектор предельного состояния имеет вид:

Список литературы диссертационного исследования кандидат наук Абдулрахман Хайдар, 2020 год

Литература

1. Абдулрахман, Х. Ресурсные сети с вентильной достижимостью / Х. Абдулрахман, Я.М. Ерусалимский, В.А. Скороходов // Инженерный вестник Дона. - 2018. - № 4. - 12 с. URL: www.ivdon.ru/magazine/archive/ n4y2018/5264.

2. Абдулрахман, Х. Полные двух ресурсные сети с петлями / Х. Абдулрахман, В.А. Скороходов // Известия ВУЗов. Северо-Кавказский регион. Естественные науки. - 2016. - № 2. - С. 10-16.

3. Абдулрахман, Х. Ресурсные сети с магнитной достижимостью / Х. Абдулрахман, В.А. Скороходов // Известия ВУЗов. Северо-Кавказский регион. Естественные науки. - 2016. - № 4. - С. 4-10.

4. Абдулрахман, Х. О распределении ресурсного потока в двухресурсных

сетях / Х. Абдулрахман, В.А. Скороходов // Международная научная конференция «Современные методы и проблемы теории операторов и гармонического анализа и их приложения - VI» в г. Ростове-на-Дону. Тезисы докладов. Издательский центр ДГТУ, Ростов-на-Дону, 2016. - C. 150.

5. Абдулрахман, Х. О потоках в двухресурсных сетях / Х. Абдулрахман, Я.М.

Ерусалимский, В.А. Скороходов // Современные методы теории краевых задач: материалы международной конференции: Воронежская весенняя математическая школа «Понтрягинские чтения - XXVII». - Воронеж: Издательский дом ВГУ, 2016. - C. 3-4.

6. Абдулрахман, Х. О ресурсных сетях с вентильной достижимостью / Х.

Абдулрахман, Я.М. Ерусалимский, В.А. Скороходов // Современные методы прикладной математики, теории управления и компьютерных технологий: сб. тр. IX междунар. конф. «ПМТУКТ-2016». - Воронеж: Изд-во «Научная книга», 2016. - с. 20-21.

7. Абдулрахман, Х. On ergodic biresources networks with magnetic reachability /

Х. Абдулрахман, В.А. Скороходов // Международная научная

конференция «Современные методы и проблемы теории операторов и гармонического анализа и их приложения — VII» в г. Ростове-на-Дону. Тезисы докладов. Издательский центр ДГТУ, Ростов-на-Дону, 2017. - C. 160.

8. Абдулрахман, Х. О потоках в двухресурсных сетях с магнитной достижимостью / Х. Абдулрахман, Я.М. Ерусалимский, В.А. Скороходов // Современные методы теории краевых задач: материалы международной конференции: Воронежская весенняя математическая школа «Понтрягинские чтения - XXVIII». - Воронеж: Издательский дом ВГУ, 2017. - C. 11.

9. Абдулрахман, Х. On dynamic resources networks. The case of low resource /

Х. Абдулрахман, В.А. Скороходов // Международная научная конференция «Современные методы и проблемы теории операторов и гармонического анализа и их приложения -VIII». - Ростов-на-Дону, 2018. - С. 134.

10. Агаев, Р.П. Метод проекции в задаче о консенсусе и регуляризованный

предел степеней стохастической матрицы / Р.П. Агаев, П.Ю. Чеботарев // Автоматика и телемеханика. - 2011. - № 12. - С. 38-59.

11. Адельсон-Вельский, Г.М. Потоковые алгоритмы / Г.М. Адельсон-Вельский, Е.А. Диниц, A.B. Карзанов. - М.: Наука, 1975. - 119 с.

12. Басангова, Е.О. Смешанная достижимость на частично ориентированных

графах / Е.О. Басангова, Я.М. Ерусалимский // Деп. в ВИНИТИ, 1982, №5892 - 18 с.

13. Басангова, Е.О. Различные виды смешанной достижимости / Е.О. Басангова, Я.М. Ерусалимский // Алгебра и дискретная математика. -Элиста, КГУ. - 1985. - С. 70-75.

14. Басакер, Р.Д. Конечные графы и сети / Р.Д. Басакер, Т.Л. Саати; [Пер. с

англ.]. - М.: Наука, 1974. - 366 с.

15. Берж, К. Теория графов и ее применения / К. Берж; [Пер. с франц.]. - М.:

Издательство Иностранной литературы, 1962. - 320 с.

16. Гантмахер, Ф.Р. Теория матриц / Ф.Р. Гантмахер. - М.: Физматлит, 2004.

- 560 с.

17. Ерзин, А.И. Задача поиска сбалансированного потока / А.И. Ерзин, И.И.

Тахонов // Сибирский журнал индустриальной математики. - 2006, - Т. IX, № 4 (28). - С. 50-63.

18. Ерзин, А.И. Равновесное распределение ресурсов в сетевой модели / А.И.

Ерзин, И.И. Тахонов // Сибирский журнал индустриальной математики.

- 2005, - Т. VIII, № 3(23). - С. 58-68.

19. Ерусалимский, Я.М. Дискретная математика: теория, задачи, приложения

/ Я.М. Ерусалимский. - М.: Вузовская книга, 2001. - 279 с.

20. Ерусалимский, Я.М. Потоки в сетях с нестандартной достижимостью / Я.М. Ерусалимский // Известия вузов. Северо-Кавказский регион. Ест. науки. - 2012. - № 1. - С. 5-7.

21. Ерусалимский, Я.М. Некоторые задачи достижимости на графах с ограничениями / Я.М. Ерусалимский, С.Ю. Логвинов // Известия ВУЗов. Северо-Кавказский регион. Естественные науки. - 1996. - №2. - С. 1417.

22. Ерусалимский, Я.М. Многопродуктовые потоки в сетях с нестандартной

достижимостью / Я.М. Ерусалимский, А.Г. Петросян // Известия ВУЗов. Северо-Кавказский регион. Естественные науки. Приложение. - 2005. -№6. - С. 8-16.

23. Ерусалимский, Я.М. Общий подход к нестандартной достижимости на

графах / Я.М. Ерусалимский, В.А. Скороходов.// Известия вузов. СевероКавказский регион. Естестественные науки. - 2005. - Спецвыпуск. Псевдодифференциальные уравнения и некоторые проблемы математической физики. - С. 64-67.

24. Ерусалимский, Я.М. Графы с вентильной достижимостью. Марковские

процессы и потоки в сетях. / Я.М. Ерусалимский, В.А. Скороходов.// Известия ВУЗов. Северо-Кавказский регион. Естественные науки. -2003. - №2. - С. 3-5.

25. Ерусалимский, Я.М. Графы с нестандартной достижимостью: задачи, приложения: моногр / Я.М. Ерусалимский, В.А. Скороходов, М.В. Кузьминова, А.Г. Петросян. - Ростов-на-Дону: Южный федеральный университет, 2009. - 195 с.

26. Жилякова, Л.Ю. Несимметричные ресурсные сети. I. Процессы стабилизации при малых ресурсах / Л.Ю. Жилякова // Автоматика и телемеханика. - 2011. - №4. - С.133-143.

27. Жилякова, Л.Ю. Несимметричные ресурсные сети. II. Потоки при больших ресурсах и их стабилизация / Л.Ю. Жилякова // Автоматика и телемеханика. - 2012. - №6. - С. 103-118.

28. Жилякова, Л.Ю. Несимметричные ресурсные сети. III. Исследование предельных состояний / Л.Ю. Жилякова // Автоматика и телемеханика. -2012. - №7. - С. 67-77.

29. Жилякова, Л.Ю. Полные несимметричные ресурсные сети. Случай одного

приемника / Л.Ю. Жилякова // Известия высших учебных заведений СевероКавказский регион. - 2011. - № 4 (164). - С. 14-18.

30. Жилякова, Л.Ю. Исследование эйлеровых ресурсных сетей / Л.Ю. Жилякова // Управление большими системами. Выпуск 41. - М.: ИПУ РАН, 2013. - С. 28-50.

31. Жилякова, Л.Ю. Эргодические циклические ресурсные сети. I. Колебания

и равновесные состояния при малых ресурсах / Л.Ю. Жилякова // Управление большими системами. Выпуск 43. - М.: ИПУ РАН, 2013. -С. 34-54.

32. Жилякова, Л.Ю. Эргодические циклические ресурсные сети. II. Большие

ресурсы / Л.Ю. Жилякова // Управление большими системами. Выпуск 45. - М.: ИПУ РАН, 2013. - С. 6-29.

33. Жилякова, Л.Ю. Управление предельными состояниями в поглощающих

ресурсных сетях / Л.Ю. Жилякова // Проблемы управления. - 2013. -№ 3. -С. 51-59.

34. Замбицкий, Д.К. Алгоритмы решения оптимизационных задач на сетях. /

Д.К. Замбицкий, Д.Д. Лозовану. - Кишинев: Штиинца, 1983. - 171 с.

35. Зыков, A.A. Основы теории графов. / A.A. Зыков. - М: Вузовская книга,

2004. - 664 с.

36. Кемени, Дж. Конечные цепи Маркова. / Дж. Кемени, Дж. Снелл. - М.:

Наука, 1970. - 272 с.

37. Кристофидес, Н. Теория графов. Алгоритмический подход. / Н. Кристофидес; [Пер. с англ.]. - М.: Наука, 1978. - 432с.

38. Кузнецов, О.П. Однородные ресурсные сети. I. Полные графы / О.П. Кузнецов // Автоматика и телемеханика. - 2009. - № 11. - С. 136-147.

39. Кузнецов, О.П. Двусторонние ресурсные сети - новая потоковая модель /

О.П. Кузнецов, Л.Ю. Жилякова // Доклады Академии Наук. - 2010. -Т. 433, № 5. - С. 609-612.

40. Кузнецов, О.П. Полные двусторонние ресурсные сети с произвольными

пропускными способностями / О.П. Кузнецов, Л.Ю. Жилякова // Управление большими системами. Специальный выпуск 30.1 "Сетевые модели в управлении". -М.: ИПУ РАН, 2010. - С. 640-664. 41 . Кузьминова, М.В. Ограниченные магнитные достижимости на ориентированных графах / М.В. Кузьминова // Известия ВУЗов. СевероКавказский регион. Естественные науки. Приложение. - 2006. - №6. - С. 12-26.

42. Ope, О. Графы и их применение / О. Ope [Пер. с англ.]. - М : Мир, 1965. -

176 с.

43. Ope, О. Теория графов / О. Ope. [Пер. с англ.]. - М : Наука, 1980. - 334 с.

44. Свами, М. Графы, сети и алгоритмы / М. Свами, К. Тхуласираман. [Пер. с

англ.]. - М.: Мир, 1984. - 454 с.

45. Скороходов, В.А. Графы с магнитной достижимостью. Марковские процессы и потоки в сетях / В.А. Скороходов. - Ростов-на-Дону, 2003. -16с. деп. в ВИНИТИ, 06.03.2003, № 410-В2003.

46. Скороходов, В.А. Устойчивость и стационарное распределение на графах

с нестандартной достижимостью / В.А. Скороходов // Известия ВУЗов. Северо-Кавказский регион. Естественные науки. - 2007. - № 4. - С. 17-21.

47. Скороходов, В.А. Задача нахождения порогового значения в эргодической ресурсной сети / В.А. Скороходов // Управление большими системами. Выпуск 63. - М.: ИПУ РАН, 2016. - С. 6-23.

48. Скороходов, В.А. Динамические ресурсные сети. Случай малого ресурса /

В.А. Скороходов, Х. Абдулрахман // Вестник Воронежского государственного университета. Серия: Физика. Математика. - 2018. --№ 4. - С.186-194.

49. Скороходов, В.А. Задача о максимальном потоке в сети с особыми условиями распределения потока / В.А. Скороходов, А.С. Чеботарева // Дискретный анализ и исследование операций. - 2015. - Т. 22, № 3. - C. 55-74.

50. Стефанюк, В.Л. Обобщенные цепи Маркова / В.Л. Стефанюк // Искусственный интеллект и принятие решений. - 2011. - №4. -С. 95-99.

51. Татт, У. Теория графов / У. Татт. - М.: Мир, 1988. - 424 с.

52. Тутубалин, В.Н. Теория вероятностей и случайных процессов / В.Н. Тутубалин. - М.: Изд-во МГУ, 1992. - 400 с.

53. Фаддеев, Д.К., Фаддеева В.Н. Вычислительные методы линейной алгебры

/ Д.К. Фаддеев, В.Н. Фаддеева. - М.: Физматлит, 1963. - 656 с.

54. Форд, Л.Р. Потоки в сетях / Л.Р. Форд, Д.Р. Фалкерсон; [Пер. с англ.]. -

М.: Мир, 1966. - 276 с.

55. Харари, Ф. Теория графов / Ф. Харари; [Пер. с англ.]. - М.: Мир, 1973. - 300 с.

56. Харари, Ф. Перечисление графов / Ф. Харари, Е. Палмер; [Пер. с англ.]. -

М.: Мир, 1977. - 324 с.

57. Хорн, Р. Матричный анализ / Р.Хорн, Ч.Джонсон. - М.:Мир, 1989. - 655 с.

58. Aiello, W. Approximate load balancing on dynamic and asynchronous networks / W. Aiello, B. Awerbuch, B. Maggs, S. Rao. - Proc. 25th ACM Symp. of Theory of Computing. 1993. - P. 632-634.

59. Ahuja, R.K. Network Flows: Theory, Algorithms, and Applications / R.K. Ahuja, T.L. Magnanti, J.B. Orlin. - New Jersey: Prentice-Hall, Inc., 1993. -864 p.

60. Aldous, D.J. Lower bounds for covering times for reversible Markov chains

and random walks on graphs / D.J. Aldous. - J. Theoret. Probab. 2, no. 1. -1989. - P. 91-100.

61. Edmonds, J. Theoretical improvements in algorithmic efficiency for network

flow problems / J. Edmonds, R.M. Karp. - J. ACM. - 1972. - Vol. 19, №2. -P. 248-264.

62. Hajnal, J. The ergodic properties of non-homogeneous finite Markov chains / J.

Hajnal // Proc. Cambridge Philos. Soc. - 1956. - Vol. 52. - P. 67-77.

63. Hajnal, J. Weak ergodicity in non-homogeneous Markov chains / J. Hajnal //

Proc. Cambridge Philos. Soc. - 1958. - Vol. 54. - P. 233-246.

64. Hu, T.C. Multy-commodity network flows / T.C. Hu. - J. ORSA, 1963. - №11

(3). - P. 344-360.

65. Kuznetsov, O. P. Nonsymmetric resource networks. The study of limit states /

O. P. Kuznetsov, L.Yu. Zhilyakova // Management and Production Engineering Review. - Volume 2, Number 3, September 2011. - P. 33-39.

66. Lovasz, L. Mixing of Random Walks and Other Diffusions on a Graph / L.

Lovasz, P. Winkler // Surveys in Combinatorics, 1995 (ed. P. Rowlinson), London Math. Soc. Lecture Notes Series 218, Cambridge Univ. Press. - P. 119-154.

67. Meshbahi, M. Graph Theoretic Methods in Multiagent Networks / M. Meshbahi, M. Egerstedt. Princeton, NJ: Princeton University Press, 2010.

68. Meyn, S., Markov Chains and Stochastic Stability / S. Meyn, R.L. Tweedie.

Cambridge University Press, 2009. - 237 p.

69. Ren, W Distributed Coordination of Multi-agent Networks: Emergent Problems, Models, and Issues / W. Ren, Y. Cao. - London: Springer, 2011.