Проталкивание и изменение разметки

Теперь посмотрим, какие действия выполняет алгоритм для преобразования пред- потока f в допустимый поток, с сохранением его совместимости с некоторой раз- меткой h. Рассмотрим любой узел v с избыточным потоком (то есть e (v) > 0).
Если в остаточном графе Gf имеется ребро e, которое выходит из v и переходит к узлу w на меньшей высоте (следует учитывать, что h(v) превышает h(w) не более чем на 1 из-за ограничения крутизны), то f можно изменить, перемещая часть избыточного потока из v в w.

push( f,h,v,w)

Применяется, если e (v) > 0, h(w) < h(v) и (v,w) е Ef Если e= (v,w) - прямое ребро

Присвоить δ = тiп(e (v),ce - f (e)) и увеличить f(e) на δ Если (v,w) - обратное ребро

Присвоить e = (w,v), δ = miп(еf(v),f(e)) и уменьшить f(e) на δ Вернуть (f,h)

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

relabel (f,h,v)

Применяется, если e (v) > 0, и

для всех ребер (v,w) е Ef выполняется условие h(w) > h(v)

Увеличить h(v) на 1 Вернуть ( f, h)

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

Еще по теме Проталкивание и изменение разметки:

  1. Упражнение РАЗМЕТКА ВАШИХ ЛИНИЙ ЖИЗНИ
  2. Статья 652. Изменение или расторжение договора в связи с существенным изменением обстоятельств
  3. 7. Изменение и расторжение договора в связи с существенным изменением обстоятельств
  4. 2. Изменение учредительного договора вследствие изменения состава участников юридического лица
  5. § 17 Изменение в существующих обязательствах. – Общие причины изменения прав и обязанностей по договору. – Отступление от права и уступка. – Нарушение обязанности, вина. – Понятие о внимании и радении и ответственность. – Умедление и признаки его. – Ответственность за умедление.
  6. Изменение реальности
  7. Изменения и инновации.
  8. АФФЕРЕНТАЦИЯ ИЗМЕНЕННАЯ
  9. Суть сопротивления изменениям.
  10. § 2. Изменение и расторжение договора
  11. § 5. Изменение и расторжение договора
  12. ГЛАВА ДЕВЯТАЯ ИЗМЕНЕНИЕ Л И Ц В О Б Я З А Т Е Л Ь С Т В А Х
  13. Глава 11 ОРГАНИЗАЦИОННЫЕ ИЗМЕНЕНИЯ
  14. § 11.1. Сущность изменений в организации
  15. §61. ИЗМЕНЕНИЕ И РАСТОРЖЕНИЕ ДОГОВОРА
  16. Неопределенность в организации и проводимые изменения.