Предпотоки

Предпотоком s—t (или сокращенно предпотоком) называется функцияf связыва- ющая каждое ребро e с неотрицательным вещественным числом f : E ^ R+. Пред- поток f должен удовлетворять ограничениям пропускной способности:

(i) Для всех e E выполняется условие 0 < f (e) < с.

Вместо жестких ограничений сохранения потока обязательны только неравен- ства: для каждого узла, кроме s, входной поток должен быть по крайней мере не меньше выходного.

(ii) Для всех узлов v, кроме источника s, выполняется условие


Разность

называется избыточным потоком предпотока в узле v. Обратите внимание: предпо- ток, в котором все узлы, кроме s и t, имеют нулевой избыточный поток, является потоком, и величина потока равна в точности e (t) = -e (s). Для предпотока f можно определить концепцию остаточного графа Gf — точно так же, как это делалось для потока. Алгоритм «проталкивает» поток по ребрам остаточного графа (с исполь- зованием как прямых, так и обратных ребер).

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

Еще по теме Предпотоки:

  1. Л.О. Доліненко, В.О. Доліненко, С.О. Сарновська. Цивільне право України, 2006
  2. ЦИВІЛЬНЕ ПРАВО УКРАЇНИ
  3. ПЕРЕДМОВА
  4. Частина І ПРОГРАМА КУРСУ «ЦИВІЛЬНЕ ПРАВО УКРАЇНИ»
  5. Розділ І. Загальні положення цивільного права
  6. Тема 1. Поняття цивільного права. Предмет та метод, система цивільного права. Функції та принципи цивільного права
  7. Тема 2. Цивільне законодавство України
  8. Тема 3. Поняття, елементи та види цивільних правовідносин
  9. Тема 4. Здійснення цивільних прав і виконання обов’язків
  10. Тема 5. Захист цивільних прав та інтересів