Дальнейший анализ: целочисленные потоки

Среди многочисленных следствий нашего анализа алгоритма Форда-Фалкерсона есть одно особенно важное. Согласно (7.2) в любой момент времени величина по- тока остается целочисленной, а согласно (7.9) в итоге формируется максимальный поток.
Следовательно:

(7.14) Если все пропускные способности потоковой сети являются целыми числами, то существует максимальный поток, для которого каждая величина по- тока f (e) также является целым числом.

Обратите внимание: (7.14) не утверждает, что каждый максимальный поток является целочисленным, а лишь то, что некоторый максимальный поток обладает этим свойством. Интересно, что в (7.14) алгоритм Форда-Фалкерсона никак не упоминается, но наш алгоритмический подход предоставляет, пожалуй, самый простой способ доказательства этого утверждения.

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

Еще по теме Дальнейший анализ: целочисленные потоки:

  1. коян: Восходящий узел - включение в общий поток; Нисходящий узел - исключение из общего потока.
  2. Альбатрос (восхождение на поток)
  3. ТЕОРИЯ ПОТОКА СОЗНАНИЯ
  4. 3.9. ПОТОК СОЗНАНИЯ
  5. ПОТОК СОЗНАНИЯ
  6. 2.2.1. Поток образов
  7. Глава 3. ОТКРОЙТЕ СВОЙ ПОТОК ОБРАЗОВ
  8. 12.2.1. Групповой поток образов
  9. МИХАЙ ЧИКСЕНТМИХАЙИ. В ПОИСКАХ ПОТОКА, 2015
  10. 13.5.1. Игра в поток образов
  11. 2.7. КАК ВЫЗВАТЬ ПОТОК ОБРАЗОВ
  12. 3.10. ТИПИЧНЫЙ ПОТОК ОБРАЗОВ
  13. 12.3.2. Сценарий группового потока образов
  14. РАБОТА С ДАЛЬНИМИ СИГНАЛАМИ. ПВБ
  15. Тема 18. Правовые системы стран Дальнего Востока
  16. Глава четырнадцатая. Дальнейшие рекомендации по духовному очищению
  17. 3.3. Дальнейшая реализация проекта
  18. II. 2. 7. Тетрады и дальнейшее разбиение множеств.