Введение
Глава 1. Обзор литературы. основные понятия и определения 12
1.1. Задача поиска максимального потока на графе 13
1.2. Обзор задач о динамическом потоке 24
1.3. Основные подходы к решению задач на графах с нестандартной достижимостью 28
Глава 2. Поток на графах с нестандартной достижимостью 47
2.1. Определение потока в сети с ограничениями на достижимость 49
2.2. Поток в сети с барьерными ограничениями на достижимость 50
2.3. Обобщение алгоритма поиска максимального потока на графах со связанными дугами 62
2.4. NP-полнота задачи нахождения максимального целочисленного потока с ограничениями на достижимость 73
Глава 3. Динамические потоки в сетях 100
3.1. Основные определения 100
3.2. Ограничение на величину динамического потока 102
3.3. Нахождение максимального всплеска на графе 110
3.4. Нахождение потока, имеющего максимальный объем 119
Заключение 131
Библиографический список используемой литературы
