Возникли проблемы с пониманием алгоритма максимального потока псевдокода для решения геометрических ограничений

Question

Итак, я пытаюсь пройтись по этой статье , которая в основном посвящена поиску минимальных плотных подграфов взвешенного графа (в контексте решения геометрических ограничений).

Плотный подграф - это тот, в котором сумма весов ребер и сумма весов вершин равны.

Автор объясняет, что это как-то эквивалентно алгоритму максимального потока, и поэтому он предлагает вариант стандартного алгоритма максимального потока, который, по его словам, более эффективен для этой задачи. Однако я не слишком знаком с концепциями, и нахожу фактическое описание очень тупым. Возможно, кто-то мог бы помочь мне с этим?

Алгоритм сформулирован следующим образом:

Я ужасно запутался в том, каким должен быть шаг 17, где фактически инициализируются потоки и как работает процесс дополнения.

В статье приводится пример:

Поэтому я попытался пройтись по примеру, но не смог заставить его сделать то, что должен. Кажется, что когда он зацикливается в первый раз, он посещает e1, v0 и v2 и помечает e0 и e2. Затем он посещает e0 и маркирует v2. Затем он посещает e2, но все его вершины уже посещены, поэтому алгоритм никогда ничего не делает. Как это увеличивает путь?

Заранее спасибо.

Answer 1

где потоки фактически инициализированы Это не так - недосмотр авторов. Предположим для всех e и v, что f _e ^v изначально равно нулю.

как работает процесс дополнения Шаг 17 заметно выше уровня, чем остальная часть процедуры. Дополнительные пути - это стандартная подтема о максимальном потоке, которая описана во многих текстах алгоритмов для студентов.

Давайте рассмотрим проблему потока, где все имеет вес 1.

a-->b
   ^
  /
 /
c-->d

Я не рисовал s и t. Предположим, что мы переместили одну единицу с c на b.

a-->b
   /
  /
 v
c-->d

Обратная дуга от b до c появляется потому, что, хотя мы не можем отправить поток с b до c в абсолютном смысле, мы можем отменить одну единицу, идущую от c до b, что математически имеет тот же эффект. Максимальный поток имеет значение 2, которое мы реализуем, увеличивая путь a -> b -> c -> d. Это просто означает, что нажмите одну единицу с a до b, отмените одну единицу до b с c, нажмите на одну единицу с c до d.

Вот некоторый псевдокод для шага 17.

Augment(vert, pred, amount)
  v = vert
  while true
    e = pred(v)
    f_e^v += amount
    if pred(e) is null
      break
    v = pred(e)
    f_e^v -= amount

amount должно быть наибольшим значением, которое не приводит к тому, что какое-либо ребро производит больше, чем его вес, или любая вершина потребляет больше, чем его вес.