Блог пользователя Mano

Вопрос про потоки
Автор Mano, история, 8 лет назад, По-русски

Возможно довольно глупый вопрос, но очень хочелось бы понять одну вещь, связанную с поиском макс. потока в графе. В алгоритме Форда Фалкерсона как в принципе и в алгоритме Диница мы ищем какой-то увеличивающий поток в остаточной сети и вот тут довольно магически выглядит возможность увеличивать поток, уменьшая предыдущий, т.е. например когда по ребру в одну сторону течёт flow < capacity, а в обратную течёт -flow < 0 и мы можем увеличить поток тем, что отменим этот, т.е. увеличить -flow в обратном направлении и уменьшить flow в прямом. Почему при этом не страдает первоначальный поток, который мы нашли?

  • Проголосовать: нравится
  • +15
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

Допустим, у нас есть ориентированное ребро (s, d), и мы пускаем x единиц потока против этого ребра. В этом случае мы как бы думаем про себя:

  1. В вершину s по какому-то пути из истока входили x единиц потока, проходили по ребру (s, d), а потом каким-то путем доходили до стока.
  2. Если мы найдем какой-либо способ пустить в вершину d x единиц потока в обход ребра (s, d), то мы можем уменьшить поток, входящий в вершину s и проходящий через ребро (s, d), на x, не уменьшив суммарный поток.
  3. Однако, если мы найдем способ довести эти x единиц потока из вершины s в сток в обход ребра (s, d), то мы увеличим суммарный поток на x единиц.

Вроде бы все.

→ Ответить
  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    Спаисбо большое! Теперь наконец-то разобрался с этим вопросом.

    → Ответить