Предпотоки и разметка

Алгоритм проталкивания предпотока работает с предпотоком и стремится пре- образовать его в поток. Алгоритм основан на интуитивном представлении о том, что поток естественным образом стекает «сверху вниз».
«Возвышенностями» для этого интуитивного представления являются метки h(v) для всех узлов v, определяемых и поддерживаемых алгоритмом (рис. 7.7). Мы будем проталкивать поток от узлов с большими метками к узлам с меньшими метками (в соответствии с аналогией о жидкости, стекающей сверху вниз). В более точной формулиров- ке разметка представляет собой функцию h: V ^ Z > 0, отображающую узлы на неотрицательные целые числа. Метки также будут называться высотами узлов. Разметка h и предпоток s-t будут называться совместимыми, если

♦ (i) (ограничения источника и стока) h(t) = 0 и h(s) = n,

♦ (ii) (ограничения крутизны) для всех ребер (v, w) в остаточном графе h(v) < h(w) + 1.

Рис. 7.7. Остаточный граф и совместимая разметка. Никакое ребро в остаточном графе

не может быть слишком «крутым» — высота начального узла не может превышать высоту конечного узла более чем на 1. У источника s высота должна быть равна h(s) = n; на схеме она не показана


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

Ключевое свойство совместимого предпотока и разметки заключается в том, что в остаточном графе не может существовать путь s-t.

(7.21) Если предпоток s-t совместим с разметкой h, то в остаточном графе Gf не существует путь s-t.

Доказательство. Утверждение доказывается от обратного. Пусть P — простой путь s-t в остаточном графе G. Обозначим узлы P: s, v1, ..., vk = t. По определе- нию разметки, совместимой с предпотоком f имеем h(s) = n. Ребро (s, v) входит в остаточный граф, а следовательно, h(v1) > h(s) - 1 = n - 1.

Используя индукцию по i и ограничение крутизны для ребра (v. - 1, v.), получаем, что для всех узлов v. в пути P высота равна минимум h(v) > n - i. Обратите внимание: последним узлом пути является vk = t; следовательно, мы приходим к тому, что h(t) > n - k. Однако h(t) = 0 по определению, а k < n, так как путь P является простым. Это противоречие доказывает исходное утверждение. ■

Вспомните из (7.9), что если в остаточном графе Gf потока f не существует пути s-t, то поток имеет максимальную величину. Из этого вытекает следующее следствие.

(7.22) Если поток s-t совместим с разметкой h, то f является потоком с макси- мальной величиной.

Следует заметить, что (7.21) относится к предпотокам, а утверждение (7.22) более ограничено в том отношении, что оно применимо только к потокам. Таким образом, алгоритм проталкивания предпотока ведет предпоток f и разметку h, совместимую с f, и работает над модификацией f и h, чтобы превратить f в поток. Когда f действительно станет потоком, мы можем при помощи (7.22) сделать вы- вод о том, что это поток с максимальной величиной. В свете сказанного алгоритм проталкивания предпотока можно рассматривать как механизм, ортогональный алгоритму Форда-Фалкерсона. Алгоритм Форда-Фалкерсона поддерживает до- пустимый поток, постепенно изменяя его в направлении оптимальности. Алгоритм проталкивания предпотока, напротив, поддерживает условие, из которого следует оптимальность предпотока f, чтобы он был допустимым потоком, а алгоритм по- степенно преобразует предпоток f в поток.

Для запуска алгоритма необходимо определить исходный предпоток f и совме- стимую с ним разметку h. Мы будем использовать исходную разметку h(v) = 0 для всех v ф s, и h(s) = n. Чтобы предпотокf был совместимым с этой разметкой, следует убедиться в том, что ни одно ребро, выходящее из s, не присутствует в остаточном графе (так как эти ребра не удовлетворяют ограничению крутизны). Для этого мы определяем исходный предпоток f (e) = ce для всех ребер e = (s, v), выходящих из источника, и f(e) = 0 для всех остальных ребер.

(7.23) Исходный предпоток f и разметка h совместимы.

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

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

  1. Упражнение РАЗМЕТКА ВАШИХ ЛИНИЙ ЖИЗНИ
  2. К учителям
  3. При оформлении анкеты следует соблюдать следующие правила:
  4. Почему я здесь?
  5. Л.О. Доліненко, В.О. Доліненко, С.О. Сарновська. Цивільне право України, 2006
  6. ЦИВІЛЬНЕ ПРАВО УКРАЇНИ
  7. ПЕРЕДМОВА
  8. Частина І ПРОГРАМА КУРСУ «ЦИВІЛЬНЕ ПРАВО УКРАЇНИ»
  9. Розділ І. Загальні положення цивільного права
  10. Тема 1. Поняття цивільного права. Предмет та метод, система цивільного права. Функції та принципи цивільного права
  11. Тема 2. Цивільне законодавство України
  12. Тема 3. Поняття, елементи та види цивільних правовідносин
  13. Тема 4. Здійснення цивільних прав і виконання обов’язків
  14. Тема 5. Захист цивільних прав та інтересів
  15. Тема 6. Об’єкти цивільних прав
  16. Тема 7.ФІЗИЧНІ особи як суб’єкти цивільного права
  17. Тема 8. Юридичні особи
  18. Тема 9. Держава як суб’єкт цивільного права. Територіальні громади та Автономна Республіка Крим як суб’єкти цивільного права