Анализ алгоритма: потоки и разрезы

Наша следующая цель — показать, что поток, возвращаемый алгоритмом Фор- да-Фалкерсона, имеет максимальную возможную величину для любого потока в G. Для этого мы вернемся к теме, поднятой в разделе 7.1: верхним границам для максимальной величины потока s-t, обусловленным структурой потоковой сети.
Одна из таких границ уже приводилась: величина v(f) любого потока s-t не превы-

шает С = Иногда эта граница приносит пользу, но иногда оказывается

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

Рассмотрим разбиение узлов графа на два множества A и B, для которых 5

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

Еще по теме Анализ алгоритма: потоки и разрезы:

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