Потоки в сетях

Обложка ......Page 1
Титульный лист оригинала ......Page 3
Титульный лист ......Page 4
Аннотация ......Page 5
Предисловие ......Page 6
Введение ......Page 10
1. Сети ......Page 11
2. Потоки в сетях ......Page 15
3. Обозначения ......Page 22
4. Разрезы ......Page 23
5. Максимальный поток ......Page 25
6. Рассекающие множества и разрезы ......Page 30
7. Несколько источников и стоков ......Page 31
8. Метод расстановки пометок для решения задачи о максимальном потоке ......Page 34
9. Нижние границы дуговых потоков ......Page 40
10. Потоки в неориентированных и смешанных сетях ......Page 42
11. Пропускные способности узлов и другие обобщения ......Page 43
12. Линейное программирование и принципы двойственности ......Page 47
13. Максимальная величина потока как функция пропускных способностей двух дуг ......Page 52
Введение ......Page 60
1. Теорема о спросе и предложении ......Page 61
2. Симметричная теорема о спросе и предложении ......Page 69
3. Теорема о циркуляции ......Page 78
4. Теоремы Кёнига — Эгервари и Менгера о графах ......Page 84
5. Построение максимального независимого множества допустимых клеток ......Page 87
6. Задача на узкие места о назначении ......Page 90
7. Уникурсальные графы ......Page 92
8. Теорема Дилворта о цепном разложении частично упорядоченных множеств ......Page 96
9. Минимальное число исполнителей для выполнения твердого плана заданий ......Page 100
10. Представители множеств ......Page 104
11. Задача о подграфах ориентированного графа ......Page 116
12. Матрицы, состоящие из нулей и единиц ......Page 120
Введение ......Page 139
1. Задача Хитчкока ......Page 142
2. Задача об оптимальном назначении ......Page 164
3. Общая задача о потоке минимальной стоимости ......Page 166
4. Эквивалентность задачи Хитчкока и задачи о потоке минимальной стоимости ......Page 185
5. Алгоритм кратчайшей цепи ......Page 189
6. Задача минимальной стоимости о спросе и предложении: неотрицательные стоимости направленных циклов ......Page 195
7. Задача о складе ......Page 199
8. Задача о поставщике ......Page 203
9. Максимальный динамический поток ......Page 205
10. Кривая стоимости проекта ......Page 216
11. Построение циркуляции минимальной стоимости ......Page 232
1. Леса, деревья и деревья-остовы ......Page 242
2. Условия реализации ......Page 246
3. Эквивалентные сети ......Page 248
4. Синтез сети ......Page 260
Литература ......Page 267
Указатель ......Page 274
Оглавление ......Page 276