Введение
1. Основные определения, обозначения и свойства 12
1.1. Обозначения 12
1.2. Потоки в сетях 13
1.3. Декомпозиции потоков 16
1.4. Минимаксные потоковые теоремы 18
2. Приложения к классическим задачам комбинаторной оптимизации 20
2.1. Паросочетания и fr-паросочетания 20
2.2. Т-соединения 23
2.3. Упаковки Т-путей 24
2.4. Гаммоиды и дельта-гаммоиды 25
2.5. Матроидные паросочетания в гаммоидах 28
3. Пути в кососимметрических и двунаправленных графах 30
3.1. Введение 30
3.2. Фрагменты, ростки и барьеры 32
3.3. Алгоритм поиска регулярного пути 34
3.4. Реализация алгоритма поиска регулярного пути 36
3.5. Консервативность и регулярная консервативность 38
3.6. Алгоритм поиска кратчайшего регулярного пути 41
3.7. Реализация алгоритма поиска кратчайшего регулярного пути 44
3.8. Случай произвольных длин дуг 50
4. Стоимостные потоки в кососимметрических сетях 53
4.1. Введение 53
4.2. Алгоритм дополнения вдоль путей минимальной стоимости 54
4.3. Алгоритм сведения к задаче в стандартной направленной сети 59
5. Ациклические кососимметрические графы 62
5.1. Введение 62
5.2. Ациклические графы 63
5.3. Регулярно ациклические графы 64
5.4. Приложение к теории паросочетаний 66
5.5. Ациклическая декомпозиция 67
5.6. Алгоритм проверки регулярной ацикличности 67
5.7. Характеризация в терминах сильно связных компонент 72
6. Задача о цикле минимального среднего веса 75
6.1. Введение 75
6.2. Общий подход 76
6.3. Минимальные средние регулярные циклы 78
7. Потоки в простых кососимметрических сетях 81
7.1. Введение 81
7.2. Оценка мощности носителя ациклического потока 82
7.3. Оценка величины потока 86
7.4. Метод блокирующего потока 86
8. Декомпозиция многополюсных потоков 88
8.1. Введение 88
8.2. Декомпозиция в направленных графах 89
8.3. Декомпозиция в кососимметрических графах 91
9. Мультипотоки в двунаправленных и кососимметрических сетях 94
9.1. Введение 94
9.2. Мультипотоки в кососимметрических сетях 97
9.3. Случай двух пар терминалов 99
9.4. Случай трех пар терминалов 101
9.5. Общий случай 104
9.6. Оценка времени работы 105
Литература 108
Предметный указатель 112
