После запуска алгоритма максимального потока найдите в потоковой сети все ребра, которые находятся в некотором минимальном разрезе.

Question

Пусть G = (V, A, s, t, U) - потоковая сеть. Предположим, мы получили максимальный поток. Есть ли быстрый алгоритм для поиска всех ребер, которые находятся в некотором минимальном разрезе?

Я знаю, что если x является максимальным потоком, то мы можем найти в остаточной сети G(x) набор S вершин, достижимых из источника s, и T набор вершин, из которых мы можем достичь t. И, следовательно, S и его дополнение - это min-cut. Более того, T и его дополнение также образуют min-cut.

Если, к сожалению, случается, что T не является дополнением к S, то min-cut не уникален. И мне интересно, есть ли хороший способ определить, принадлежат ли ребра, концы которых l ie ни в S, ни в T, минимальному разрезу или нет.

Answer 1

Каждый ar c u-->v принадлежит некоторому s--t min сокращению тогда и только тогда, когда

1. нет остаточного пути от u до t,
2. нет остаточного пути от s до v, и
3. нет остаточного пути от u до v.

Чтобы доказать, что если рассмотрим разрез, состоящий из вершин, достижимых из s или u по остаточному пути, который представляет собой s--t, разрезанный по (1), имеет нулевую остаточную пропускную способность и, следовательно, является разрезом s--t мин по построению, и содержит u-->v по (2) и (3).

Чтобы доказать направление только если, мы можем использовать разрез s--t min, содержащий u-->v, чтобы показать, что для каждого пути из u до t, от s до v или от u до v, некоторые ar c в пути не являются остаточными.

Это приведет вас к O(n m) времени довольно легко. Возможно, этого достаточно - если это не так, есть полезная литература по ответам на запросы о доступности в автономном режиме.