Появляется вопрос: действительно ли достаточно просто провести обход по остаточной сети, чтобы выделить минимальный разрез? Обычно считается, что если запустить обход и поместить все достижимые вершины в множество S, а остальные в T, этого должно быть достаточно. Однако, чтобы прояснить это утверждение, можно обратиться к обсуждению на <a href="https://cs.stackexchange.com/questions/33834/how-to-find-a-minimum-cut-of-a-network-flow" rel="nofollow">CSSE</a>, где сказано, что: <br/> <blockquote>Минимальный разрез - это разбиение узлов на две группы.<br/> <br/> После нахождения максимального потока, минимальный разрез можно определить, создав остаточную сеть и пройдя по ней от источника до всех достижимых узлов. Эти узлы определяют одну часть разбиения, назовем ее A. Оставшиеся узлы (недостижимые) можно назвать B. Размер минимального разреза равен сумме весов ребер в оригинальной сети, которые ведут от узла в A к узлу в B.<br/> </blockquote> <br/> <br/> Однако возникает контрпример: <br/>
Для нахождения минимального разреза в графе можно использовать алгоритм Эдмондса — Карпа, который является реализацией алгоритмаford-full. Он находит максимальный поток в сети, а затем минимальный разрез может быть определен с использованием остаточной сети. Как вы правильно заметили, достаточно провести обход по остаточной сети после того, как был найден максимальный поток. Этот обход позволяет выделить достижимые от источника узлы и их противоположность. Узлы, до которых можно добраться из источника в остаточной сети, образуют одно множество (обычно это обозначается как S), а недостижимые узлы — другое (обозначается как T). Это утверждение имеет под собой обоснование, так как минимальный разрез связан с максимальным потоком по теореме о максимальном потоке и минимальном разрезе. Однако важно помнить, что при измерении веса разреза, учитываются только те ребра, которые « ведут от S в T» (то есть из достижимых вершин в недостижимые). Тем не менее, контрпример может возникнуть, если рассматривать графы, у которых нет явных путей от источника к некоторым узлам в исходном графе (то есть результаты обхода могут оказаться не полными). Однако это преимущественно касается специфических структур графов или неверного применения алгоритма. Таким образом, в общем случае да, алгоритм нахождения максимального потока и последующий обход остаточной сети — это правильный и эффективный метод для определения минимального разреза.
У вас ошибка в понимании остаточной сети. Раз фиолетовые ребра насыщены, то на самом деле в остаточной сети есть обратные им ребра. И вершина v отлично найдется обходом из s.
Без этих обратных ребер алгоритм поиска потока не работает, ведь у него не будет возможности "отменять" потоки.
Например в графе:
________ a-b-c / | \ s | t \ v / d-e-f
Если сначала найдется поток по пути s-a-b-e-f-t, то дальше единственный способ его дополнить - это взять путь s-d-e-b-c-t, и надо будет "отменить" поток по перекрестному ребру b-e.