Расширения задачи о максимальном потоке

Полезность задачи о максимальном потоке в основном не имеет никакого отно- шения к самому факту моделирования сетевого трафика. Скорее она заключается в том, что многие задачи с нетривиальной составляющей комбинаторного поиска могут быть решены за полиномиальное время, потому что их удается свести к за- даче нахождения максимального потока или минимального разреза в направлен- ном графе.

Двудольные паросочетания — первое естественное практическое применение задачи в этом направлении; в следующих разделах рассматриваются и другие при- менения. На первых порах мы сохраним представление о потоке как об абстракт- ном «трафике» и будем искать более общие условия, которым этот трафик может подчиняться. Как выясняется, эти более общие условия могут принести пользу в будущем.

В частности, особое внимание будет уделено двум обобщениям задачи о мак- симальном потоке. Вы увидите, что оба случая приводятся к базовой задаче о мак- симальном потоке.

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

Еще по теме Расширения задачи о максимальном потоке:

  1. коян: Восходящий узел - включение в общий поток; Нисходящий узел - исключение из общего потока.
  2. Наличие максимально полной информации о допрашиваемом
  3. 6. Таблица минимальных и максимальных размеров и сроков наказаний по Уголовному кодексу РФ 1996 г.
  4. ВАРИКОЗНОЕ РАСШИРЕНИЕ ВЕН
  5. Альбатрос (восхождение на поток)
  6. ТЕОРИЯ ПОТОКА СОЗНАНИЯ
  7. 3.9. ПОТОК СОЗНАНИЯ
  8. ПОТОК СОЗНАНИЯ
  9. 3.12.2. Техника расширенного восприятия
  10. 2.2.1. Поток образов
  11. Расширение графического метода
  12. Глава 3. ОТКРОЙТЕ СВОЙ ПОТОК ОБРАЗОВ
  13. Самовоспитание как "расширение" сознания
  14. 12.2.1. Групповой поток образов
  15. 3.1. РАСШИРЕНИЕ НЕЙРОЛОГИЧЕСКОГО КОНТАКТА
  16. Расширение внутреннего кругозора
  17. 7.2.2. Расширение полноты ответа
  18. 7.2.2. Расширение полноты ответа