Набор узлов в каждом минимальном разрезе потокового графа

Question

В настоящее время я работаю над упражнениями по изучению алгоритмов сетевого потока, и я застрял в подзадаче, которая, по моему мнению, необходима для решения одного такого упражнения.

Вопрос: как вычислить множество узлов, которые принадлежат каждому минимальному разрезу потокового графа?

Интуитивно понятно, что если используется Ford-Fulkerson и пути расширения выбираются таким образом, чтобы иметь минимальное количество ребер, это должно дать нам набор минимальной мощности среза, но должны ли эти узлы присутствовать при каждом минимальном сечении?

Если так, я не могу доказать это. Если нет, у меня нет никаких реальных идей. Возможно, найти механизм обмена ребрами в остаточном графе?

Пожалуйста помоги!

Answer 1

Я думаю, что я приготовил соответствующий ответ:

Утверждение: Каждый узел, который может быть в наборе минимального среза (на стороне источника), должен быть доступен для источника в графе остаточного потока Gf, возвращаемого максимальным потоком (т. Е. Форд-Фулкерсон).

Доказательство: предположим, нет. Тогда существует некоторый u такой, что в Fg нет su path и он находится в некотором множестве min-cut со стороны источника S'. Поскольку FF возвращает набор узлов, достижимых с помощью s, в качестве своего набора минимальных срезов (например, с помощью BFS), S' не возвращается FF. Это означает, что вы находитесь в T (сторона среза min-cut).

Теперь мы покажем, что нет средств для преобразования S в S 'при сохранении свойства min-cut. Предположим, это было возможно. Тогда любой алгоритм, способный к преобразованию, должен был бы иметь возможность идентифицировать su-путь для передачи потока от s к u в некотором остаточном графе. Обратите внимание, однако, что это невозможно.

Рассмотрим любое ребро (v, w) такое, что v находится в S, а w в T. Поскольку u не было в S, должно быть, что w не является u (т. Е. Не существует переднего ребра из S в u, иначе это будет в S уже). Тогда должно быть, что u сделан доступным для s, добавив передний фронт от S к T. Однако это невозможно! Только поток может быть добавлен к обратным краям с помощью свойства max-flow/min-cut. Требование тогда доказано.

Чтобы решить проблему, описанную выше, мы просто вычисляем набор всех узлов, которые могут быть в наборе минимального среза на стороне источника (назовем этот набор A), затем обращаем ребра и вычисляем набор всех узлов, которые могут быть в приемнике. со стороны min-cut (назовите это B), вычислите пересечение (назовите это C), а затем вычислите Ответ = A - C. Сложность этого алгоритма такая же, как и в FF, то есть O(|V|^3).

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