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

Обложка ......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