Вопрос про потоки

Правка ru1, от Mano, 2016-10-29 14:55:50

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

Теги потоки, max flow, графы, диница

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
ru1 Русский Mano 2016-10-29 14:55:50 625 Потоки (опубликовано)