Максимальный поток - обнаружение, если данный край обнаружен в некотором минимальном срезе

Question

Учитывая сеть G=(V,E), максимальный поток f и ребро e в E, мне нужно найти алгоритм efficeint, чтобы определить, есть ли какое-то минимальное сокращение, которое содержит e. Другой вопрос: если я обнаружил, что e содержится в некотором минимальном разрезе, можно ли определить, является ли это самым легким краем поперечного разреза?

Я думал о запуске алгоритма Форда-Фулкерсона и об увеличении / уменьшении пропускной способности данного фронта и посмотрим, что произойдет, но я не нашел ничего, что могло бы помочь мне решить проблему.

Я был бы признателен, если бы кто-нибудь мог указать мне на решение, спасибо заранее.

Answer 1

Вот решение для первого вопроса: Предположим, w(e) вес e, рассчитать минимальное значение для Gпредположим C, Затем мы удаляем e от G делать G'; снова мы рассчитываем минимальное значение для G'предположим C', если C-C'>=w(e), то это делает вывод, что eучаствуя хотя бы в одном мин-сокращении (это вы уже знаете), иначе e не принадлежит ни к какому минимальному разрезу.