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

Revision ru1, by Mano, 2016-10-29 14:55:50

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

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

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
ru1 Russian Mano 2016-10-29 14:55:50 625 Потоки (опубликовано)