Мы знаем, что вычисление максимального потока соотв. минимальный срез сети с емкостями эквивалентен; ср теорема о максимальном потоке .
У нас есть (более или менее эффективные) алгоритмы для вычисления максимальных потоков, и вычисление минимального сокращения при максимальном потоке также не является ни сложным, ни дорогим.
Но как насчет обратного? Учитывая минимальное сокращение, как мы можем определить максимальный поток? Без решения Max-Flow с нуля, конечно, и желательно быстрее, чем это тоже.
Некоторые мысли:
Из минимального среза мы знаем максимальное значение потока. Я не понимаю, как эта информация помогает стандартным подходам увеличивать пути и выдвигать, но адаптация последнего кажется немного более правдоподобной.
Мы не можем использовать минимальное сокращение, чтобы разделить сеть на две части и выполнить рекурсивный анализ, поскольку это не уменьшит проблему в худшем случае (если один раздел является одиночным); также у нас не было бы минимального сокращения меньших экземпляров.
Знание значения максимальной скорости потока ускоряет решение Max-Flow LP, возможно, из-за дополнительных условий расслабления?
источник
Ответы:
В худшем случае само минимальное сокращение не передает много информации о максимальном потоке. Рассмотрим граф в котором минимум s , t- cut имеет значение w . Если я расширяю G , добавляя новую вершину s ′ и ребро ( s ′ , s ) с весом w , минимальный s ′ , t- разрез в новом графе состоит только из ребра ( s ′ , s )G = ( V, E) с , т вес грамм s' ( с', с ) вес s', т ( с', с ) но это не дает никакой информации о том, как получить единиц потока от s до t .вес s T
Фактически, минимальное сокращение говорит вам о значении потока, но не о том, как этого добиться. Это означает, что знание минимального среза может ускорить поиск потока не более чем по логарифмическому коэффициенту, поскольку мы могли бы выполнить бинарный поиск, чтобы найти значение среза.
источник
Конечно, существуют алгоритмы, которые позволяют вычислить минимальное сокращение перед вычислением максимального потока. Два таких алгоритма - это алгоритмы push-relbel и псевдопоток, которые тесно связаны между собой. Последнее более эффективно. Оба этих алгоритма используют специальные свойства остаточного графа, которые они итеративно улучшают, чтобы получить максимальный поток из минимального разреза. Для подробностей я настоятельно рекомендую прочитать код и документы.
Чтобы детализировать случай принудительной пересылки, когда алгоритм не может больше выдвигать поток в приемник, он гарантированно рассчитал минимальное сокращение. Эта часть алгоритма называется фазой 1 из-за отсутствия лучшего названия. Фаза 2 является более эффективной стадией, где она преобразует минимальное сокращение в максимальный поток путем итеративной отмены циклов в остаточном графе, используя поиск на одной глубине и выталкивая избыток обратно к источнику. Я полагаю, что фаза 2 может оказаться бессимптомно более эффективной, чем фаза 1.
источник