Введение
1. Ограничения на достижимость различныхвидов, кратчайшие пути на графах с ограничениями на достижимость 24
1.1. Основные определения 24
1.2. Смешанная достижимость на орграфах 27
1.3. Магнитная достижимость на орграфах 32
1.4. Барьерная достижимость на графах 37
1.5. Обсуждение результатов главы 1 42
1.6. Выводы по главе 1 45
2. Случайные блуждания на графах с ограничениями на достижимость 46
2.1. Случайные блуждания на графах со смешанной достижимостью 48
2.2. Случайные блуждания на графах с монотонной достижимостью 52
2.3. Случайные блуждания по графам с вентильной достижимостью 59
2.4. Случайные блуждания по графу-решётке 66
2.5.Заключение к главе 2 78
2.6. Выводы по главе 2 79
3. Потоки в сетях с ограничениями на достижимость 80
3.1. Примеры потоков в сетях с ограничениями на достижимость 81
3.2. Основные определения теории потоков в сетях с ограничениями на достижимость 87
3.3. Вычислительный эксперимент 91
3.4. Заключение к главе 3 96
3.5. Выводы по главе 3 97
4. Смешанная достижимость порядка к. ступенчатая достижимость. ограничения надостижимость в терминах вершин 98
4.1. Ступенчатая достижимость смешанная достижимость порядка к 99
4.2. Смешанная достижимость порядка к 104
4.3. Ограничения на достижимость различных видов, определяемые в терминах вершин графа 108
4.4.Маршрутизация в информационных сетях. Достижимость с затуханиями на дугах и усилением в вершинах 120
4.5.Выводы по главе 4 125
5. Динамические потоки в сетях 126
5.1 Основные определения 126
5.2. Ограничения на величину динамического потока 131
5.3. Временная развертка графа 141
5.4. Всплеск динамического потока, ёмкость сети 149
5.5. Выводы по главе 5 165
6. Динамические графы и сети 166
6.1. Динамические графы. Определение и примеры 166
6.2. Временная развертка динамического графа 171
6.3. Периодические динамические графы 173
6.4. Построение развёртки периодического динамического графа 176
6.5. О потоках в динамических сетях 181
6.6. Заключение к главе 6 183
6.7. Выводы по главе 6 183
7. Семейства функций гранди 184
7.1. Семейство функций Гранди ориентированного графа 185
7.2. Семейство функций Гранди неориентированного
графа 191
7.3. Выводы по главе 7 193
Заключение 194
Библиографический список
