Здравствуйте, у меня проблемы с изучением алгоритма Форда-Фалкерсона с помощью теоремы max-flow min-cut .
Согласно теореме, максимальный поток должен быть равен общему весу разрезаемых ребер.
Однако просмотр видео https://www.youtube.com/watch?v=Tl90tNtKvxs, это приводит меня в замешательство. Лектор говорит, что максимальный расход 19 по алгоритму Форда-Фалкерсона, но я не могу найти ни одного разреза с расходом 19. Что не так?
В вашей интерпретации теоремы о максимальном потоке и минимальном разрезе нет ничего неправильного.
Минимальный набор отрезков состоит из ребер SA и CD общей мощностью 19.
Чтобы сделать разрез и рассчитать его стоимость, вы можете:
Для приведенного выше минимального разреза S содержит вершины s и c, а D содержит остальные.
Разрез означает, что вы определяете разрез между истоком и стоком. Этот срез не обязательно должен быть прямой линией, кривой или любой другой формы.
Например, здесь я выбрал синий разрез таким образом, чтобы края AB, AD и CD проходили через разрез. Теперь, если мы посмотрим на назначенный поток этих ребер и суммируем их, мы получим 4+6+9=19.
Альтернативная огранка, например, зеленого цвета. Здесь у нас есть ребра BT, AD и AC, которые перемещаются «вперед», и ребро DC, которое перемещается « назад». Таким образом, сумма потоков равна 9+6+9-5=19. Таким образом, независимо от того, какой разрез мы делаем, сумма всегда равна 19 (конечно, нам нужно вести надлежащий учет и вычитать потоки в противоположном направлении).
Конечно, вы можете выбрать любой срез (например, срез сразу после истока или непосредственно перед сливом), если алгоритм выполнен правильно, то сумма всех этих срезов всегда равна 19. Это логично, так как если поток одного разреза будет больше (или меньше) 19, тогда существование разреза, который «продвигает» один узел с потоком 19, означает, что в этом узле поток исчез или появился.
Однако считается, что если вы будете перебирать все возможные разрезы, то минимальный разрез — это тот, при котором сумма мощностей максимальна. Так что мы можем, строго говоря, перебрать все возможные разрезы, и каждый раз следить за суммой мощностей, и в конце выбирать тот, с наименьшим расходом. Однако наивный подход, заключающийся в простом повторении всех разрезов, привел бы к алгоритму O(2n), что по сравнению с алгоритмом Форда–Фалкерсона, конечно не желательно.
