Задача о максимальном потоке и алгоритм Форда-Фалкерсона

Графы часто используются для моделирования транспортных сетей — сетей, по ребрам которых передается некоторый трафик, а узлы выполняют функции «пере- садочных узлов» для передачи трафика по разным ребрам.
Представьте дорожную сеть, в которой ребра представляют дороги, а узлы — развязки; или компьютерную сеть, в которой ребра представляют каналы, способные передавать пакеты, а узлы — коммутаторы; или сеть трубопроводов, в которой ребра представляют трубы, а узлы — места соединения труб. Для сетевых моделей такого типа характерны некоторые компоненты: пропускные способности ребер, обозначающие максималь- ную величину передаваемого трафика; узлы-источники, генерирующие трафик; узлы-стоки (или приемники), «поглощающие» поступающий трафик; и наконец, сам трафик, передаваемый по ребрам.

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Задача о максимальном потоке и алгоритм Форда-Фалкерсона:

  1. коян: Восходящий узел - включение в общий поток; Нисходящий узел - исключение из общего потока.
  2. Наличие максимально полной информации о допрашиваемом
  3. 6. Таблица минимальных и максимальных размеров и сроков наказаний по Уголовному кодексу РФ 1996 г.
  4. Sшrvig Morten. Базовые алгоритмы Qt 4 (Qt 4's Generic Algorithms), 2000
  5. АЛГОРИТМ
  6. Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science, 2016
  7. АЛГОРИТМ УДАЧИ
  8. Алгоритм исцеления:
  9. § 2. АЛГОРИТМ АНАЛИЗА ПСИХОЛОГО-ПЕДАГОГИЧЕСКИХ СИТУАЦИЙ
  10. Альбатрос (восхождение на поток)
  11. Алгоритм избавления от боли
  12. ТЕОРИЯ ПОТОКА СОЗНАНИЯ
  13. 3.9. ПОТОК СОЗНАНИЯ
  14. ПОТОК СОЗНАНИЯ