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

• Автор: Ерусалимский, Яков Михайлович
• Шифр специальности: 05.13.17
• Научная степень: Докторская
• Год защиты: 2015
• Место защиты: Ростов-на-Дону
• Количество страниц: 258 с. : ил.

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

1.1. Основные определения

1.2. Смешанная достижимость на орграфах

1.3-Магнитная доетижимоеть-на орграфах 32 - -

1.4. Барьерная достижимость на графах

1.5. Обсуждение результатов главы

1.6. Выводы по главе

2. СЛУЧАЙНЫЕ БЛУЖДАНИЯ НА ГРАФАХ С ОГРАНИЧЕНИЯМИ НА ДОСТИЖИМОСТЬ

2.1. Случайные блуждания на графах со смешанной достижимостью
2.2. Случайные блуждания на графах с монотонной достижимостью
2.3. Случайные блуждания по графам с вентильной достижимостью
2.4. Случайные блуждания по графу-решётке
2.5.Заключение к главе
2.6. Выводы по главе
3. ПОТОКИ В СЕТЯХ С ОГРАНИЧЕНИЯМИ НА ДОСТИЖИМОСТЬ
3.1. Примеры потоков в сетях с ограничениями на достижимость
3.2. Основные определения теории потоков в сетях с ограничениями на достижимость
3.3. Вычислительный эксперимент
3.4. Заключение к главе 3
3.5. Выводы по главе
4. СМЕШАННАЯ ДОСТИЖИМОСТЬ ПОРЯДКА к . СТУПЕНЧАТАЯ ДОСТИЖИМОСТЬ. ОГРАНИЧЕНИЯ НА ДОСТИЖИМОСТЬ В ТЕРМИНАХ ВЕРШИН
4.1. Ступенчатая достижимость смешанная
достижимость порядка к
4.2. Смешанная достижимость порядка к
4.3. Ограничения на достижимость различных видов, определяемые в терминах вершин графа
4.4.Маршрутизация в информационных сетях. Достижимость с затуханиями на дугах и усилением в вершинах
4.5.Выводы по главе

5. ДИНАМИЧЕСКИЕ ПОТОКИ В СЕТЯХ
5.1 Основные определения
5.2. Ограничения на величину динамического потока
5.3. Временная развертка графа
5.4. Всплеск динамического потока, ёмкость сети . . .
5.5. Выводы по главе
6. ДИНАМИЧЕСКИЕ ГРАФЫ И СЕТИ
6.1. Динамические графы. Определение и примеры
6.2.-Временная развертка-динамического графа . .
6.3. Периодические динамические графы
6.4. Построение развёртки периодического динамического графа
6.5. О потоках в динамических сетях
6.6. Заключение к главе 6
6.7. Выводы по главе
7. СЕМЕЙСТВА ФУНКЦИЙ ГРАНДИ
7.1. Семейство функций Гранди ориентированного графа
7.2. Семейство функций Гранди неориентированного
графа
7.3. Выводы по главе
ЗАКЛЮЧЕНИЕ
БИБЛИОГРАФИЧЕСКИЙ СПИСОК
Приложение 1. Некоторые комбинаторные и полиномиальные
тождества
Приложение 2. Примеры решения задач на графах с ограничениями на достижимость
Приложение 3. О способах задания графов ограничениями на
достижимость и сетей со связанными дугами
Приложение 4. Акты об использовании результатов работы

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

Утверждение 1.4. ▼ Кратчайшему пути на развёртке С из вершины х° в вершины множества соответствует кратчайший
магнитно-накопительный путь на графе С . А
Таким образом, для нахождения кратчайшего пути на графе с магнитной достижимостью можно на развёртке графа применить известный алгоритм нахождения кратчайшего пути, а затем по найденному на развертке кратчайшему пути восстановить кратчайший путь на исходном графе с магнитной достижимостью.
Пример 1.2. Рассмотрим граф С , изображенный на рис. 1.6. Множество магнитных дуг Vм = {(а,Ь),{Ъ,с)} (помечены буквой «М»), множество немагнитных дуг ин = {(а,с),(Ь,с1),(с,с1)} (помечены буквой «Н»). Порядок магнитности будем считать равным единице (& = 1). Развёртка С для графа Є изображена на рис. 1.7.

Рис. 1.6. Граф (т
Рис. 1.7. Развёртка С'