Оглавление
Введение
1. Основные определения, обозначения и свойства
1.1. Обозначения
1.2. Потоки в сетях.
1.3. Декомпозиции потоков.
1.4. Минимаксные потоковые теоремы
2. Приложения к классическим задачам комбинаторной оптимизации
2.1. Паросочетания и 5наросочегания.
2.2. Тсоединения.
2.3. Упаковки Гпутей.
2.4. Гаммоиды и дельтагаммоиды
2.5. Матроидные паросочетания в гаммоидах
3. Пути в кососимметрических и двунаправленных графах
3.1. Введение
3.2. Фрагменты, ростки и барьеры.
3.3. Алгоритм поиска регулярного пути
3.4. Реализация алгоритма поиска регулярного пути
3.5. Консервативность и регулярная консервативность
3.6. Алгоритм поиска кратчайшего регулярного пути
3.7. Реализация алгоритма поиска кратчайшего регулярного пути
3.8. Случай произвольных длин дуг
4. Стоимостные потоки в кососимметрических сетях
4.1. Введение.
4.2. Алгоритм дополнения вдоль путей минимальной стоимости.
4.3. Алгоритм сведения к задаче в стандартной направленной сети
5. Ациклические кососимметрические графы
5.1. Введение.
5.2. Ациклические графы
5.3. Регулярно ациклические графы
5.4. Приложение к теории паросочетаний.
5.5. Ациклическая декомпозиция.
5.6. Алгоритм проверки регулярной ацикличности
5.7. Характеризация в терминах сильно связных компонент.
6. Задача о цикле минимального среднего веса
6.1. Введение.
6.2. Общий подход.
6.3. Минимальные средние регулярные циклы.
7. Потоки в простых кососимметрических сетях
7.1. Введение
7.2. Оценка мощности носителя ациклического потока
7.3. Оценка величины потока.
7.4. Метод блокирующего потока
8. Декомпозиция многополюсных потоков
8.1. Введение.
8.2. Декомпозиция в направленных графах.
8.3. Декомпозиция в кососимметрических графах
9. Мультипотоки в двунаправленных и кососимметрических сетях
9.1. Введение.
9.2. Мультипотоки в кососимметрических сетях.
9.3. Случай двух пар терминалов
9.4. Случай трех пар терминалов
9.5. Общий случай
9.6. Оценка времени работы.
Литература
- Київ+380960830922