Ресурсные сети и анализ их динамики

• Автор: Жилякова, Людмила Юрьевна
• Шифр специальности: 05.13.01
• Научная степень: Докторская
• Год защиты: 2013
• Место защиты: Москва
• Количество страниц: 305 с. : ил.

ОГЛАВЛЕНИЕ
ВВЕДЕНИЕ

ГЛАВА 1. ДИНАМИЧЕСКИЕ ГРАФОВЫЕ МОДЕЛИ

1.1. Потоковые модели

1.1.1. Классические потоковые модели

1.1.2. Потоки в сетях с нестандартной достижимостью

1.1.3. Задачи, сводящиеся к статическим потоковым моделям

1.1.4. Динамические задачи. Потоки во времени (flow overtime)

1.2. Случайные блуждания и рассеяние на графах

1.2.1. Области применения моделей случайного блуждания

1.2.2. Конечные цепи Маркова и их классификация

1.2.3. Графы переходов конечных цепей Маркова
1.2.4. Дискретная модель достижения консенсуса
1.2.5. Неоднородные цепи Маркова
1.3. Целочисленные пороговые модели
1.3.1. Chip-firing game
1.3.2. Модель «куча песка»
1.3.3. Графовая интерпретация «кучи песка» и chip-firing game
1.4. Ресурсная сеть
1.4.1. Основные определения
1.4.2. Классификация ресурсных сетей по топологии
1.4.3. Классификация ресурсных сетей по пропускным способностям
1.4.4. Полные однородные ресурсные сети
1.4.5. Ресурсная сеть и динамические графовые модели
ГЛАВА 2. МАРКОВСКИЕ ПРОЦЕССЫ В РЕГУЛЯРНЫХ РЕСУРСНЫХ СЕТЯХ. СВОЙСТВА РЕГУЛЯРНЫХ НЕСИММЕТРИЧНЫХ СЕТЕЙ
2.1. Предельное состояние регулярной сети при W=
2.2. Предельное состояние регулярной сети при малых ресурсах
2.3. Регулярные несимметричные сети и их свойства
2.4. Пороговое значение Т

2.5. Коэффициент симметричности сети
2.6. Аттракторы и их классификация
2.6.1. Потенциальные аттракторы
2.6.2. Классификация аттракторов
2.6.3. Признаки аттрактивности вершины
ГЛАВА 3. ПОТОКИ И ПРЕДЕЛЬНЫЕ СОСТОЯНИЯ В РЕГУЛЯРНЫХ НЕСИММЕТРИЧНЫХ СЕТЯХ
3.1. Поток ресурса
3.1.1. Поток при IV < Т
3.1.2. Поток при IV > Т
3.2. Семейство сетей, соответствующих одной стохастической матрице
3.2.1. Матрицы с большей выходной пропускной способностью вершин-источников
3.2.2. Матрицы с большей выходной пропускной способностью вершин-приемников
3.2.3. Матрицы с другой вершиной-приемником
3.3. Вектор £>’* и пороговое значение Т
3.4. Свойство аттрактивности и предельное состояние сети
3.5. Построение матрицы Я с произвольным количеством аттракторов по заданной матрице Я'
3.6. Оценка числа сетей с неединственным аттрактором
3.7. Полная сеть с одним приемником и одним источником
ГЛАВА 4. РЕГУЛЯРНЫЕ ЭЙЛЕРОВЫ СЕТИ
4.1. Существование предельного состояния и пороговое значение Т
4.2. Свойства эйлеровых сетей
4.3. Предельное состояние сети при 1 и IV <Т
4.4. Функционирование сети при ¥> Т
4.5. Предельные состояния и потоки при больших ресурсах
4.5.1. Предельное состояние сети при неизменной зоне ЯЙ?)
4.5.2. Предельное состояние эйлеровой сети. Общий случай
4.5.3. Предельные потоки при W > Т и задача нахождения вектора Ст (случай отсутствия ресурса в зоне Z~(0))
4.5.4. Задача нахождения вектора Ст (случай стационарной зоны ЯДЩ
4.5.5. Задача нахождения вектора Ст (общий случай)
ГЛАВА 5. ЭРГОДИЧЕСКИЕ ЦИКЛИЧЕСКИЕ СЕТИ
5.1. Элементарные циклы и их свойства
5.2. Функционирование произвольных циклических сетей при малом ресурсе
5.2.1. Функционирование циклической сети при W=
5.2.2. Предельные векторы и циклы «i-циклической сети
5.2.3. Достижение глобального равновесия при малых ресурсах
5.3. Пороговое значение Ти функционирование циклических сетей при больших ресурсах
5.3.1. Пороговое значение Т
5.3.2. Критерий аттрактивное и потенциальные аттракторы
5.3.3. Предельное состояние и предельный поток при больших ресурсах 198 ГЛАВА 6. ПОГЛОЩАЮЩИЕ СЕТИ
6.1. Свойства поглощающих ресурсных сетей
6.2. Поглощающие сети с единственным предельным состоянием
6.3. Поглощающие сети общего вида. Пороговое значение Т
6.4. Предельные состояния в поглощающих сетях
6.4.1. Матрица R,co и ее свойства
6.4.2. Вектор предельного состояния и его свойства
6.4.3. Нелинейное изменение промежуточных состояний
ГЛАВА 7. УПРАВЛЕНИЕ В РЕСУРСНЫХ СЕТЯХ
7.1. Управление в поглощающих сетях
7.1.1. Прямая задача управления. Распределение фиксированного суммарного ресурса между стоками

отдельно к исследованию эргодических цепей и исследованию цепей, в которых каждое эргодическое множество состоит из одного элемента. Такие цепи называются поглощающими цепями Маркова.
1.2.3. Графы переходов конечных цепей Маркова
Взвешенный орграф, соответствующий стохастической матрице Р, называется графом переходов [112]. Если неориентированный граф связен, то матрица неразложима. Если граф ориентирован, для неразложимости матрицы Р необходима сильная связность. Таким образом, смена состояний в однородной цепи Маркова эквивалентна переходу от вершины к вершине в конечном графе в соответствии с вероятностями, заданными весами на рёбрах. Такие процессы задают случайное блуждание на графе.
Покажем, что случайное блуждание можно задать на любом графе (не только на графе, соответствующем стохастической матрице). Рассмотрим сильно связный ориентированный граф С = (У,Е), п = У, т = Е (допускаются мультиребра и петли). Обозначим через ац количество ребер от
і до у, и через сіф - полустепени исхода и захода вершины і
соответственно. Если граф не ориентирован, сі, = с1~1 = сі[ - степень вершины.
Случайное блуждание на орграфе С начинается в некоторой вершине /0; после ? шагов оно переходит в вершину і,, из этой вершины на шаге Г +

блуждание может переместиться к любой вершине J с вероятностью

Множество вершин и вероятности перехода между ними задают цепь Маркова. Вершина /0 может быть фиксирована, а может сама быть выбрана на основании некоторого начального распределения сг° (где сг0 - вектор-строка). Обозначим через Р = (ри)пх„ матрицу переходных вероятностей этой цепи. Тогда: